4

In the book `elements of finite model theory' by Libkin. They prove that the parity query is not first order definable on finite structures over empty signatures by using the compactness theorem.

They do so as follows: let $\lambda_n$ by the sentence that is true if and only if the universe has at least $n$ elements. Furthermore, assume for the sake of contradiction that $\varphi$ expresses the parity query.

Now let $A = \{\varphi\} \cup \{\lambda_n \mid n \in \mathbb{N}\}$ and $B = \{\neg\varphi\} \cup \{\lambda_n \mid n \in \mathbb{N}\}$. Clearly every finite subset of $A$ and $B$ have a model, so by the compactness theorem $A$ and $B$ have models, which clearly have to be infinite.

If we now apply the Löwenheim–Skolem theorem, we can assume that there exists countable models $\mathcal{A}$ and $\mathcal{B}$ such that $\mathcal{A} \models A$ and $\mathcal{B} \models {B}$. However, since the signature is empty, $\mathcal{A}$ and $\mathcal{B}$ are just countable sets, and hence are isomorphic. This however contradicts the fact that $\mathcal{A} \models \varphi$ and $\mathcal{B} \models \neg\varphi$, and hence the parity query is not first order definable.

Now my question: how does this prove that the parity query is not expressible on finite structures, since the proof establishes a contradiction using infinite models. Is it because the parity query only makes sense on finite models?

user88120
  • 43

1 Answers1

0

The point is that the proof does establish a contradiction from the assumption that the cardinality of the universe is even is first-order definable: it shows that this assumption implies the existence of two models that are isomorphic but not elementarily equivalent, which is absurd. Any contradiction would do; in principle it could just as well have been that $\sqrt2$ is rational, say. The fact that the contradictory models are infinite is beside the point.

Brian M. Scott
  • 616,228
  • Ok, then it follows from the assumption and that parity only makes sense for finite structures? Since, take for example graph connectivity, if you use the standard compactness proof, you show that graph connectivity is not first-order definable, but that does not rule out the possibility that it could be first-order definable on finite structures only. Or is my reasoning flawed here? – user88120 Jul 29 '13 at 12:29
  • @user88120: The contradiction follows simply from the assumption that there is a first-order sentence $\varphi$ such that a finite model $\mathfrak{A}\vDash\varphi$ iff $|\mathfrak{A}|$ is even. It doesn’t matter what infinite models satisfy $\varphi$, if any. – Brian M. Scott Jul 29 '13 at 12:32
  • Ok, thank you very much! – user88120 Jul 29 '13 at 12:33
  • @user88120: You’re very welcome. – Brian M. Scott Jul 29 '13 at 12:34