Existence of a sentence $\varphi$ for finite structues

Question

How can I show that if $\mathcal{L} = \emptyset$ then there is no such $\mathcal{L}$-sentence $\varphi$ that is true in every finite structure of even cardinality and false in every finite structure of odd cardinality?

I suppose I should prove it by contradiction (seems intuitively the right way) and use maybe Vaught's test or Godel's completeness theorem.

So I would begin like this: Suppose there is such $\varphi$ and let $\mathcal{M}$ be any finite $\mathcal{L}$-structure such that $\mathcal{M} \models \varphi$. Therefore $|M| = 2n$ for some positive natural number $n$ (...)

I would gladly appreciate some hints, because I have no clue how to solve.

Answer 1

You are right that we should aim for a contradiction*. Let's assume there is some $\varphi$ that is true in all finite structures of even cardinality and false in all finite structures of odd cardinality. For each $n$ let $\psi_n$ express "there are at least $n$ elements" (convince yourself that such $\psi_n$ exists). We define two sets of formulas: $$ \Sigma = \{\varphi\} \cup \{\psi_n : n \in \mathbb{N}\} $$ and $$ \Sigma' = \{\neg \varphi\} \cup \{\psi_n : n \in \mathbb{N}\}. $$ Clearly, $\Sigma$ is finitely satisfiable, as there are arbitrarily large sets of even cardinality (an $\mathcal{L}$-structure for $\mathcal{L} = \emptyset$ is just a set). So by compactness there is some infinite $X \models \Sigma$. Let $X_0 \preceq X$ be a countable elementary substructure (either use downward Löwenheim-Skolem, but that is overkill here, so you can also convince yourself that any countable $X_0 \subseteq X$ works). Similarly, there is some infinite $Y \models \Sigma'$ with a countable $Y_0 \preceq Y$. As $X_0$ and $Y_0$ are both countable, there is a bijection between them, which is an isomorphism, as we are just considering the empty language.

So now we have that $X \models \Sigma$, so $X \models \varphi$ and hence $X_0 \models \varphi$. Using the isomorphism we then get $Y_0 \models \varphi$ and thus $Y \models \varphi$. However, the latter contradicts $Y \models \neg \varphi$, which we get from $Y \models \Sigma'$. So we find our contradiction and conclude that no such $\varphi$ can exist.

---

* = This is technically not a proof by contradiction. Proofs of the form "assume $X$ ... contradiction, so not $X$" are just the way we prove negation. A proof by contradiction would start by assuming the negation and then getting a positive answer, so something like "assume not $X$ ... contradiction, so $X$".

Answer 2

An alternative proof using ultraproducts, expanding on the hint I gave in the comments.

Let $M$ be a non-principal ultraproduct of sets of cardinalities $1, 3, \dots$ and $N$ be an ultraproduct of sets of cardinalities $2, 4, \dots$ with respect to the same ultrafilter. Because $\varphi$ is false in each structure of odd cardinality, $\varphi$ is false in $M$. Because $\varphi$ is true in each structure of even cardinality, $\varphi$ is true in $N$. We claim that this is a contradiction because $M$ and $N$ are isomorphic (i.e. are in bijection).

$M$ is a substructure of $N$ in the obvious way, namely via the componentwise inclusion. Conversely, each element of $N$ other than the equivalence class of $f(n) = 2n+2$ has a representative $g$ where $g(n) < f(n)$ for each $n$, i.e. each such element lies in this substructure $M$. Thus $M$ is in bijection with $N$ minus this one element. Because $N$ is infinite, $M$ is in bijection with $N$.