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

  • $\begingroup$ If you mean that $A$ and $B$ are elementarily equivalent, that is not necessarily the case. $\endgroup$ – André Nicolas Apr 4 '16 at 20:01
  • $\begingroup$ What would be an example of two structures both of infinite cardinality which weren't elementarily equivalent in a language with no non-logical symbols? $\endgroup$ – Rafa Apr 4 '16 at 20:13
  • $\begingroup$ With no non-logical symbols, there are no examples. You did not specify no non-logical symbols in your question, which is why I did not comment on your argument. $\endgroup$ – André Nicolas Apr 4 '16 at 20:16
  • $\begingroup$ Sorry, I forgot to specify that condition, which I have now added. In such a language would any two structures be elementarily equivalent? $\endgroup$ – Rafa Apr 4 '16 at 20:23
  • 1
    $\begingroup$ So what is the setup? We have equality and no more? Then indeed there is no sentence true in precisely finite sets of even cardinality, any sentence which is true in models of arbitrarily high finite cardinality is true in all finite structures of large enough cardinality. $\endgroup$ – André Nicolas Apr 4 '16 at 20:24

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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ So let $\psi$ be the sentence $(f(x)\neq x) \land (f(f(x)) = x)$. If a finite $ A\models \psi$, then $|A|$ is even. But the converse does not hold. So this is a relevant observation, but it doesn't answer the question. $\endgroup$ – Alex Kruckman Apr 4 '16 at 19:28
  • $\begingroup$ Your $\psi$ is not quite a sentence, but one can universally quantify. The observation can be used to answer the second part of the question. I did not answer the first part, since it is incompletely specified. $\endgroup$ – André Nicolas Apr 4 '16 at 19:34
  • $\begingroup$ There is already an answer by bof. Note that even though the (first-order) sentence $\varphi$ of my answer has the property that a model is finite if and only if it is even, there are finite even structures in which $\varphi$ is false. $\endgroup$ – André Nicolas Apr 4 '16 at 23:27

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.