Substructures and chains of models

Truth propogates through an elementary chain of models to the limit.

Another serialized installment from A Panorama of Logic, my book currently in progress. The book aims to become an introduction to topics in logic for philosophers, mathematicians, and computer scientists. Follow along as new chapters are released every week.

Substructures

One mathematical structure M is a subsubstructure of another N, written simply M ⊆ N, if the domain of M is contained in the domain of N, and the two structures agree on the interpretations of all the relations, functions and constants on that domain. For example, here is a chain of substructures:

\(⟨ℕ,+,·,0,1,<⟩ ⊆ ⟨ℤ,+,·,0,1,<⟩ ⊆ ⟨ℚ,+,·,0,1,<⟩ ⊆ ⟨ℝ,+,·,0,1,<⟩. \)

This is a chain of substructures because every natural number is an integer, every integer is a rational number, every rational number is a real number and all these structures agree on addition and multiplication on their common domains, on the meaning of 0 and 1, and on the order <.

Elementary substructures

A substructure M of a structure N is an elementary substructure, written M ≺ N, if M is a substructure of N and also they agree on the truth of every assertion, so that M ⊨ φ[a₁,...,a_n] if and only if N ⊨ φ[a₁,...,a_n], for every a₁, ..., a_n in M and every assertion φ in the language of these structures.

None of the substructures pictured in the chain of substructures above are elementary substructures, nor even elementarily equivalent. To see this, observe that amongst these structures, only ℝ has a solution to x² = 2; only ℕ thinks x + y = 0 → x = 0; only ℚ is 2-divisible, but does not have √2; and only ℤ satisfies the negations of all those properties. So none of these substructures is an elementary substructure.

Absoluteness of truth

Although an assertion can have a different truth value in a substructure than it does in the parent structure, as we have just observed, nevertheless in certain situations one can find an agreement—some kinds of truth values will be absolute. Let us begin by showing that term evaluation is absolute between a substructure and its parent.

Lemma. Term evaluation is absolute between a substructure and its parent. That is, evaluating a term t at points a₁, ..., a_n in a substructure M ⊆ N gives the same value as evaluating it in the parent structure N,

\(t^M( a_1,...,a_n ) = t^N( a_1,...,a_n ). \)

Proof. We prove this by induction on terms. Assume we have a substructure M ⊆ N. The claim is true for constant symbols, c^M = c^N, simply because this is part of what it means to be a substructure—constants must be interpreted the same in a substructure as in the parent structure. The claim is also true for variables, since we are using the same valuation [a₁,...,a_n] in the substructure as in the parent structure, so each variable x_i is interpreted as a_i in each case. Finally, we consider terms of the form f(t₁,...,t_k) and assume inductively that the claim is true for terms t₁,...,t_k. Observe that

\(\begin{eqnarray*} \bigl( f( t_1,...,t_k )\bigr )^M( a_1,...,a_n ) & = & f^M\bigl( t_1^M( a_1,...,a_n ),...,t_k^M( a_1,...,a_n )\bigr )\\ & = & f^N\bigl( t_1^N( a_1,...,a_n ),...,t_k^N( a_1,...,a_n )\bigr )\\ & = & \bigl( f( t_1,...,t_k )\bigr )^N( a_1,...,a_n ). \end{eqnarray*} \)

We used the induction hypothesis that t_i^M(a₁,...,a_n) = t_i^N(a₁,...,a_n) in the second equality, together with the fact that f ^M agrees with f ^N on points in M by the definition of substructure. Thus, by induction, we conclude that the claim holds for all terms. □

Absoluteness Theorem. Assume M is a substructure of N.

1. Quantifier-free truth is absolute between a substructure and its parent—the models agree on the truth of any quantifier-free assertion ψ at individuals a₁,...,a_n from the substructure M:

\( M ⊨ ψ[a_1, ...,a_n]\qquad\text{ if and only if }\qquad N ⊨ ψ[a_1, ...,a_n]. \)

2. Existential assertions are upward absolute from a substructure to its parent—if ψ is quantifier-free, then

\(M ⊨ ( ∃x ψ )[a_1, ...,a_n]\qquad\text{ implies }\qquad N ⊨ ( ∃x ψ )[a_1, ...,a_n]. \)

3. Universal assertions are downward absolute from a parent structure to any substructure—if ψ is quantifier-free, then

\(N ⊨ ( ∀x ψ )[a_1, ...,a_n]\qquad\text{ implies }\qquad M ⊨ ( ∀x ψ )[a_1, ...,a_n]. \)

Proof. We know by the lemma above that term evaluation is absolute between a substructure M ⊆ N and its parent, and this implies that every equality assertion s = t of terms will have the same truth value in M as in N. Similarly, every relational atomic assertion Rt₁···t_k will have the same truth value in M as in N, because the terms evaluate the same and similarly the relation in M agrees with N on points in M. Thus, the claim of statement (1) is true for atomic assertions.

We may extend from the atomic assertions to all quantifier-free assertions by induction on formulas. If the truth equivalence of statement (1) holds for assertions φ and ψ, then it also holds, I claim, for φ ∧ ψ, φ ∨ ψ, φ → ψ, φ ↔ ψ, and ¬φ.

Let me illustrate for conjunction:

\(\begin{eqnarray*} M ⊨ ( φ ∧ ψ )[a_1, ...,a_n] &\iff& M ⊨ φ[a_1, ...,a_n]\text{ and }M ⊨ ψ[a_1, ...,a_n]\\ &\iff& N ⊨ φ[a_1, ...,a_n]\text{ and }N ⊨ ψ[a_1, ...,a_n]\\ &\iff& N ⊨ ( φ ∧ ψ )[a_1, ...,a_n]. \end{eqnarray*} \)

First, we use the definition of satisfaction to break up the conjunction, and then we use the induction hypothesis to move from M to N, and finally we use the definition of satisfaction again to reassemble the conjunction. The argument follows a similar pattern for all the other logical connectives. Since every quantifier-free assertion is built in this way from atomic assertions via logical connectives, this establishes statement (1) for all quantifier-free assertions.

For statement (2), suppose that the substructure satisfies an existential statement M ⊨ (∃x ψ)[a₁,...,a_n]. So there is an individual b in M for which M ⊨ ψ[a₁,...,a_n,b]. Since ψ is quantifier-free, it follows from statement (1) that this is absolute to the parent model N ⊨ ψ[a₁,...,a_n,b] and consequently N ⊨ (∃x ψ)[a₁,...,a_n], as desired.

The reader will prove statement (3) in the exercises. □

Elementary chains

Let us next consider the concept of a chain of models, a tower of structures M_n, each a substructure of the next.

\(M_0\quad ⊆ \quad M_1\quad ⊆ \quad M_2\quad ⊆ \quad ··· \)

The union or limit of such a chain is the model M = ∪_n M_n, whose domain is the union of the domains of the models appearing in the chain, upon which we interpret the structural elements, the functions, relations, and constants of the signature. These interpretations are well defined on limit model precisely because the models in the tower cohere with one another on this atomic structure.

An elementary chain is a special kind of chain, where each model is an elementary substructure of the next.

\( M_0\quad ≺ \quad M_1\quad ≺ \quad M_2\quad ≺ \quad ··· \)

In this case, we claim, the limit model is an elementary extension of all the models in the chain.

Elementary chain theorem. The limit model of an elementary chain is an elementary extension of every model in the chain.

\( M_0\quad ≺ \quad M_1\quad ≺ \quad M_2\quad ≺ \quad ··· \quad ≺ \quad M\)

Proof.