Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2008 / B / 6

Let $L_A$ expand $L$ by a constant $c_a$ for each $a\in A$, and let ${\mathcal{A}}_A$ be the canonical expansion interpreting $c_a$ as $a$. Its diagram of a structure is the set of all atomic and negated atomic $L_A$-sentences true in ${\mathcal{A}}_A$. Its elementary diagram is the set of all $L_A$-sentences true there:A substructure inclusion $\mathcal{A}\subseteq \mathcal{B}$ means that $A\subseteq B$, constants have the same interpretations, the operations of $\mathcal{B}$ restrict to those of $\mathcal{A}$, and each relation restricts to the corresponding relation on $A$.

An elementary substructure additionally preserves the truth of every logical formula with parameters from $A$:Here the right-hand condition includes the substructure requirements by applying it to atomic logical formulas and their negations.

If $\mathcal{A}\subseteq \mathcal{B}$, interpret each new constant $c_a$ in $\mathcal{B}$ as the same element $a$. Atomic logical formulas and their negations then have exactly their truth values in ${\mathcal{A}}_A$, so the expansion satisfies the diagram of a structure. If the inclusion is elementary, every logical formula with those named parameters has the same truth value, so the expansion satisfies the elementary diagram.

Conversely, from any expansion ${\mathcal{B}}^{+}$ satisfying the diagram of a structure defineThe diagram of a structure contains $c_a\ne c_{a^{\prime }}$ whenever $a\ne a^{\prime }$, so $e$ is injective. It contains every true function-value equation, so $e$ commutes with all operations and constants. Positive and negative relation instances ensure both preservation and reflection of the relations. Thus $e$ is an embedding of first-order structures. If the expansion satisfies the elementary diagram, for every logical formula $\varphi$ and tuple $\vec{a}$ it also givesso $e$ is an elementary embedding of first-order structures.

The precise conclusion for an arbitrary expansion is an embedding of first-order structures, rather than a literal inclusion of the original carriers. The source's inclusion notation is correct when one uses the customary identification of $\mathcal{A}$ with its embedded copy, or requires the expansion to interpret $c_a$ as the actual element $a$ of a carrier already containing $A$. With that naming convention, $e$ is the inclusion and the requested two equivalences follow exactly.

Without the convention the literal wording fails, even in the first-order language of logical equality: singleton first-order structures with carriers $\{0\}$ and $\{1\}$ have a diagram-satisfying expansion by sending the first first-order structure's named point to $1$, but the first carrier is not a subset of the second. The embedding of first-order structures formulation proved above states the invariant result and makes the intended inclusion formulation precise.

The Downward Lowenheim-Skolem theorem says that for an $L$-structure $M$ and a subset $S\subseteq M$, there is an elementary substructure $N\preccurlyeq M$ containing $S$ withIf an infinite cardinal $\kappa$ satisfies $\max (|L|,{\aleph }_0)\le \kappa \le |M|$, one can in particular obtain size exactly $\kappa$ by starting with a subset of that size.

Choose a default element $a_0\in M$. For every logical formula $\exists x\varphi (x,\vec{y})$ choose a Skolem function $F_{\varphi }$ which returns a witness in $M$ when one exists, and returns $a_0$ otherwise. Begin with $S$, the interpretations of the first-order language's constants, and $a_0$. Successively adjoin the values of all the original functions and these Skolem functions on finite tuples already chosen. Let $N$ be the union of the resulting countable sequence of closure stages.

There are at most $\max (|L|,{\aleph }_0)$ logical formulas, and each function has finite arity. With $\kappa =\max (|S|,|L|,{\aleph }_0)$, each closure stage has size at most $\kappa$, and so does their countable union. Closure under the original functions makes $N$ an $L$-substructure. Whenever $M\models \exists x\varphi (x,\vec{a})$ for parameters in $N$, its chosen Skolem witness belongs to $N$, since the finitely many parameters lie in some common stage. The Tarski–Vaught test therefore gives $N\preccurlyeq M$.

For the exact-cardinality version, choose an initial set of $\kappa$ elements, enlarged to contain any prescribed subset of size at most $\kappa$. The construction gives an upper bound $\kappa$ while containment gives the matching lower bound.

Add a predicate symbol $P_{\theta }$ for each $L$-formula $\theta (\vec{x})$, of arity equal to its displayed free-variable tuple. Let $T^{+}$ consist of $T$ together with all defining axiomsEvery first-order model of $T$ has a unique such expansion, interpreting the new predicate symbols by their defining sets. Conversely the reduct of every first-order model of $T^{+}$ satisfies $T$.

Given an arbitrary $L^{+}$-formula $\psi (\vec{x})$, replace each new atomic predicate symbol by its original $L$-definition, renaming bound variables to avoid capture. This produces an $L$-formula ${\psi }^{-}(\vec{x})$ withThe defining axiom for that particular logical formula now gives an atomic replacement:Thus the expanded first-order theory eliminates quantifiers. For a first-order sentence, the same translation is an $L$-sentence, decided by completeness of $T$; hence every expanded first-order sentence is decided and $T^{+}$ is complete. Empty free-variable tuples can be handled by zero-ary predicate symbols, or by the usual logical truth and falsity constants. This definitional expansion is called Morleyization.