First-order definability of structures of at least $n$ elements

137 Views Asked by At

In class, we learned that it is possible to define structures of at least $n$ elements using the following WFF $\exists^{\geq n}$:

$$\exists x_1 \ldots x_n \bigwedge_{i \not= j} \neg (x_i = x_j)$$

Then, for any interpretation $(\mathcal A, \mathcal E^ \mathcal A)$, $(\mathcal A, \mathcal E^ \mathcal A) \models \exists^{\geq n}$ iff $|D_\mathcal A|$ has at least n elements.

But this statement is not quite true, is it? We make the implicit assumption that any first-order structure models equality logic.

So, a more correct statement would be

Then, for any interpretation $(\mathcal A, \mathcal E^ \mathcal A)$, $(\mathcal A, \mathcal E^ \mathcal A) \models \exists^{\geq n}$ iff $|D_\mathcal A|$ has at least n elements, provided that $(\mathcal A, \mathcal E^ \mathcal A)$ is a model of equality logic.

Here are my two questions:

  1. Is my reasoning correct? Am I missing something?
  2. If so, is there another way to prove / refute the first-order definability of structures of at least $n$ elements?

EDIT

In above argument I make the assumption that I treat $=$ as an arbitrary predicate symbol $P$, such that $P(x, y)$ is logically equivalent with $x=y$. By convention, $P(x, y)$ of course represents equality. But if we are talking about ALL first-order structures, we need to include those where $P(x, y)$ does not represent equality.