Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 3 / 16H / Solution

A first-order structure consists of a nonempty domain, an interpretation of each constant as a domain element, each $k$-ary function symbol as a map from the $k$-fold domain product to the domain, and each $k$-ary relation symbol as a subset of that product. Under an assignment of values to variables, terms are evaluated recursively. Atomic formulas assert equality of term values or membership in an interpreted relation. Boolean connectives act on truth values, and quantifiers range over the whole domain. The set $[[\phi ]{]}_A$ consists of assignments to the free variables making the formula true.

For a substructure $B\subseteq A$, constants lie in $B$, functions restrict to $B$, and relations restrict to tuples from $B$. Induction on terms shows that every term with arguments from $B$ has the same value in both structures. Atomic formulas consequently have the same truth values, and induction on Boolean connectives givesfor every quantifier-free formula.

For a nonempty chain of $T$-model substructures, form their union $U$. Every finite tuple belongs to one member of the chain, so $U$ is closed under all interpreted functions and contains the constants. Consider any inductive axiom $\forall x\exists y\psi (x,y)$. A specified finite tuple $x$ lies in one member, which supplies witnesses $y$ there. The quantifier-free formula $\psi$ has the same truth value in that member and $U$, so $U$ satisfies the axiom. Hence $U$ is a $T$-model and the least upper bound of the chain. The poset is complete for nonempty chains. If chain-complete is defined to include the empty chain, a least element must additionally exist, which the stated hypotheses do not ensure.