Question: Let $\sigma$ be a signature that has only equality as a relation in it. Prove that there doesn't exist a statement $\phi$ s.t it's valid in M $\iff$ $|D^M|$ is odd.
My problem: I think the statement is false... but the textbook asks me to prove it. If I pick M s.t. $D^M=${1,2,3} and $\phi= \exists x \exists y (x=y)$ then I found a statement like the one I'm supposed to show doesn't exist... Where is my problem?
The problem is that the statement $\phi$ should be a statement which classifies this property for any finite model. For instance if $D^M=\{1,2,3,4\}$ then $\mathcal{M}\models \exists x\exists y (x=y)$. Thus your formula $\phi$ does not satisfy $\mathcal{M}\models \phi$ if and only if $|D^\mathcal{M}|$ is odd, for all finite structures $\mathcal{M}$.
One of the easier ways to prove this theorem, if you got the tools, is to use an Ehrenfeucht-Fraisse game. Just take two structures $M$ and $N$ of size $n$ and $n+1$ and show that we can play $n$ step between them (which is easy since there are no relations). Thus we may conclude that $M$ and $N$ satisfies the same formulas of quantifier rank at most $n$, and thus if $\phi$ exist, it can't have quantifier rank $n$, for any arbitrary number $n.$