Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 16G (Logic and Set Theory)

The compactness theorem for first-order logic says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. The forward implication is immediate. Conversely, if every finite subset is satisfiable, then $T$ is syntactically consistent: any proof of a contradiction would use only finitely many premises. The Godel completeness theorem then gives a model of $T$.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has arbitrarily large models. Given an infinite model of $T$ and any cardinal $\kappa$, enlarge the language by constants $c_{\alpha }$ for $\alpha <\kappa$ and addEvery finite subset can interpret its finitely many constants as distinct elements of the original infinite model. By the compactness theorem, the enlarged theory has a model containing at least $\kappa$ distinct elements; its reduct is a model of $T$.

Finally, suppose a set $S$ and a finite set $T$ axiomatize the same class. Let $\tau$ be the conjunction of the sentences in $T$. Since $S\models \tau$, the set $S\cup \{\neg \tau \}$ is unsatisfiable. Compactness gives a finite $S_0\subseteq S$ such that $S_0\models \tau$. Because $\tau \models S$, we also have $S_0\models S$, while $S\models S_0$ is immediate. Therefore yes: the finite subset $S_0$ axiomatizes the same theory. This is finite subaxiomatization from an equivalent finite theory.

The class of finite groups is not first-order axiomatizable. If $S$ axiomatized it, add constants $c_1,c_2,\dots$ and all inequalities $c_i\ne c_j$. Every finite fragment has a sufficiently large finite cyclic group as a model. The compactness theorem would then give an infinite group satisfying $S$, contradicting the definition of the class. This is the group instance of the fact that finite structures are not first-order axiomatizable.

This class is the class of torsion-free groups and is axiomatizable. Take the group axioms and, for every integer $n\ge 2$, the sentenceThese sentences exclude every nonidentity element of finite order and give the first-order axiomatization of torsion-free groups.

The class is axiomatizable by the partial order axioms together with totality:Explicitly, the remaining axioms state reflexivity, antisymmetry, and transitivity. This is the first-order axiomatization of total orders.

The class of well-orderings is not first-order axiomatizable. If $S$ axiomatized it, add constants $c_0,c_1,\dots$ and sentencesEvery finite subset has a finite well-order containing the required finite descending chain. By the compactness theorem, the whole set has a model; that model satisfies $S$ but contains an infinite descending chain, so it is not a well-order. This contradiction proves the claim, as summarized by well-orders are not first-order axiomatizable.