= Distinct witnesses from incompatible unary predicates
{title2=$\bigwedge_{\epsilon\in\{0,1\}^k}\exists x\,\bigwedge_iP_i(x)^{\epsilon_i}$}
The displayed <first-order sentence> requires a domain with at least $2^k$ elements without using <logical equality>. Distinct patterns disagree on some predicate, so a single element cannot witness both. Conversely, a domain consisting of the $2^k$ <binary strings> of length $k$, with $P_i$ selecting strings whose $i$th <bit> is one, realizes every pattern. More generally, requiring any $m$ distinct <unary predicate types> forces at least $m$ distinct elements.
Back to article page
