Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 16F (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 implication follows by taking the same model. Conversely, if $T$ had no model, then by the Godel completeness theorem it would prove a contradiction. A formal proof uses only finitely many assumptions, so some finite subset of $T$ would already have no model. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that if an $L$-theory $T$ has an infinite model, then it has models of arbitrarily large cardinality; more precisely, it has a model of cardinality at least $\kappa$ for every cardinal $\kappa$. Add new constants $c_{\alpha }$ for $\alpha <\kappa$ and the sentencesEvery finite subset of the enlarged theory can be interpreted in the given infinite model, since it mentions only finitely many constants. Compactness supplies a model of the whole enlarged theory, in which the $c_{\alpha }$ are pairwise distinct. Its reduct to $L$ is a model of $T$ having at least $\kappa$ elements. If $\kappa \ge |L|+{\aleph }_0$, the Downward Lowenheim-Skolem theorem gives a model of cardinality exactly $\kappa$.

This class is not axiomatisable. Suppose that a theory $T$ axiomatized it. Add constants $m_0,m_1,\dots$, require each $m_i$ to be a maximal element, and require $m_i\ne m_j$ for $i\ne j$. Every finite part of this enlarged theory has a model: choose a finite partially ordered set with enough maximal elements. By the compactness theorem the whole theory has a model, but its reduct is a model of $T$ with infinitely many maximal elements, a contradiction. This is the compactness obstruction to axiomatizing finitely many maximal elements.

This class is axiomatisable when an uncountable set of constants is allowed. Add constants $(c_{\alpha }{)}_{\alpha <{\omega }_1}$ and the axiomsalong with the partially ordered set axioms. Every reduct of a model has at least ${\aleph }_1$ maximal elements. Conversely, in every poset with uncountably many maximal elements the constants can be interpreted as distinct maximal elements. Thus the expanded theory axiomatizes precisely the desired reducts.

This class is axiomatisable in the original language. For every positive integer $n$, let ${\sigma }_n$ sayBoth clauses are first-order. If one of the two sets is infinite, every ${\sigma }_n$ holds. Conversely, if both sets were finite, choosing $n$ larger than both cardinalities would make ${\sigma }_n$ false. Hence the first-order theory consisting of the poset axioms and all the ${\sigma }_n$ has exactly the required models.

This class is not axiomatisable. If $T$ axiomatized it, add constants $m_i$ and $n_i$ for $i\in \mathbb{N}$, requiring the $m_i$ to be distinct maximal elements and the $n_i$ to be distinct minimal elements. Every finite fragment has a model of $T$: make one of the two sets infinite and make the other finite but large enough to interpret the finitely many constants mentioned. Compactness would then give a model of $T$ having both infinitely many maximal and infinitely many minimal elements, contrary to the exclusive condition. This is the compactness obstruction to an exclusive disjunction of infinitude.

This class is not axiomatisable. It contains an infinite model, for example the total order $\mathbb{Q}$. If a theory $T$ in any fixed expanded language axiomatized it, choose a cardinalThe Upward Lowenheim-Skolem theorem would give a model of $T$ of cardinality at least $\kappa$. Its underlying order cannot be isomorphic to a subset of $\mathbb{R}$, because every such subset has cardinality at most $|\mathbb{R}|$. This contradiction proves the claim.