Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 16H (Logic and Set Theory)

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One direction is immediate: a model of $T$ models every subset. Conversely, suppose every finite subset is satisfiable. If $T$ had no model, then $T\models \perp$. The Godel completeness theorem would give a formal proof $T⊢\perp$. Every proof is finite, so it would use only a finite subset $T_0\subseteq T$, making $T_0$ inconsistent and hence unsatisfiable. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has models of arbitrarily large cardinality. Fix a cardinal $\kappa$ and expand the language by constants $c_{\alpha }$ for $\alpha <\kappa$. Add the sentencesto $T$. Any finite subset mentions only finitely many new constants, which can be interpreted as distinct elements of the given infinite model. Compactness therefore gives a model of the expanded theory in which the $c_{\alpha }$ are all distinct. Its reduct is a model of $T$ of cardinality at least $\kappa$. Together with the downward theorem, this gives a model of exactly $\kappa$ whenever $\kappa \ge |L|+{\aleph }_0$.

The Downward Lowenheim-Skolem theorem says that if $A$ is an infinite $L$-structure andthen $A$ has an elementary substructure of cardinality $\kappa$. To see why, first choose $\kappa$ elements. For every existential formula, add a Skolem function selecting a witness whenever one exists, and repeatedly close the chosen set under all language operations and these witness functions. There are at most $\kappa$ functions of finite arity, so the closure still has size $\kappa$. Every existential statement true in $A$ with parameters from the closure has a witness in the closure; the Tarski--Vaught test therefore says that the resulting substructure is elementary.

Expand $L$ by a unary function symbol $f$. Let $T^{\ast }$ contain:

Every finite subset $S\subseteq T^{\ast }$ contains only finitely many size requirements, say no requirement beyond ${\theta }_N$. By hypothesis there is a finite nonrigid model $A\models T$ with at least $N$ elements. Interpret $f$ as a nonidentity automorphism of $A$. This expanded structure satisfies $S$; indeed it satisfies every automorphism axiom, including any finitely many that occur in $S$.

Thus every finite subset of $T^{\ast }$ is satisfiable. By the compactness theorem, $T^{\ast }$ has a model $M^{\ast }$. The sentences ${\theta }_n$ make its domain infinite, while $\exists x[f(x)\ne x]$ and the automorphism axioms make $f^{M^{\ast }}$ a nonidentity automorphism. The $L$-reduct $M$ is therefore an infinite nonrigid model of $T$. This is the compactness transfer of finite nonrigidity.

No. Take $L=\{<\}$ and let $T$ be the theory of linear orders. It has finite models of every positive size. Every finite linear order is a rigid first-order structure: an order automorphism fixes the least element, then the next element, and inductively every element.

However, $(\mathbb{Z},<)$ is an infinite model of $T$ and is not rigid. For example,is a nonidentity order automorphism. Hence arbitrarily large rigid finite models do not force all infinite models to be rigid.