Question on finite structures

Question

I need to find a sentence such that it is valid for all finite structures but false in some infite structure. I've couldn't find any sentence that includes only "=" to be true in finite structures but false in infinte structures. Am I doing something wrong?

Answer 1

This can't be done if "=" is your only relation symbol (see below), but with a larger vocabulary this is possible.

Easiest solution, in my opinion, is to add a single function symbol $f$. For all finite structures, if $f$ is injective then it is surjective, but this fails for some infinite structures. So:

$$\forall x\forall y(f(x)=f(y)\to x=y)\to\forall x\exists y(f(y)=x)$$

As for the case where all you have is equality: you can show this can't be done using Ehrenfeucht–Fraïssé games. (See for example Marker, Model Theory, pp.52-55, especially Lemma 2.4.9.) Note that "structure" in this case simply means "set".

It is not hard to show the following using Lemma 2.4.9. If $M$ is a set with at least $n$ elements, and $N$ is an infinite set, then $M\equiv_n N$, where $\equiv_n$ means that a sentence with quantifier depth at most $n$ holds in $M$ if and only it holds in $N$. Let $\sigma$ be the sentence that fails in some infinite structure (say $N$). If $\sigma$ has quantifier depth $n$, then by the above, $\sigma$ also fails in $M$ if $M$ has at least $n$ elements. QED