Use Compactness Theorem to prove that "an even number of things with property Y" cannot be expressed in first order predicate logic

Question

I am trying to prove that "an even number of things have property Y" cannot be expressed in first order predicate logic. I need to prove this using compactness theorem. I have tried looking online but cannot figure this out as much as I try.

Answer 1

Assume for a contradiction that $\phi_0$ is a sentence that holds in a structure iff $Y(x)$ is true for an even number of values $x$. Now let $\phi_n$ for $n = 1, 2, \ldots$ assert that $Y(x)$ holds for at least $n$ values of $x$. Then any finite subset of $\Phi = \{\phi_0, \phi_1, \phi_2, \ldots\}$ has a model and hence is consistent. By compactness, $\Phi$ has a model, and in this model $Y(x)$ holds for infinitely many $x$. Even numbers are (usually assumed to be) finite, so $\phi_0$ can't be doing its job.

There is a a rationale for defining infinite cardinalities to be even. If you want to do this, then see Noah's answer.

Answer 2

The solution depends on what, exactly, we mean by "even." Is an infinite set even?

If we say that infinite sets are not even, then Rob's answer is correct.

However, we might also say that an infinite set is both even and odd. In this case, things are a bit trickier. HINT: suppose $\varphi$ says "There are an even number of objects." Then $\neg\varphi$ has arbitrarily large finite models, so by compactness it has an infinite model $\mathcal{A}\models\neg\varphi$. But we said above that infinity is both even and odd, so we must have $\mathcal{A}\models\varphi$; and this is a contradiction.