Undefinability of evenness in first order logic

Question

My question is to show there is no sentence $\psi$ in a language of first order logic without any non-logical symbols such that for every finite structure $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; \text{if and only if} \; | \mathcal{A} | \; \text{is even}.$$ Is there such a sentence $\psi$ if we add a unary function symbol $f$ to our language?

My attempt at a solution:

For the first part, suppose for contradiction there is such a $\psi$. Let $\Gamma = \{ \lnot \gamma _n : n \ge 0\}$ where $\lnot \gamma _n$ expresses there are 2n+1 objects.

Now let $\mathcal{A}$ be a structure such that $\mathcal{A} \vDash \Gamma$.

If $\mathcal{A}$ is finite, then $| \mathcal{A} |$ is even and so $\mathcal{A} \vDash \psi$.

We know $\{ \psi \}$ is consistent, since every finite, even structure is a model of $\{ \psi \}$. So by Lowenheim-Skolem theorem, $\{ \psi \}$ has a countable model, $\mathcal{B}$ say. So $\mathcal{B} \vDash \psi$.

So if $\mathcal{A}$ is infinite, then $\mathcal{A} \vDash \psi$ as $\mathcal{A}$ and $\mathcal{B}$ are equivalent(?).

Therefore, $\Gamma \vDash \psi$. So by compactness there is $\Gamma _0 \subset \Gamma$ finite such that $\Gamma _0 \vDash \psi$. This is a contradiction as we can easily find a model $\mathcal{C}$ of $\Gamma _0$ for which $\mathcal{C} \vDash \Gamma _0$ but $\mathcal{C}$ does not model $\psi$ : any model of cardinality $2k+1$ where $k$ is chosen greater than the index of any $\gamma _n$ occurring in $\Gamma _0$ will do. Thus, there is no such $\psi$.

Is the above method correct? I am unsure about the case when $\mathcal{A}$ is infinite and applying the Lowenheim-Skolem theorem. I also have no idea on the second part of the question. Any help would be appreciated. Thanks

Answer 1

We show that there if our language $L$ has (among perhaps other symbols) a unary function symbol $f$, then there is a sentence $\varphi$ with the following properties. (i) For every positive even integer $n$ there is an $L$-structure $A$ whose underlying set has cardinality $n$ and in which $\varphi$ is true and (ii) There is no odd positive integer $n$ such that $\varphi$ is true in a structure of cardinality $n$.

For example we can let $\varphi$ be the sentence $$\forall x(\lnot(f(x)=x)\land (f(f(x))=x)).$$

Added: Now that it has been added that the language for the first question has no non-logical symbols, we can make a few comments. Lowenheim-Skolem is not needed. Compactness shows that any sentence $\varphi$ which is true in finite sets of arbitrarily high cardinality is true in all sets.

Answer 2

I think your argument is OK but a little bit more involved that it has to be.

Assume for a contradiction that $\psi$ is a sentence of first-order logic with no nonlogical symbols, and that the finite models of $\psi$ are precisely the finite sets of even cardinality. Since $\psi$ has arbitrarily large finite models, by compactness $\psi$ has an infinite model $\mathcal A.$ Since $\neg\psi$ has arbitrarily large finite models, $\neg\psi$ has an infinite model $\mathcal B.$ But this contradicts the fact that $\mathcal A$ and $\mathcal B$ are elementarily equivalent. Also, by Löwenheim's theorem, we could assume that $\mathcal A$ and $\mathcal B$ are countably infinite, so that they are even isomorphic.

Adding a unary function symbol $f$ isn't going to change anything. If we had a sentence $\psi$ in this expanded language with the property that $(A,f)\vDash\psi\iff|A|\text{ is even},$ then in particular this equivalence would hold for models in which $f$ is the identity function. Clearly, then, we could write a sentence in pure identity theory which does the same job as $\psi.$

As André Nicholas's answer shows, the second-order sentence $$\exists f\forall x[f(x)\ne x\wedge f(f(x))=x]$$ characterizes sets of even cardinality.

Answer 3

Evenness is fundamentally a property of finite structures; there are ways to extend it to infinite sets, but there are different incompatible ways to do so. For example, you could say that the support should be divided in two sets that are in bijection, or you could say that it is even if it cannot be divided into two sets in bijection and a singleton; both these definitions characterize finite even structures, but the first find infinite sets to be even but not the second.

If you restrict yourself to finite structures, you can't appeal to compactness or LS. You should use Ehrenfeucht–Fraïssé games. The idea is very similar to what you have already done. If 'even' can be expressed by a formula, this formula must have some quantifier depth $q$. Which means that Spoiler should win any $k$-round game, for $k\geq q$, on two structures where one is even and not the other. So to prove that it is not definable, you need to exhibit a family of pairs of structures $(M,M')_k$ that are equivalent for $k$-round games, yet $M$ is even and $M'$ is not.