42.02.01 · mathematical-logic / model-theory

Structures, Embeddings, and Elementary Equivalence

shipped3 tiersLean: none

Anchor (Master): Marker 2002 *Model Theory: An Introduction* (Springer GTM 217) Ch. 1-2 (structures, embeddings, elementary maps, the Tarski-Vaught test, elementary chains, the method of diagrams, downward Löwenheim-Skolem); Chang and Keisler 1990 *Model Theory* 3e (North-Holland) Ch. 1-3 (the systematic theory of elementary equivalence, elementary extensions, and chains); Hodges 1993 *Model Theory* (Cambridge) Ch. 2-3 (homomorphisms and the preservation hierarchy, back-and-forth systems, Ehrenfeucht-Fraïssé games and the Fraïssé characterisation of ≡); Tarski and Vaught 1957 *Arithmetical extensions of relational systems* (Compositio Math. 13)

Intuition Beginner

The previous unit fixed what it means for a sentence to be true in a world — a structure — and gave a precise rule for checking it. Model theory begins the moment you stop looking at one world at a time and start comparing worlds. Two questions drive everything: when does one world sit inside another, and when can no logical statement tell two worlds apart?

The first question is about fitting in. The whole numbers $0, 1, 2, \dots$ sit inside the integers, which sit inside the fractions. Each smaller world is a faithful copy of part of the larger one: the same objects, the same addition, the same order. A map that plants one world inside another without distorting any of its symbols is an embedding. When the smaller world is literally a piece of the larger one, it is a substructure.

The second question is subtler and more surprising. Sometimes two worlds are not copies of each other at all — one might be small and the other huge — yet no statement you can write down distinguishes them. The ordered fractions and the ordered real numbers are like this: any finite check you perform comes out the same in both. We say such worlds are elementarily equivalent. They agree on every statement first-order logic can phrase, even though they are not the same size. Learning to build worlds inside worlds, and to detect when worlds are logically indistinguishable, is the whole toolkit this unit assembles. The rest of model theory deploys it.

Visual Beginner

Three worlds nested inside one another, and a separate picture of two worlds that no statement can separate. Read the left column as "sits inside"; read the right column as "looks the same to logic."

   SUBSTRUCTURES (each world sits inside the next):

      whole numbers   { 0, 1, 2, 3, ... }
            |  sits inside (same +, same order)
            v
      integers        { ..., -2, -1, 0, 1, 2, ... }
            |  sits inside
            v
      fractions       { ..., 1/2, 3/4, -5/7, ... }

   Each smaller world is a faithful copy of part of the larger one:
   same objects where they overlap, same readings of every symbol.

   ELEMENTARILY EQUIVALENT (no statement tells them apart):

      ordered fractions   <-- agree on every -->   ordered reals
         (countable)         logical statement       (uncountable)

      different sizes, yet every first-order check
      comes out the same in both

The left picture shows nesting: a smaller world is carried, undistorted, into a bigger one. The right picture shows something different — two worlds of different sizes that nonetheless answer every logical question identically.

relationship	what it means	example
substructure	one world is a piece of another	whole numbers inside integers
embedding	a faithful copy planted inside	integers planted inside fractions
elementarily equivalent	no statement separates them	ordered fractions and ordered reals
isomorphic	the same world relabelled	two five-bead ordered chains

Nesting and indistinguishability are different ideas. Two worlds can be indistinguishable without one sitting inside the other, and one world can sit inside another while still being distinguishable from it.

Worked example Beginner

We compare two ordered worlds and decide, by hand, whether one sits inside the other and whether a statement separates them. World one: the whole numbers $0, 1, 2, 3, \dots$ with their usual order. World two: the integers $\dots, - 2, - 1, 0, 1, 2, \dots$ with their usual order. The only symbol is "less than."

Step 1. Does world one sit inside world two? Every whole number is an integer, and the order among whole numbers is the same order they have as integers: $2 < 5$ holds in both. So the whole numbers form a piece of the integers — a substructure. The planting map sends each whole number to itself.

Step 2. Now look for a statement that is true in one world but false in the other. Consider "there is a smallest object." In the whole numbers this is true: $0$ is below everything else. In the integers it is false: given any integer, a smaller one exists.

Step 3. So the two worlds disagree on the statement "there is a smallest object." They are not elementarily equivalent. One sits inside the other, yet a statement still separates them.

Step 4. Contrast with the fractions and the reals, both ordered. Take any property you can phrase with "less than," "and," "or," "not," "there exists," and "for all." Whatever you ask — is the order dense? does it have endpoints? — the fractions and the reals answer the same way. No statement separates them, so they are elementarily equivalent, even though the reals are far larger.

What this tells us: sitting inside and being indistinguishable are independent. The whole numbers sit inside the integers but a statement separates them; the fractions and reals do not nest one inside the other, yet no statement separates them. The strong notion that combines both — a piece that is also indistinguishable from the whole — is what the later sections call an elementary substructure.

Check your understanding Beginner

Exercise (easy, multiple choice).

The whole numbers $0, 1, 2, \dots$ sit inside the integers as a substructure (same order). Which statement is true in the whole numbers but false in the integers, showing the two are not indistinguishable?

A. "for every object there is a larger object"

B. "there is a smallest object"

C. "the order is the usual less-than"

D. "every object equals itself"

Hint

Look for a feature the whole numbers have at their bottom end that the integers, stretching down forever, do not.

Answer

B. "there is a smallest object." In the whole numbers $0$ is below everything; in the integers no object is smallest. Feedback-correct: a single statement separating two worlds shows they are not elementarily equivalent, even when one sits inside the other. Feedback-wrong: A is true in both, and C and D are true in both, so none of those separate the worlds.

Formal definition Intermediate+

Fix a first-order language $L$ and recall the satisfaction relation $M ⊨ φ [\overset{a}{ˉ}]$ from 42.01.04 pending. Let $M, N$ be $L$ -structures with universes $M, N$ .

An $L$ -homomorphism $h : M \to N$ is a map $h : M \to N$ with $h (c^{M}) = c^{N}$ for each constant, $h (f^{M} (\overset{a}{ˉ})) = f^{N} (h \overset{a}{ˉ})$ for each function symbol, and $\overset{a}{ˉ} \in R^{M} \Rightarrow h \overset{a}{ˉ} \in R^{N}$ for each relation symbol. An embedding is an injective $h$ for which the relation clause holds in both directions: $\overset{a}{ˉ} \in R^{M} \Leftrightarrow h \overset{a}{ˉ} \in R^{N}$ . An isomorphism is a surjective embedding. When $M \subseteq N$ , the constants and functions of $N$ restrict to $M$ , and the relations of $M$ are the restrictions $R^{N} \cap M^{n}$ , we say $M$ is a substructure of $N$ and $N$ an extension, written $M \subseteq N$ ; equivalently $M$ is a subset of $N$ containing every $c^{N}$ and closed under every $f^{N}$ , carrying the induced relations ^{[Marker §1.1]}.

An embedding $h : M \to N$ is elementary when $$ \mathfrak{M} \models \varphi[\bar a] \quad\Longleftrightarrow\quad \mathfrak{N} \models \varphi[h\bar a] $$ for every $L$ -formula $φ$ and tuple $\overset{a}{ˉ}$ from $M$ . When $M \subseteq N$ and the inclusion is elementary, $M$ is an elementary substructure and $N$ an elementary extension, written $M ⪯ N$ ^{[Marker §1.1]}. The complete theory of $M$ is $Th (M) = {σ : σ an L -sentence, M ⊨ σ}$ . Two structures are elementarily equivalent, $M \equiv N$ , when $Th (M) = Th (N)$ — they satisfy the same sentences. Taking $\overset{a}{ˉ}$ empty in the elementary condition shows $M ⪯ N \Rightarrow M \equiv N$ , and isomorphisms are elementary 42.01.04 pending, so $M ≅ N \Rightarrow M \equiv N$ .

The method of diagrams packages embeddings as models. Expand $L$ to $L_{M}$ by adding a fresh constant $c_{a}$ for each $a \in M$ . The atomic diagram $Diag (M)$ is the set of atomic and negated-atomic $L_{M}$ -sentences true in $M$ (under $c_{a} \mapsto a$ ); the elementary diagram $Diag_{el} (M)$ is the set of all $L_{M}$ -sentences true in $M$ . An $L_{M}$ -structure models $Diag (M)$ iff its $L$ -reduct receives an embedding of $M$ , and models $Diag_{el} (M)$ iff it receives an elementary embedding — the engine of the compactness constructions of 42.02.02 pending.

Counterexamples to common slips Intermediate+

"A substructure of $N$ is an elementary substructure." The whole numbers $(N; <)$ are a substructure of $(Z; <)$ , but $(N; <) \neq \equiv (Z; <)$ : only the former satisfies "there is a least element." Substructure-hood is about closure under the symbols; elementarity is the far stronger demand that all formulas, including quantified ones, be preserved.
" $\equiv$ is the same as $≅$ ." The orders $(Q; <)$ and $(R; <)$ are elementarily equivalent (both are dense linear orders without endpoints, a complete theory) yet not isomorphic, since one is countable and the other is not. First-order logic cannot see this cardinality gap. The non-standard models of arithmetic 42.01.04 pending are the other canonical witnesses: elementarily equivalent to $(N; +, \cdot)$ , never isomorphic to it.
"An embedding preserves all formulas." A bare embedding preserves only quantifier-free formulas. The inclusion $(N; <) ↪ (Z; <)$ is an embedding but reverses the truth of " $\exists y (y < x)$ " at $x = 0$ . Preservation of quantified formulas is exactly the surplus content of elementary embedding.

Key theorem with proof Intermediate+

The signature theorem of this unit is the Tarski-Vaught test: a usable, formula-by-formula criterion deciding when a substructure is elementary, replacing the unbounded quantifier-over-all-formulas in the definition by a single existential-witness condition. It is the lever behind the construction of every elementary substructure, including the downward Löwenheim-Skolem theorem.

Theorem (Tarski-Vaught test). Let $M \subseteq N$ be $L$ -structures. Then $M ⪯ N$ if and only if for every $L$ -formula $φ (x, \overset{y}{ˉ})$ and every tuple $\overset{ˉ}{b}$ from $M$ , whenever $N ⊨ \exists x φ (x, \overset{ˉ}{b})$ there is some $a \in M$ with $N ⊨ φ (a, \overset{ˉ}{b})$ ^{[Tarski and Vaught 1957]}.

Proof. ( $\Rightarrow$ ) Suppose $M ⪯ N$ and $N ⊨ \exists x φ (x, \overset{ˉ}{b})$ with $\overset{ˉ}{b}$ from $M$ . By elementarity applied to the sentence-with-parameters $\exists x φ (x, \overset{y}{ˉ})$ , $M ⊨ \exists x φ (x, \overset{ˉ}{b})$ , so there is $a \in M$ with $M ⊨ φ (a, \overset{ˉ}{b})$ ; elementarity again, now for $φ$ , gives $N ⊨ φ (a, \overset{ˉ}{b})$ . The witness $a$ lies in $M$ , as required.

( $\Leftarrow$ ) Assume the witness condition. We prove $M ⊨ ψ [\overset{a}{ˉ}] \Leftrightarrow N ⊨ ψ [\overset{a}{ˉ}]$ for all $ψ$ and tuples $\overset{a}{ˉ}$ from $M$ , by induction on $ψ$ . For atomic $ψ$ the equivalence holds because $M \subseteq N$ is a substructure: term values agree and the induced relations match. The connective cases $\neg$ and $\to$ are immediate from the inductive hypothesis. The case that uses the hypothesis is $ψ = \exists x φ (x, \overset{a}{ˉ})$ . If $M ⊨ \exists x φ (x, \overset{a}{ˉ})$ , a witness $a^{'} \in M$ gives $M ⊨ φ (a^{'}, \overset{a}{ˉ})$ , so $N ⊨ φ (a^{'}, \overset{a}{ˉ})$ by the inductive hypothesis, hence $N ⊨ \exists x φ (x, \overset{a}{ˉ})$ . Conversely if $N ⊨ \exists x φ (x, \overset{a}{ˉ})$ , the witness condition supplies $a^{'} \in M$ with $N ⊨ φ (a^{'}, \overset{a}{ˉ})$ , and the inductive hypothesis gives $M ⊨ φ (a^{'}, \overset{a}{ˉ})$ , so $M ⊨ \exists x φ (x, \overset{a}{ˉ})$ . Universal quantifiers are handled through $\forall x = \neg\exists x \neg$ , already covered. Thus the inclusion is elementary. $□$

Corollary (downward Löwenheim-Skolem). If $∣ L ∣ \leq κ$ , $κ$ is infinite, $N$ is an $L$ -structure, and $A \subseteq N$ with $∣ A ∣ \leq κ$ , then there is $M ⪯ N$ with $A \subseteq M$ and $∣ M ∣ \leq κ$ . Build $M$ as a Skolem hull: starting from $A$ , repeatedly adjoin, for each formula $φ (x, \overset{ˉ}{b})$ with parameters $\overset{ˉ}{b}$ already in hand that $N$ satisfies existentially, one witness $a \in N$ . Each round adds at most $κ$ elements and there are $\leq κ$ formulas, so the union $M$ has size $\leq κ$ , is closed under the witness condition, and is closed under functions; the Tarski-Vaught test then gives $M ⪯ N$ ^{[Marker §2.3]}. In particular every infinite structure in a countable language has a countable elementary substructure — the model-theoretic reading of the theorem, drawing on the compactness/Löwenheim-Skolem machinery of 42.01.07 pending.

Bridge. The Tarski-Vaught test is the foundational reason elementary substructure, defined by an unbounded condition over all formulas, is decided by a single existential-witness chase, and this is exactly the engine of the Skolem-hull construction. It builds toward the elementary-chain theorem below, whose proof reuses the existential-witness step stage by stage, and it appears again in the method of diagrams of 42.02.02 pending, where compactness builds elementary extensions by realising $Diag_{el} (M)$ . The argument generalises the coincidence-and-isomorphism preservation of 42.01.04 pending from full structure maps to the partial setting of a substructure inclusion: an isomorphism preserves everything because it is onto, and the witness condition is precisely the surjectivity-surrogate that recovers elementarity for an inclusion that is not onto. The central insight is that elementarity is a closure property — closed under existential witnesses — not a global comparison, and putting these together, the same witness chase yields downward Löwenheim-Skolem, the elementary chain theorem, and the diagram constructions that carry the rest of model theory.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Use the Tarski-Vaught test to show that $(Q; <)$ is an elementary substructure of the dense linear order $(Q \cup {r}; <)$ obtained by adjoining a single irrational $r$ between the rationals. Identify the one formula schema you must check.

Hint

You must show: any element of the larger order that satisfies $\exists x φ (x, \overset{ˉ}{b})$ over rational parameters $\overset{ˉ}{b}$ already has a witness in $Q$ . Quantifier elimination for dense linear orders reduces $φ$ to a quantifier-free condition.

Answer

The theory of dense linear orders without endpoints eliminates quantifiers, so any $φ (x, \overset{ˉ}{b})$ is equivalent to a quantifier-free condition: a Boolean combination of $x < b_{i}$ , $x = b_{i}$ , $b_{i} < x$ . If $\exists x φ (x, \overset{ˉ}{b})$ holds in the larger order with $\overset{ˉ}{b}$ rational, the satisfying $x$ lies in some open interval determined by rationals (or equals a rational $b_{i}$ ); by density of $Q$ that interval already contains a rational witness. So the witness condition holds for every $φ$ , and the Tarski-Vaught test gives $(Q; <) ⪯ (Q \cup {r}; <)$ . The schema to check is exactly $\exists x φ (x, \overset{ˉ}{b})$ for quantifier-free $φ$ . Rubric: full credit for the reduction to a quantifier-free interval condition and the density argument supplying the rational witness.

Exercise 4 (medium, symbolic).

Prove the back-and-forth step for dense linear orders: given a partial isomorphism $p$ between finite subsets of two dense linear orders without endpoints $M, N$ , and any new element $a \in M$ , show $p$ extends to a partial isomorphism with $a$ in its domain.

Hint

$a$ falls into one of finitely many gaps cut out by the current domain. Match it to an element of $N$ in the corresponding gap, using density and no-endpoints to guarantee one exists.

Answer

Let $p$ have domain ${m_{1} < \dots < m_{k}}$ and range ${n_{1} < \dots < n_{k}}$ with $p (m_{i}) = n_{i}$ (order-preserving). The new element $a$ satisfies exactly one of: $a < m_{1}$ ; $m_{i} < a < m_{i + 1}$ for a unique $i$ ; or $m_{k} < a$ . In the middle case, density of $N$ supplies $b$ with $n_{i} < b < n_{i + 1}$ ; in the end cases, no-endpoints supplies $b < n_{1}$ respectively $b > n_{k}$ . Set $p^{'} (a) = b$ . Then $p^{'} = p \cup {(a, b)}$ is order-preserving on its domain, hence a partial isomorphism extending $p$ with $a$ in its domain. Rubric: full credit for the gap analysis and the explicit use of density and no-endpoints to produce $b$ .

Exercise 5 (medium, symbolic).

Show that elementary equivalence is preserved under isomorphism but not conversely, by exhibiting structures $A \equiv B$ with $A \neq ≅ B$ , and explaining why $A ≅ B \Rightarrow A \equiv B$ .

Hint

Isomorphisms preserve all formulas (the isomorphism theorem of 42.01.04 pending). For the failure of the converse, compare two dense linear orders of different cardinalities.

Answer

An isomorphism $h : A \to B$ satisfies $A ⊨ σ \Leftrightarrow B ⊨ σ$ for every sentence by the isomorphism theorem, so $A \equiv B$ . For the converse failure take $A = (Q; <)$ and $B = (R; <)$ : both are dense linear orders without endpoints, whose complete theory decides every sentence, so $A \equiv B$ ; but $∣ Q ∣ = ℵ_{0} \neq = 2^{ℵ_{0}} = ∣ R ∣$ , so no bijection exists and $A \neq ≅ B$ . Rubric: full credit for the isomorphism-preserves-sentences direction and a correct elementarily-equivalent non-isomorphic pair.

Exercise 6 (medium, symbolic).

State the elementary diagram criterion: show that $N$ , expanded by naming the elements of $M$ , models $Diag_{el} (M)$ if and only if there is an elementary embedding $M \to N$ .

Hint

An interpretation of the constants $c_{a}$ is the same data as a map $M \to N$ ; modelling each sentence of $Diag_{el} (M)$ is the same as that map preserving every formula.

Answer

A model of $Diag_{el} (M)$ is an $L_{M}$ -structure $N^{*}$ ; the interpretations $c_{a}^{N^{*}}$ define a map $h : M \to N$ , $h (a) = c_{a}^{N^{*}}$ . For each $L$ -formula $φ$ and tuple $\overset{a}{ˉ}$ from $M$ , the sentence $φ (c_{\overset{a}{ˉ}})$ lies in $Diag_{el} (M)$ iff $M ⊨ φ [\overset{a}{ˉ}]$ , and $N^{*} ⊨ φ (c_{\overset{a}{ˉ}})$ iff $N ⊨ φ [h \overset{a}{ˉ}]$ . So $N^{*} ⊨ Diag_{el} (M)$ iff $M ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow N ⊨ φ [h \overset{a}{ˉ}]$ for all $φ, \overset{a}{ˉ}$ , which is exactly $h$ being an elementary embedding (injectivity comes from preserving $x \neq = y$ ). Rubric: full credit for identifying the constant interpretations with the map and matching membership in $Diag_{el}$ to the elementary condition.

Exercise 7 (hard, symbolic).

Prove Cantor's theorem in full: any two countable dense linear orders without endpoints are isomorphic. Use the back-and-forth construction.

Hint

Enumerate both universes. Build a chain of finite partial isomorphisms, alternately ensuring the next element of $M$ enters the domain (forth) and the next element of $N$ enters the range (back), using Exercise 4 at each step. The union is the isomorphism.

Answer

Let $M = {m_{0}, m_{1}, \dots}$ and $N = {n_{0}, n_{1}, \dots}$ enumerate the two countable orders. Build finite partial isomorphisms $p_{0} \subseteq p_{1} \subseteq \dots$ with $p_{0} = \emptyset$ . At an even stage $2 k + 1$ (forth) ensure $m_{k} \in dom (p_{2 k + 1})$ : if $m_{k}$ is already in the domain do nothing, else extend by the gap argument of Exercise 4. At an odd stage $2 k + 2$ (back) ensure $n_{k} \in ran (p_{2 k + 2})$ symmetrically, using density and no-endpoints in $M$ to place a preimage. Each $p_{j}$ is order-preserving and finite. Let $h = ⋃_{j} p_{j}$ . The forth stages guarantee $dom (h) = M$ , the back stages guarantee $ran (h) = N$ , and $h$ is order-preserving as a union of an increasing chain of order-preserving maps, hence injective; surjectivity onto $N$ makes it a bijection. An order isomorphism between linear orders preserves $<$ , $=$ , and their negations, so it is an isomorphism of ${<}$ -structures. Rubric: full credit for the alternating forth/back stages, the use of the extension lemma, and the verification that the union is a bijective order isomorphism.

Exercise 8 (hard, symbolic).

Prove the elementary chain theorem (Tarski-Vaught union): if $(M_{i})_{i < λ}$ is a chain with $M_{i} ⪯ M_{j}$ for $i < j$ , then each $M_{i} ⪯ ⋃_{i < λ} M_{i}$ .

Hint

Let $M = ⋃_{i} M_{i}$ . Prove $M_{i} ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow M ⊨ φ [\overset{a}{ˉ}]$ for all $φ$ and tuples from $M_{i}$ , by induction on $φ$ . The existential case is where the chain hypothesis enters: a witness in $M$ lies in some $M_{j}$ .

Answer

First $M = ⋃_{i} M_{i}$ is a well-defined $L$ -structure: the universes form an increasing chain, and since each inclusion $M_{i} \subseteq M_{j}$ is (elementary, hence) a substructure embedding, the interpretations cohere, so functions and relations are defined unambiguously on the union. Claim: for every $φ$ , every $i$ , and every tuple $\overset{a}{ˉ}$ from $M_{i}$ , $M_{i} ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow M ⊨ φ [\overset{a}{ˉ}]$ . Induct on $φ$ . Atomic formulas hold by the substructure relation. Connectives pass through the inductive hypothesis. For $φ = \exists x ψ (x, \overset{a}{ˉ})$ : if $M_{i} ⊨ φ [\overset{a}{ˉ}]$ , a witness in $M_{i} \subseteq M$ and the inductive hypothesis give $M ⊨ φ [\overset{a}{ˉ}]$ . Conversely if $M ⊨ φ [\overset{a}{ˉ}]$ , a witness $b \in M$ lies in some $M_{j}$ with $j \geq i$ ; then $\overset{a}{ˉ}, b$ are all in $M_{j}$ , the inductive hypothesis gives $M_{j} ⊨ ψ [b, \overset{a}{ˉ}]$ , so $M_{j} ⊨ \exists x ψ (x, \overset{a}{ˉ})$ , and $M_{i} ⪯ M_{j}$ pulls this back to $M_{i} ⊨ φ [\overset{a}{ˉ}]$ . Thus the inclusion $M_{i} \subseteq M$ preserves all formulas, i.e. $M_{i} ⪯ M$ . Rubric: full credit for the coherence of the union, the formula induction, and the correct use of both the chain enumeration (witness lands in some $M_{j}$ ) and the hypothesis $M_{i} ⪯ M_{j}$ .

Advanced results Master

The toolkit fixed in the Formal definition supports four developments: the preservation hierarchy that grades maps by the formulas they respect, the Tarski-Vaught machinery driving elementary chains and Löwenheim-Skolem, the back-and-forth and Ehrenfeucht-Fraïssé characterisations of elementary equivalence with no deductive calculus in sight, and the method of diagrams that turns embeddings into models.

Theorem 1 (the preservation hierarchy). The kinds of maps between $L$ -structures are graded by the syntactic class they preserve. A homomorphism $h : M \to N$ preserves atomic positive formulas in the forward direction; an embedding preserves all quantifier-free formulas in both directions; an elementary embedding preserves every first-order formula ^{[Hodges Ch. 1]}. The Łoś-Tarski theorem sharpens the first level: a first-order theory is preserved under substructures iff it is axiomatisable by universal ( $Π_{1}$ ) sentences, and preserved under extensions iff by existential ( $Σ_{1}$ ) sentences; the Chang-Łoś-Suszko theorem extends this to chains, where preservation under unions of chains characterises $Π_{2}$ -axiomatisability. These preservation theorems read the map hierarchy off the quantifier prefix, the semantic counterpart of the prenex hierarchy of 42.01.03 pending.

Theorem 2 (Tarski-Vaught, elementary chains, and Löwenheim-Skolem). The Tarski-Vaught test characterises $M ⪯ N$ by the single condition that every $L (M)$ -formula satisfiable in $N$ over parameters from $M$ is witnessed inside $M$ ^{[Tarski and Vaught 1957]}. From it the union of an elementary chain is an elementary extension of each member, and the Skolem-hull construction yields the downward Löwenheim-Skolem-Tarski theorem: every infinite $N$ with $∣ L ∣ \leq κ$ has, over any $A \subseteq N$ with $∣ A ∣ \leq κ$ , an elementary substructure of size $max (κ, ∣ A ∣, ℵ_{0})$ . Compactness 42.01.07 pending supplies the upward direction — every infinite structure has arbitrarily large elementary extensions — so the elementary-substructure relation populates every infinite cardinal, and the Löwenheim-Skolem-Tarski theorem fixes the spectrum of cardinalities at which a theory has models.

Theorem 3 (back-and-forth, Ehrenfeucht-Fraïssé, and Fraïssé's characterisation of $\equiv$ ). A back-and-forth system between $M$ and $N$ is a nonempty set $I$ of finite partial isomorphisms closed under the forth property (each $p \in I$ extends to any $a \in M$ ) and the back property (each extends to any $b \in N$ ); its existence implies $M \equiv N$ , and for countable $M, N$ implies $M ≅ N$ ^{[Hodges Ch. 3]}. The finitary form is the Ehrenfeucht-Fraïssé game $EF_{n} (M, N)$ : across $n$ rounds Spoiler plays an element from either structure and Duplicator answers in the other, Duplicator winning iff the chosen tuples form a partial isomorphism. The Fraïssé-Hintikka theorem states that Duplicator wins $EF_{n}$ iff $M$ and $N$ agree on all sentences of quantifier rank $\leq n$ , so Duplicator wins every finite game iff $M \equiv N$ . This converts elementary equivalence — a statement quantifying over the infinitely many sentences — into a combinatorial game, the indispensable tool for separating structures in finite model theory and for the $0$ - $1$ laws.

Theorem 4 (the method of diagrams). Robinson's diagram lemma renders embeddings as satisfaction facts: $N$ admits an embedding of $M$ iff some expansion of $N$ models the atomic diagram $Diag (M)$ , and an elementary embedding iff it models the elementary diagram $Diag_{el} (M)$ ^{[Chang and Keisler Ch. 2]}. Fed to the compactness theorem of 42.02.02 pending, this manufactures elementary extensions realising prescribed types, the source of saturated and homogeneous models; combined with downward Löwenheim-Skolem it produces the elementary substructures of controlled cardinality on which stability theory operates. The diagram method is the bridge from the static comparison of two structures to the constructive generation of new ones, and it is the technique unit 42.02.02 pending develops in full alongside quantifier elimination 42.02.05 pending.

Synthesis. The Tarski-Vaught test is the foundational reason elementarity is a closure property rather than a global comparison, and putting these together it controls all four developments: it is exactly what makes the elementary-chain theorem run stage by stage, and the Skolem hull it builds is the downward Löwenheim-Skolem theorem read as a witness-closure construction. The preservation hierarchy generalises the isomorphism-preserves-truth theorem of 42.01.04 pending from the top of the ladder downward — an isomorphism preserves everything because it is total and onto, an embedding preserves only the quantifier-free fragment because it sees no witnesses outside its image, and elementary embedding is the exact surplus that recovers the quantifiers; this is the central insight that the quantifier prefix of 42.01.03 pending, read semantically, grades both formulas and the maps preserving them. Back-and-forth is dual to the deductive route to $\equiv$ : where completeness 42.01.06 pending certifies same-theory by a proof system, the Ehrenfeucht-Fraïssé game certifies it by a combinatorial strategy, the same relation $\equiv$ approached from syntax and from play. The method of diagrams is the bridge that turns every preceding comparison into a construction, feeding the compactness of 42.02.02 pending to build the elementary extensions, types, and saturated models on which the structural model theory of 42.02.05 pending and beyond is erected. This is the toolkit promised at the Beginner tier — embeddings, $⪯$ , $\equiv$ , and the games that detect it — assembled by recursion on the satisfaction relation of 42.01.04 pending and standing ready for the rest of model theory to deploy.

Full proof set Master

Proposition 1 (substructure preserves quantifier-free formulas; embedding criterion). If $M \subseteq N$ then $M ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow N ⊨ φ [\overset{a}{ˉ}]$ for every quantifier-free $φ$ and tuple $\overset{a}{ˉ}$ from $M$ . Conversely an injective $h : M \to N$ commuting with the constants and functions and satisfying $\overset{a}{ˉ} \in R^{M} \Leftrightarrow h \overset{a}{ˉ} \in R^{N}$ is an embedding, and preserves all quantifier-free formulas.

Proof. Term values agree: by induction on terms, $t^{M} [\overset{a}{ˉ}] = t^{N} [\overset{a}{ˉ}]$ for $\overset{a}{ˉ}$ from $M$ , since the constants and functions of $N$ restrict to those of $M$ . Atomic $R t_{1} \dots t_{n}$ : both sides ask whether the common tuple of term values lies in $R^{M} = R^{N} \cap M^{n}$ , and the tuple is in $M^{n}$ , so the answers coincide; equality is identity in both. Connectives propagate the equivalence, and quantifier-free formulas are Boolean combinations of atomics, so the equivalence holds throughout. For the converse, the term induction $h (t^{M} [\overset{a}{ˉ}]) = t^{N} [h \overset{a}{ˉ}]$ uses the constant- and function-commutation; the atomic biconditional is the relation hypothesis together with injectivity for equality; Boolean combinations preserve the biconditional. $□$

Proposition 2 (Tarski-Vaught test). For $M \subseteq N$ : $M ⪯ N$ iff for every $φ (x, \overset{y}{ˉ})$ and $\overset{ˉ}{b}$ from $M$ , $N ⊨ \exists x φ (x, \overset{ˉ}{b})$ implies some $a \in M$ has $N ⊨ φ (a, \overset{ˉ}{b})$ .

Proof. ( $\Rightarrow$ ) Elementarity gives $N ⊨ \exists x φ (x, \overset{ˉ}{b}) \Rightarrow M ⊨ \exists x φ (x, \overset{ˉ}{b})$ , so a witness $a \in M$ has $M ⊨ φ (a, \overset{ˉ}{b})$ , and elementarity again gives $N ⊨ φ (a, \overset{ˉ}{b})$ . ( $\Leftarrow$ ) Induct on $ψ$ to show $M ⊨ ψ [\overset{a}{ˉ}] \Leftrightarrow N ⊨ ψ [\overset{a}{ˉ}]$ for $\overset{a}{ˉ}$ from $M$ . Atomic: Proposition 1. Connectives: inductive hypothesis. Existential $ψ = \exists x φ (x, \overset{a}{ˉ})$ : forward, a witness in $M$ transfers up by the inductive hypothesis; backward, the witness condition supplies $a^{'} \in M$ with $N ⊨ φ (a^{'}, \overset{a}{ˉ})$ , and the inductive hypothesis gives $M ⊨ φ (a^{'}, \overset{a}{ˉ})$ . Universals reduce via $\neg\exists\neg$ . Hence the inclusion is elementary. $□$

Proposition 3 (downward Löwenheim-Skolem-Tarski). Let $∣ L ∣ \leq κ$ infinite, $N$ an $L$ -structure, $A \subseteq N$ with $∣ A ∣ \leq κ$ . There is $M ⪯ N$ with $A \subseteq M$ and $∣ M ∣ \leq κ$ .

Proof. Fix a choice of Skolem witnesses: for each formula $φ (x, \overset{y}{ˉ})$ and tuple $\overset{ˉ}{b}$ from $N$ with $N ⊨ \exists x φ (x, \overset{ˉ}{b})$ , select one $w_{φ, \overset{ˉ}{b}} \in N$ with $N ⊨ φ (w_{φ, \overset{ˉ}{b}}, \overset{ˉ}{b})$ . Set $A_{0} = A \cup {c^{N} : c a constant}$ and $A_{n + 1} = A_{n} \cup {w_{φ, \overset{ˉ}{b}} : φ, \overset{ˉ}{b} from A_{n}}$ . Since there are $\leq κ$ formulas and, at each stage, $\leq κ$ parameter tuples, $∣ A_{n + 1} ∣ \leq κ$ whenever $∣ A_{n} ∣ \leq κ$ ; by induction every $A_{n}$ has size $\leq κ$ , so $M = ⋃_{n} A_{n}$ has $∣ M ∣ \leq κ$ . $M$ contains all constants and is closed under functions (a function value is the witness for $\exists x (x = f \overset{y}{ˉ})$ ), so $M$ is the universe of a substructure $M \subseteq N$ . For the witness condition: if $N ⊨ \exists x φ (x, \overset{ˉ}{b})$ with $\overset{ˉ}{b}$ from $M$ , then $\overset{ˉ}{b}$ lies in some $A_{n}$ , so $w_{φ, \overset{ˉ}{b}} \in A_{n + 1} \subseteq M$ witnesses $φ$ . By Proposition 2, $M ⪯ N$ . $□$

Proposition 4 (elementary chain theorem). If $(M_{i})_{i < λ}$ is an elementary chain then $M_{i} ⪯ M := ⋃_{j < λ} M_{j}$ for every $i$ .

Proof. The union is a structure: universes increase, and each $M_{i} \subseteq M_{j}$ being a substructure inclusion makes the interpretations cohere, so a constant, function value, or relation instance computed in any $M_{j}$ containing the relevant elements is independent of $j$ . Prove $M_{i} ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow M ⊨ φ [\overset{a}{ˉ}]$ for $\overset{a}{ˉ}$ from $M_{i}$ , by induction on $φ$ . Atomic: substructure relation. Connectives: inductive hypothesis. Existential $\exists x ψ$ : forward is immediate as $M_{i} \subseteq M$ ; backward, a witness $b \in M$ lies in some $M_{j}$ , $j \geq i$ , so $M_{j} ⊨ ψ [b, \overset{a}{ˉ}]$ by the inductive hypothesis, whence $M_{j} ⊨ \exists x ψ [\overset{a}{ˉ}]$ , and $M_{i} ⪯ M_{j}$ returns $M_{i} ⊨ \exists x ψ [\overset{a}{ˉ}]$ . Universals via $\neg\exists\neg$ . So the inclusion $M_{i} \subseteq M$ is elementary. $□$

Proposition 5 (back-and-forth yields $\equiv$ , and isomorphism in the countable case). If a back-and-forth system $I$ between $M$ and $N$ exists then $M \equiv N$ ; if moreover $M, N$ are countable then $M ≅ N$ .

Proof. For $\equiv$ : show by induction on quantifier rank that for $p \in I$ with domain tuple $\overset{a}{ˉ}$ and range tuple $\overset{ˉ}{b} = p (\overset{a}{ˉ})$ , and every $φ$ , $M ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow N ⊨ φ [\overset{ˉ}{b}]$ . Atomic and Boolean cases hold because $p$ is a partial isomorphism and the inductive hypothesis. For $\exists x ψ$ : if $M ⊨ \exists x ψ [\overset{a}{ˉ}]$ with witness $a^{*}$ , the forth property extends $p$ to $p^{'} \in I$ with $a^{*} \in dom (p^{'})$ ; the inductive hypothesis applied to $p^{'}$ gives $N ⊨ ψ [p^{'} (a^{*}), \overset{ˉ}{b}]$ , so $N ⊨ \exists x ψ [\overset{ˉ}{b}]$ . The converse uses the back property symmetrically. Taking $\overset{a}{ˉ}$ empty (the empty map lies in $I$ , which is nonempty and downward closed under restriction) gives equality of theories, $M \equiv N$ . For isomorphism with $M, N$ countable, enumerate $M$ and $N$ and build $p_{0} \subseteq p_{1} \subseteq \dots$ in $I$ alternately forcing the next element of $M$ into the domain (forth) and the next element of $N$ into the range (back); the union is an order-respecting bijection commuting with all symbols, an isomorphism. $□$

Connections Master

Structures and Tarski's definition of truth 42.01.04 pending is the semantic foundation this unit builds on. The satisfaction relation $M ⊨ φ [\overset{a}{ˉ}]$ , the coincidence lemma, and the isomorphism-preserves-truth theorem proved there are the exact inputs to the definitions of elementary embedding, $⪯$ , and $\equiv$ here; every formula induction in this unit (Tarski-Vaught, elementary chains, back-and-forth) is run over the recursive satisfaction clauses of that unit. That unit owns the meaning of a single structure; this unit owns the comparison of structures.
The Löwenheim-Skolem theorems 42.01.07 pending supply the compactness and Skolem-function machinery that the downward Löwenheim-Skolem corollary here reads model-theoretically. The upward direction — arbitrarily large elementary extensions — is a compactness consequence proved there, and together with the Tarski-Vaught Skolem hull of this unit it fixes the cardinal spectrum of an elementary class. The two units meet wherever a theory's models must be produced at a prescribed cardinality.
The method of diagrams and the compactness theorem in model theory, co-produced as 42.02.02 pending, take the atomic and elementary diagrams introduced here as their primitive device. Robinson's diagram lemma of this unit, fed to compactness there, manufactures the elementary extensions, realised types, and saturated models that are the working objects of model theory; the embeddings and elementary embeddings defined here become satisfaction facts about diagrams there.
Quantifier elimination and model completeness, co-produced as 42.02.05 pending, specialise the preservation hierarchy and the Tarski-Vaught test of this unit to theories whose definable sets collapse to the quantifier-free level. Model completeness is exactly the statement that every embedding between models of the theory is elementary, the strongest possible link between the embedding and elementary-embedding levels graded here; quantifier elimination is the syntactic certificate that produces it, and the dense-linear-order back-and-forth of this unit is its first instance.

Historical & philosophical context Master

The systematic study of structures compared by embeddings and elementary maps belongs to the consolidation of model theory in the 1950s. Alfred Tarski and Robert Vaught's "Arithmetical extensions of relational systems" (1957) introduced the elementary-extension relation and the elementary-substructure relation as primary objects, proved the test now bearing their names, and established the elementary-chain union theorem; these results turned the Löwenheim-Skolem phenomena — Leopold Löwenheim (1915) and Thoralf Skolem (1920) had shown first-order theories with infinite models have countable models — into the controlled construction of elementary substructures and extensions of prescribed cardinality ^{[Tarski and Vaught 1957]}.

The back-and-forth method descends from Georg Cantor's 1895 proof that the countable dense linear orders without endpoints form a single isomorphism type; Edward Huntington and others isolated the technique, and Roland Fraïssé (1954) and Andrzej Ehrenfeucht (1961) recast it as the game that characterises elementary equivalence by quantifier rank, the Fraïssé-Hintikka analysis fixing the connection to sentences of bounded rank. Abraham Robinson's method of diagrams, developed through the 1950s, made embeddings into models and supplied the model-theoretic proof technique that compactness drives; the preservation theorems of Łoś, Tarski, Suszko, and Chang reading the quantifier prefix off the map hierarchy were assembled in the same period and codified in the textbooks of Chang and Keisler, Hodges, and Marker ^{[Chang and Keisler Ch. 3]}.

Bibliography Master

@book{marker2002modeltheory,
  author    = {Marker, David},
  title     = {Model Theory: An Introduction},
  series    = {Graduate Texts in Mathematics},
  volume    = {217},
  publisher = {Springer},
  year      = {2002}
}

@book{changkeisler1990,
  author    = {Chang, Chen Chung and Keisler, H. Jerome},
  title     = {Model Theory},
  edition   = {3},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {73},
  publisher = {North-Holland},
  year      = {1990}
}

@book{hodges1993modeltheory,
  author    = {Hodges, Wilfrid},
  title     = {Model Theory},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {42},
  publisher = {Cambridge University Press},
  year      = {1993}
}

@book{hodges1997shorter,
  author    = {Hodges, Wilfrid},
  title     = {A Shorter Model Theory},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@article{tarskivaught1957,
  author  = {Tarski, Alfred and Vaught, Robert L.},
  title   = {Arithmetical extensions of relational systems},
  journal = {Compositio Mathematica},
  volume  = {13},
  year    = {1957},
  pages   = {81--102}
}

@article{fraisse1954,
  author  = {Fra\"{i}ss\'{e}, Roland},
  title   = {Sur quelques classifications des syst\`{e}mes de relations},
  journal = {Publications Scientifiques de l'Universit\'{e} d'Alger, S\'{e}rie A},
  volume  = {1},
  year    = {1954},
  pages   = {35--182}
}

@article{ehrenfeucht1961,
  author  = {Ehrenfeucht, Andrzej},
  title   = {An application of games to the completeness problem for formalized theories},
  journal = {Fundamenta Mathematicae},
  volume  = {49},
  year    = {1961},
  pages   = {129--141}
}

Prerequisites

42.01.04

Tier anchors

beginner: Marker 2002 *Model Theory: An Introduction* (Springer GTM 217) §1.1 (a structure read informally as a world made of objects with meanings attached to its symbols; one world sitting inside another as a sub-world; two worlds that no finite English description can tell apart; the picture of matching up two ordered sets of beads point by point so that order is respected); checking by hand that the whole numbers sit inside the integers and that the integers sit inside the rationals, and that the rationals and the reals, ordered, cannot be separated by any finite check
intermediate: Marker 2002 *Model Theory: An Introduction* §§1.1-1.3 (L-structures and L-homomorphisms; embeddings and substructures; elementary embeddings and elementary substructures M ≼ N; elementary equivalence M ≡ N as agreement on all L-sentences; the Tarski-Vaught test for M ≼ N; elementary chains and the Tarski-Vaught union theorem; the back-and-forth method proving any two countable dense linear orders without endpoints are isomorphic); Hodges 1997 *A Shorter Model Theory* (Cambridge) Ch. 2-3
master: Marker 2002 *Model Theory: An Introduction* (Springer GTM 217) Ch. 1-2 (structures, embeddings, elementary maps, the Tarski-Vaught test, elementary chains, the method of diagrams, downward Löwenheim-Skolem); Chang and Keisler 1990 *Model Theory* 3e (North-Holland) Ch. 1-3 (the systematic theory of elementary equivalence, elementary extensions, and chains); Hodges 1993 *Model Theory* (Cambridge) Ch. 2-3 (homomorphisms and the preservation hierarchy, back-and-forth systems, Ehrenfeucht-Fraïssé games and the Fraïssé characterisation of ≡); Tarski and Vaught 1957 *Arithmetical extensions of relational systems* (Compositio Math. 13)

References

Marker, D. — Model Theory: An Introduction · Graduate Texts in Mathematics 217, Springer (2002), Chapters 1-2. For a language L, an L-structure M consists of a universe M together with interpretations of the constant, function, and relation symbols. An L-embedding h : M → N is an injection preserving the interpretation of every symbol: h(c^M)=c^N, h(f^M(a))=f^N(h(a)), and a-bar ∈ R^M iff h(a-bar) ∈ R^N; an isomorphism is a surjective embedding; M is a substructure of N (M ⊆ N) when M ⊆ N and the inclusion is an embedding, equivalently when M is a subset of N closed under the functions and containing the constants, carrying the induced relations. An embedding h : M → N is elementary when M ⊨ φ(a-bar) iff N ⊨ φ(h(a-bar)) for every L-formula φ and tuple a-bar from M; M is an elementary substructure of N, written M ≼ N, when M ⊆ N and the inclusion is elementary. The Tarski-Vaught test: M ⊆ N is elementary iff for every formula φ(x, y-bar) and tuple b-bar from M, if N ⊨ ∃x φ(x, b-bar) then there is a ∈ M with N ⊨ φ(a, b-bar). Two structures are elementarily equivalent, M ≡ N, when they satisfy exactly the same L-sentences; M ≼ N implies M ≡ N but not conversely. The elementary diagram method: Th(M) is the set of L-sentences true in M, a complete theory; the elementary diagram is Th of M with a constant for each element. The Tarski-Vaught chain theorem: the union of an elementary chain (M_i)_{i<κ} with M_i ≼ M_j for i<j is an elementary extension of each M_i. The downward Löwenheim-Skolem theorem: if M is an L-structure and A ⊆ M with |A| ≤ κ, |L| ≤ κ, κ infinite, there is M_0 ≼ M with A ⊆ M_0 and |M_0| ≤ κ; in particular every infinite structure in a countable language has a countable elementary substructure. The back-and-forth method shows any two countable dense linear orders without endpoints are isomorphic (Cantor's theorem).
Hodges, W. — Model Theory · Cambridge University Press (1993), Chapters 1-3. Treats the hierarchy of maps between structures and the formulas each kind preserves: homomorphisms preserve atomic positive sentences; embeddings preserve quantifier-free formulas in both directions; elementary embeddings preserve all first-order formulas. Develops partial isomorphisms and back-and-forth systems: a back-and-forth system between M and N is a nonempty set I of partial isomorphisms with the forth property (each p ∈ I extends to cover any further element of M) and the back property (each p extends to cover any further element of N); the existence of a back-and-forth system implies M and N satisfy the same first-order sentences, and for countable M, N implies M ≅ N. Introduces the Ehrenfeucht-Fraïssé game EF_n(M, N): Spoiler picks elements alternately from the two structures, Duplicator answers to maintain a partial isomorphism on the chosen tuples; Duplicator wins the n-round game iff M and N agree on all sentences of quantifier rank ≤ n, and Duplicator wins every finite game iff M ≡ N (the Fraïssé-Hintikka theorem), giving a purely combinatorial characterisation of elementary equivalence with no reference to a deductive calculus.
Chang, C. C. and Keisler, H. J. — Model Theory · Studies in Logic and the Foundations of Mathematics 73, 3rd edition, North-Holland (1990), Chapters 1-3. Systematic development of elementary equivalence and elementary extension. Establishes that elementary equivalence is strictly coarser than isomorphism, exhibiting elementarily equivalent non-isomorphic structures (dense linear orders of different cardinalities, ω-saturated models). Proves the elementary chain theorem (Tarski-Vaught): the union of an elementary chain is an elementary extension of each member, with the proof by induction on formula complexity using that existential witnesses appear at some stage of the chain. Presents the method of diagrams (Robinson): the diagram D(M) of M (the atomic and negated-atomic sentences with constants for elements) characterises embeddings — N models D(M), in the expanded language naming the elements of M, iff there is an embedding M → N; the elementary diagram El-D(M) (all sentences true in M with the new constants) characterises elementary embeddings. Develops the downward and upward Löwenheim-Skolem-Tarski theorems and the Löwenheim-Skolem-Tarski theorem as consequences of compactness and the Skolem-hull construction.
Tarski, A. and Vaught, R. L. — Arithmetical extensions of relational systems · Compositio Mathematica 13 (1957), pp. 81-102. The paper that introduced elementary extensions (arithmetical extensions, in the original terminology) and the elementary-substructure relation as objects of systematic study, and proved the Tarski-Vaught test characterising when a substructure is elementary by the existential-witness condition, together with the elementary-chain (union) theorem. These two results are the technical backbone of the construction of elementary substructures and elementary extensions, hence of the model-theoretic reading of the Löwenheim-Skolem theorems.

Estimated time

beginner: 20m
intermediate: 52m
master: 88m