Distinct witnesses from incompatible unary predicates (${\bigwedge }_{ϵ\in \{0,1{\}}^k}\exists x{\bigwedge }_i{P}_i(x{)}^{{ϵ}_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.