Two elementary equivalent $L$-structures of a first order language $L$ have the same cardinality if one of them is finite.

Question

Let $M,N$ are elementary equivalent $L$-structures where $L$ is a first-order language. If $M$ is finite , then how to prove that $|M|=|N|$ ?

I was thinking like this. Let $|M|=n$. To prove $|N|=n$, I have to somehow write down the fact that $M$ has at least $n$ many elements by using a sentence (closed formula). If I can do that, then $M$ and $N$ proves same $L$-sentences would give me that $N$ has at least $n$ many elements. Now if $N$ had more than $n$ many elements then it would have at least $n+1$ many elements, then again using an $L$-sentence we would have $M$ has at least $n+1$ many elements , contradiction ! Hence that would prove $|N|=n$. But unfortunately I'm unable to write the fact that $M$ has at least $n$ many elements by using an $L$-sentence. (Perhaps if we could write $M$ has exactly $n$ many elements using some $L$-sentence, that would also work, but that seems even difficult)

Please help.

Answer 1

We have that $$ M\models\exists x_1...x_n\left(\bigwedge_{i,j\leq n, \ j\neq i}x_i\neq x_j\right) $$ then $$ N\models\exists x_1...x_n\left(\bigwedge_{i,j\leq n, \ j\neq i}x_i\neq x_j\right) $$

Now, if $$ N\models\exists x_{n+1}\exists x_1...x_n(\bigwedge_{i\leq n} x_{n+1}\neq x_i) $$

then $$ M\models\exists x_{n+1}\exists x_1...x_n(\bigwedge_{i\leq n} x_{n+1}\neq x_i) $$ but this is a contradiction, so $|N|=n$.

Answer 2

Let

$\phi_n := \forall z(z = x_1 \vee \dots z=x_n)$.

Let

$\psi_n := \exists x_1 \dots \exists x_n(x_1 \not = x_2 \wedge \dots \wedge x_1 \not = x_n \wedge \dots \wedge x_{n-1} \not = x_n \wedge \phi_n)$.

Then $M \models \psi_n$ iff $M$ has exactly $n$ elements.

So let now $M$ and $N$ be two elementary equivalent structures. Let $|M| = n$. Since $|M|=n$, it follows that $M \models \psi_n$. But $M$ and $N$ are elementary equivalent, so $N \models \psi_n$. Thus, $|N| = n$, as required.