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

An $L$-embedding $\pi :A\to B$ is an injective map preserving the interpretations of all constants and functions and preserving and reflecting every relation. Explicitly $\pi (c^A)=c^B$, $\pi (f^A(\bar{a}))=f^B(\pi \bar{a})$, and $A\models R(\bar{a})$ if and only if $B\models R(\pi \bar{a})$. Injectivity handles logical equality. Equivalently it is an isomorphism onto an $L$-substructure of $B$, or a map preserving the truth of all quantifier-free formulas. Preserving relations in only one direction would instead give a weaker homomorphism notion, not an embedding.

The relation $A\subseteq B$ means that the domain of $A$ is a subset of the domain of $B$ and the inclusion map is an $L$-embedding. Thus it contains all named constants, is closed under every named function, and uses the restrictions of the ambient relations.

The stronger relation $A\preccurlyeq B$ means that for every first-order formula $\varphi (\bar{x})$ and tuple $\bar{a}$ from $A$,This includes formulas with quantifiers ranging over the respective domains. Elementary inclusion implies ordinary substructure inclusion, but the latter need only preserve quantifier-free truth. In particular an existential witness available in $B$ need not lie in an arbitrary substructure.

The Tarski-Vaught test says that a substructure $A\subseteq B$ is elementary exactly when for every formula $\varphi (x,\bar{y})$ and tuple $\bar{a}\in A$, if $B\models \exists x\varphi (x,\bar{a})$, some $b\in A$ satisfies $B\models \varphi (b,\bar{a})$. Thus every existential assertion with parameters from $A$ that has a witness in $B$ already has a witness in $A$. The matrix may contain quantifiers; restricting it to quantifier-free formulas would not state the full test.

Finite satisfiability means that every finite subset $T_0\subseteq T$ has an $L$-structure satisfying all its sentences. Different finite subsets may have different witnessing structures. The first-order compactness theorem says this condition is equivalent to satisfiability of the entire set, but finite satisfiability itself is defined by the finite-subset condition.

Satisfiability means that there exists one nonempty-domain $L$-structure $M$ such that $M\models \varphi$ for every $\varphi \in T$. It is this single simultaneous model that is required. By the soundness and completeness theorems, satisfiability is equivalent to syntactic consistency in classical first-order logic.

Under the deductively closed convention, an $L$-theory is a set of $L$-sentences containing all its first-order logical consequences: if $T\models \varphi$, then $\varphi \in T$. By completeness this is equivalent to closure under provability. An axiom set is often called a theory too, with its deductive closure understood. Neither convention by itself requires completeness or satisfiability; an inconsistent deductively closed theory contains every sentence.

A complete satisfiable theory has a model and decides every $L$-sentence: for each $\sigma$, exactly one of $\sigma$ and $\neg \sigma$ is a consequence. Under the closed convention, exactly one belongs to $T$. Satisfiability excludes the possibility of both. Equivalently all models of the theory are elementarily equivalent, even though they need not be isomorphic or have equal cardinality.

The complete theory $\mathrm{Th}(A)$ is the set of all $L$-sentences true in $A$. The existential theory of a structure ${\mathrm{Th}}_{\exists }(A)$ consists of those true sentences of the form $\exists \bar{x}\theta (\bar{x})$ with quantifier-free $\theta$. The universal theory ${\mathrm{Th}}_{\forall }(A)$ uses $\forall \bar{x}\theta (\bar{x})$ with quantifier-free matrix. Allow equivalent formulas and empty quantifier blocks, or insert dummy variables in nonempty domains. These are sentences in the original language, distinct from diagrams, which add constants naming Elements of the structure.

If a model $B$ of $T$ contains $A$ as a substructure, every existential sentence true in $A$ remains true in $B$: use the same witness tuple and preservation of quantifier-free truth. Hence $B$ satisfies the required joint theory.

For the existential-theory embedding criterion, conversely suppose that joint theory has a model. Expand the language by a constant $c_a$ for each $a\in A$, and add the atomic and negated atomic diagram $D(A)$ to $T$. Any finite collection of its literals is a quantifier-free conjunction $\theta (\bar{c})$ true of the corresponding tuple in $A$. Replacing those named constants by variables and existentially closing gives a sentence in ${\mathrm{Th}}_{\exists }(A)$. A model of the assumed joint theory can supply its witnesses, and hence an expansion satisfying those finitely many diagram requirements and any finite subset of $T$.

Compactness therefore gives a model of $T+D(A)$. Its named Elements define an embedding of $A$ into its $L$-reduct: inequalities ensure injectivity, and all function and relation literals ensure preservation and reflection. Replace the ambient model by an isomorphic copy identifying this image with $A$ itself. Thus a model of $T$ containing $A$ exists. The diagram step explains how parameter-free existential information nevertheless yields an embedding of the whole structure.

If $B\models T$ and $B\subseteq A^{\ast }\equiv A$, every universal sentence of $A$ holds in $A^{\ast }$ and is preserved by passage to the substructure $B$. Thus $B$ witnesses satisfiability of the joint theory.

For universal theory and substructures of elementarily equivalent models, conversely let $B$ satisfy $T$ together with the universal theory of $A$. Every existential sentence true in $B$ must be true in $A$: if an existential $\sigma$ were false in $A$, its universal negation would belong to ${\mathrm{Th}}_{\forall }(A)$ and hold in $B$, a contradiction. Hence ${\mathrm{Th}}_{\exists }(B)\subseteq \mathrm{Th}(A)$. In particular $\mathrm{Th}(A)\cup {\mathrm{Th}}_{\exists }(B)$ is satisfiable, with model $A$. Apply the preceding embedding result to the theory $\mathrm{Th}(A)$ and structure $B$. It supplies a structure $A^{\ast }\models \mathrm{Th}(A)$ containing $B$. Therefore $A^{\ast }\equiv A$ and $B\subseteq A^{\ast }$, as required. Elementary equivalence here does not assert that $A$ itself contains a copy of $B$.

The natural-number successor chain embeds into the integer successor chain by ordinary inclusion. Thus $\mathbb{Z}$ witnesses the existential joint satisfiability in the first assertion. The two chains are not elementarily equivalent: every integer has a predecessor, whereas zero has none in the natural-number chain.

For the universal assertion, construct an elementary extension of the natural-number chain containing a two-sided successor chain. To its elementary diagram add distinct constants $d_j$ for $j\in \mathbb{Z}$ with $s(d_j)=d_{j+1}$ and require them to differ from all named natural numbers. Every finite subset is realized in the natural-number chain: place the finitely many required consecutive blocks sufficiently far to the right, away from the finitely many forbidden named Elements. Compactness yields an elementary extension $A^{\ast }$ with the required two-sided chain. That chain is a substructure isomorphic to the integer successor structure and hence is a model of its complete theory.

Consequently both joint theories in the two assertions are satisfiable, though the integer chain cannot embed into the natural-number chain itself: repeated predecessors would give an infinite descending sequence of natural numbers. The second assertion correctly uses an elementarily equivalent ambient structure rather than the original one.

Existential sentences are preserved under extensions: witnesses remain present and quantifier-free truth is unchanged by an embedding. Therefore any existential axiomatization implies the specified extension-closure property.

For existential axiomatization from extension closure, let $E$ be all existential consequences of $T$, and suppose $A\models E$. We claim that $T\cup {\mathrm{Th}}_{\forall }(A)$ is satisfiable. Otherwise compactness supplies finitely many universal sentences ${\theta }_1,\dots ,{\theta }_m$ true in $A$ such that $T\models \neg ({\theta }_1\wedge \cdots \wedge {\theta }_m)$. The finite conjunction is universal after renaming bound variables, so its negation is existential. It belongs to $E$ but is false in $A$, a contradiction.

The preceding universal-theory embedding result now yields $B\models T$ and $A^{\ast }\equiv A$ with $B\subseteq A^{\ast }$. By the assumed extension closure, $A^{\ast }\models T$; elementary equivalence implies $A\models T$. Thus $E$ axiomatizes exactly the models of $T$, proving existential axiomatizability is equivalent to closure under extensions. This includes the inconsistent case, whose empty model class is axiomatized by an existential contradiction.