Why does the compactness theorem not apply to infinite languages?

115 Views Asked by At

I am trying to show that compactness doesn't apply to infinite languages like $L_{\omega_1,\omega}$ that allow infinite FOL sentences like $\forall x\, \bigvee_{n\in \omega} x \approx S^n(0)$, i.e. $\forall x\, (x \approx 0 \vee x \approx S(0) \vee x\approx S(S(0)) \dots)$.

I already picked a language $L=(0,S)$, gave an example of a set of sentences which is satisfiable, since every subset $\Gamma_m$ of $\Gamma_n\colon x\approx 0 \vee \dots \vee s\approx S^n(0)$, has a finite model for every $m$ smaller than $n$.

I am trying to show that nonetheless $\Gamma_n$ has no model. I can't get my head around how to perform this last step. Maybe my example of a set of sentences $\Gamma_n$ which is supposed to be finitely satisfiable but not satisfiable is not the right one?

1

There are 1 best solutions below

0
On

Actually, you don't need any signature: $L=\{=\}$ is completely fine. Note that you can express the property for any $n\in \mathbb{N}$ that the model contains at least $n$ different elements. In fact, there is a finite first-order formula that expresses this. Let $\phi_n$ be such a formula.

(E.g., $\phi_3$ is $\exists x_1,x_2,x_3 \,\, x_1\neq x_2 \wedge x_2\neq x_3 \wedge x_1\neq x_3$.)

The theory $T$ now consists of

$\bullet$ all the $\phi_n$,

$\bullet$ and the formula that says that one of the $\phi_n$ must be false (this is an infinite disjunction of all the negations of the $\phi_n$)

Altogether, this means that the model is infinite and finite (contradiction).

But any finite subsystem is satisfiable (by some finite set).