If every finite subset of a theory has an infinite model then the theory has an infinite model

466 Views Asked by At

Consider the famous compactness theorem, one of the first theorems in model theory: Let $T$ be a theory, i.e., a set of first-order sentences. If every finite subset of $T$ has a model, then the whole set $T$ itself has a model.

It is well-known that this theorem fails if one just considers finite models. I asked myself the question? Is it true if one just considers infinite models? That is, if every finite subset of $T$ has an infinite model, does $T$ have an infinite model?

I think one can deduce this by applying the compactness theorem to an extended theory $T$ in an extended signature. Let $\tau$ be the signature of $T$. We can get a new signature $\tau' := \tau\sqcup\{s, 0\}$ by adding a unary function symbol $s$ and a constant symbol $0$ to $\tau$. Now consider the theory $T'$ over $\tau'$ defined by: $$T' := T\cup\{\quad\forall x(s(x)\not=0)\,\land\, \forall x, y (s(x) = s(y)\Rightarrow x = y)\quad\}.$$ Let $F'$ be an arbitrary finite subset of $T'$. $F'$ induces a finite subset $F$ of $T$ by deleting $\forall x(s(x)\not=0)\,\land\, \forall x, y (s(x) = s(y)\Rightarrow x = y)$ if it happens to be in $F'$ (otherwise $F=F'$). By assumption, $F$ has an infinite model $\mathcal A$. Since $\mathcal A$ is infinite, this model can be transformed into a model of $F'$ by choosing $0\in A$ and $s\colon A\to A$ such that $\mathcal A\models \forall x(s(x)\not=0)\,\land\, \forall x, y (s(x) = s(y)\Rightarrow x = y)$. By compactness, $T'$ has a model, which must be infinite. Thus also $T$ has an infinite model.

First question: is my proof correct? Is there a simpler proof?

Second question: in my proof, I use the compacntess theorem as a blackbox. But maybe it's possible to directly construct an infinite model of $T$. Using the standard ultraproduct argument, this would be trivially possible if the ultraproduct of infinite structures is infinite (no matter which ultrafilter we choose). Is this true?

1

There are 1 best solutions below

3
On BEST ANSWER
  1. Yes, your proof is correct.
  2. Yes, ultraproduct of infinite models is infinite: consider the formulas $$\exists x_1\dots\exists x_n:\bigwedge_{i\ne j} \lnot(x_i=x_j) $$