# 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:

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*_{1},...,*a _{n}*] if and only if

*N*⊨ φ[

*a*

_{1},...,

*a*], for every

_{n}*a*

_{1}, ...,

*a*in

_{n}*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} = 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*_{1}, ..., *a _{n}* in a substructure

*M*⊆

*N*gives the same value as evaluating it in the parent structure

*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*, 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 [

^{N}*a*

_{1},...,

*a*] in the substructure as in the parent structure, so each variable

_{n}*x*is interpreted as

_{i}*a*in each case. Finally, we consider terms of the form

_{i}*f*(

*t*

_{1},...,

*t*) and assume inductively that the claim is true for terms

_{k}*t*

_{1},...,

*t*Observe that

_{k. }We used the induction hypothesis that *t _{i}^{M}*(

*a*

_{1},...,

*a*) =

_{n}*t*(

_{i}^{N}*a*

_{1},...,

*a*) in the second equality, together with the fact that

_{n}*f*agrees with

^{M}*f*on points in

^{N}*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*.

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*_{1},...,*a*from the substructure_{n}*M*:

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

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

**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*_{1}···*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:

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*_{1},...,*a _{n}*]. So there is an individual

*b*in

*M*for which

*M*⊨ ψ[

*a*

_{1},...,

*a*,

_{n}*b*]. Since ψ is quantifier-free, it follows from statement (1) that this is absolute to the parent model

*N*⊨ ψ[

*a*

_{1},...,

*a*,

_{n}*b*] and consequently N ⊨ (∃x ψ)[

*a*

_{1},...,

*a*], as desired.

_{n}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.

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.

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.

**Proof.**

## Keep reading with a 7-day free trial

Subscribe to Infinitely More to keep reading this post and get 7 days of free access to the full post archives.