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

The compactness theorem states that a set of first-order sentences has a model if every finite subset has a model. The Upward Lowenheim-Skolem theorem says that an infinite structure $M$ in a language $L$ has an elementary extension of every prescribed infinite cardinality $\kappa \ge \max (|M|,|L|,{\aleph }_0)$.

Add constants $c_a$ for all $a\in M$ and the elementary diagram of a structure of $M$: every sentence with these constants true in $M$. Add $\kappa$ further constants $d_i$ and sentences $d_i\ne d_j$ for $i\ne j$. Any finite subset is satisfiable in $M$, by choosing the finitely many new constants distinctly, since $M$ is infinite. Compactness gives a model containing an elementary copy of $M$ and at least $\kappa$ elements.

For the exact cardinality, start with that copy and all the $d_i$, a set of cardinality $\kappa$. For every existential formula with parameters from this set that holds in the large model, choose one witness. Also close under the language's functions. Repeat countably many times. At each stage there are at most $\kappa$ formulas and finite parameter tuples, so the union still has cardinality $\kappa$. Every existential formula true in the large model with parameters in the union has a witness in the union; an induction on formulas proves that this substructure is elementary. This establishes the exact-size statement without assuming an unproved downward theorem.

A dense total order with $a<b$ is not a well-order: the nonempty set $\{x:a<x\}$ has no least element, since density supplies a point strictly between $a$ and any proposed least element.

In the strict-order language, the required axioms areThese axiomatize dense total orders, allowing endpoints. If more than one point is required, add $\exists x\exists y(x<y)$. For a non-strict poset language replace $x<y$ by $x\le y\wedge x\ne y$.

This class is not first-order axiomatisable. If a theory axiomatized the countable dense total orders, it would have $(\mathbb{Q},<)$ as an infinite model. By the Upward Lowenheim-Skolem theorem it would also have an uncountable model, contradicting the proposed restriction. The same argument applies whether countable means exactly countably infinite or at most countable.

This class is also not first-order axiomatisable. Suppose such a theory had an uncountable dense-order model $M$. Its language is finite. Starting with a countably infinite set of elements and repeatedly adjoining witnesses for all existential formulas with parameters already chosen yields a countable elementary substructure: there are only countably many formulas and parameter tuples at every stage. The induction-on-formulas argument from part (i) proves elementarity. The substructure satisfies every sentence of the theory, yet is countable, a contradiction. This is the witness construction underlying the Downward Lowenheim-Skolem theorem.

Well-orders are not first-order axiomatisable. Suppose a theory $T$ axiomatized them. Enlarge the language by constants $c_0,c_1,\dots$ and addEvery finite subset of the resulting theory has a model in the well-order $(\mathbb{N},<)$: assign its finitely many constrained constants to a sufficiently long finite descending chain. Thus the compactness theorem supplies a model of $T$ with an infinite descending chain. The set of the $c_i$ has no least element, contradicting well-ordering. This shows why the second-order assertion that every nonempty subset has a least member cannot be replaced by a first-order theory in the poset language.