Showing that $|\phi(\mathcal{M})| = |\phi(\mathcal{N})|$ if $\phi(\mathcal{M}) \Subset M^n$ and $\mathcal{M} \equiv \mathcal{N}$

Question

Let $\phi \in L$ define a finite set $X$ in the $L$-structure $\mathcal{M}$. Show that in every $\mathcal{N}$ elementarily equivalent to $\mathcal{M}$, the set defined by $\phi$ has the same power as $X$.

1. Let $n$ denote the number of free variables of $\phi$. That is, let $\phi \in L_n$

2. Then $X = \phi(\mathcal{M}) = \{a^n \in M^n : \mathcal{M} \models \phi(\overline{a})\}$ and is a finite subset of $M^{n}$. That is, $X \Subset M^n$. Denote $|X| = k \in \mathbb{N}$.

3. Let $\mathcal{N}$ be an arbitrary $L$-structure s.t. $\mathcal{M} \equiv \mathcal{N}$. Then, by definition, $Th(\mathcal{M}) = Th(\mathcal{N})$.

4. Let $|\phi(\mathcal{N})| = Y$

   $\fbox{WANT:}$ $X = |\phi(\mathcal{M})| = |\phi(\mathcal{N})| = Y$

Now this would be easy to show if $\mathcal{M}$ were isomorphic to $\mathcal{N}$. But we cannot assume that unless $\mathcal{M}$ is finite. I'm not sure how then to proceed.

Answer 1

The property "there are exactly $k$ elements of $M^n$ satisfying $\phi$" is equivalent to a first-order sentence. Since it is true in $\mathcal{M}$, it is also true in $\mathcal{N}$.

This reduces the problem to identifying this sentence. Hint: Do you know how to write down a sentence expressing that there exist exactly $k$ things in the universe? Can you adapt this to realizations of $\phi$?