Basics of Model Theory

Definition of reduct and expansion

Suppose $L\subseteq L^{\prime }$source, $M$source is an $L$source-structure and $M^{\prime }$source is an $L^{\prime }$source-structure. $M$source is the reduct of $M^{\prime }$source to $L$source, and $M^{\prime }$source is an expansion of $M$source to $L^{\prime }$source iff

1. $\left|M\right|=\left|M^{\prime }\right|$source

2. For every constant symbol $c\in L$source, $c^M=c^{M^{\prime }}$source.

3. For every function symbol $f\in L$source, $f^M=f^{M^{\prime }}$source.

4. For every predicate symbol $P\in L$source, $P^M=P^{M^{\prime }}$source.

Reducts preserve smaller-language sentences

If an $L$source-structure $M$source is a reduct of an $L^{\prime }$source-structure $M^{\prime }$source, then for all $L$source-sentences $A$source,

Proof

Exercise.

Exercise proving preservation under reduct

Prove reference prop:reduct.

Expansion by one predicate relation

When we have an $L$source-structure $M$source, and $L^{\prime }=L\cup \left\{P\right\}$source is the expansion of $L$source obtained by adding a single $n$source-place predicate symbol $P$source, and $R\subseteq {\left|M\right|}^n$source is an $n$source-place relation, then we write $M\left[R\right]$source for the expansion $M^{\prime }$source of $M$source with $P^{M^{\prime }}=R$source.

Definition of substructure and extension

Given structures $M$source and $M^{\prime }$source for the same language $L$source, we say that $M$source is a substructure of $M^{\prime }$source, and $M^{\prime }$source an extension of $M$source, written $M\subseteq M^{\prime }$source, iff

1. $\left|M\right|\subseteq \left|M^{\prime }\right|$source,

2. For each constant $c\in L$source, $c^M=c^{M^{\prime }}$source;

3. For each $n$source-place function symbol $f\in L$source $f^M(a_1,\dots ,a_n)=f^{M^{\prime }}(a_1,\dots ,a_n)$source for all $a_1$source, dots, $a_n\in \left|M\right|$source.

4. For each $n$source-place predicate symbol $R\in L$source, $⟨a_1,\dots ,a_n⟩\in R^M$source iff $⟨a_1,\dots ,a_n⟩\in R^{M^{\prime }}$source for all $a_1$source, dots, $a_n\in \left|M\right|$source.

Overspill theorem for finite models

If a set $\Gamma$source of sentences has arbitrarily large finite models, then it has an infinite model.

Proof

Expand the language of $\Gamma$source by adding countably many new constants $c_0$source, $c_1$source, dots and consider the set $\Gamma \cup \{c_i\ne c_j:i\ne j\}$source. To say that $\Gamma$source has arbitrarily large finite models means that for every $m>0$source there is $n\ge m$source such that $\Gamma$source has a model of cardinality $n$source. This implies that $\Gamma \cup \{c_i\ne c_j:i\ne j\}$source is finitely satisfiable. By compactness, $\Gamma \cup \{c_i\ne c_j:i\ne j\}$source has a model $M$source whose domain must be infinite, since it satisfies all inequalities $c_i\ne c_j$source.

Finiteness is not first-order definable

There is no sentence $A$source of any first-order language that is true in a structure $M$source if and only if the domain $\left|M\right|$source of the structure is infinite.

Proof

If there were such a $A$source, its negation $\neg A$source would be true in all and only the finite structures, and it would therefore have arbitrarily large finite models but it would lack an infinite model, contradicting reference overspill.

Definition of elementary equivalence

Given two structures $M$source and $M^{\prime }$source for the same language $L$source, we say that $M$source is elementarily equivalent to $M^{\prime }$source, written $M\equiv M^{\prime }$source, if and only if for every sentence $A$source of $L$source, $M\models A$source iff $M^{\prime }\models A$source.

Definition of isomorphism

Given two structures $M$source and $M^{\prime }$source for the same language $L$source, we say that $M$source is isomorphic to $M^{\prime }$source, written $M\simeq M^{\prime }$source, if and only if there is a function $h:\left|M\right|\to \left|M^{\prime }\right|$source such that:

1. $h$source is injective: if $h\left(x\right)=h\left(y\right)$source then $x=y$source;

2. $h$source is surjective: for every $y\in \left|M^{\prime }\right|$source there is $x\in \left|M\right|$source such that $h\left(x\right)=y$source;

3. for every constant symbol $c$source: $h\left(c^M\right)=c^{M^{\prime }}$source;

4. for every $n$source-place predicate symbol $P$source:

   $$⟨a_1,\dots ,a_n⟩\in P^M\text{iff}⟨h\left(a_1\right),\dots ,h\left(a_n\right)⟩\in P^{M^{\prime }};$$source

5. for every $n$source-place function symbol $f$source:

   $$h\left(f^M\right(a_1,\dots ,a_n\left)\right)=f^{M^{\prime }}\left(h\right(a_1),\dots ,h(a_n\left)\right).$$source

Isomorphic structures are elementarily equivalent

If $M\cong M^{\prime }$source then $M\equiv M^{\prime }$source.

Proof

Let $h$source be an isomorphism of $M$source onto $M^{\prime }$source. For any assignment $s$source, $h\circ s$source is the composition of $h$source and $s$source, i.e., the assignment in $M^{\prime }$source such that $(h\circ s)\left(x\right)=h\left(s\right(x\left)\right)$source. By induction on $t$source and $A$source one can prove the stronger claims:

1. $h\left({⟦t⟧}^M\right[s\left]\right)={⟦t⟧}^{M^{\prime }}[h\circ s]$source.

2. $M,s\models A$source iff $M^{\prime },h\circ s\models A$source.

The first is proved by induction on the complexity of $t$source.

1. If $t\equiv c$source, then ${⟦c⟧}^M\left[s\right]=c^M$source and ${⟦c⟧}^{M^{\prime }}[h\circ s]=c^{M^{\prime }}$source. Thus, $h\left({⟦t⟧}^M\right[s\left]\right)=h\left(c^M\right)=c^{M^{\prime }}$source (by reference defn:iso-const of reference defn:isomorphism) $={⟦t⟧}^{M^{\prime }}[h\circ s]$source.

2. If $t\equiv x$source, then ${⟦x⟧}^M\left[s\right]=s\left(x\right)$source and ${⟦x⟧}^{M^{\prime }}[h\circ s]=h\left(s\right(x\left)\right)$source. Thus, $h\left({⟦x⟧}^M\right[s\left]\right)=h\left(s\right(x\left)\right)={⟦x⟧}^{M^{\prime }}[h\circ s]$source.

3. If $t\equiv f(t_1,\dots ,t_n)$source, then

   $$\begin{array}{cc}{⟦t⟧}^M\left[s\right]& =f^M\left({⟦t_1⟧}^M\right[s],\dots ,{⟦t_n⟧}^M[s\left]\right)\text{and}\\ {⟦t⟧}^{M^{\prime }}[h\circ s]& =f^{M^{\prime }}\left({⟦t_1⟧}^{M^{\prime }}\right[h\circ s],\dots ,{⟦t_n⟧}^{M^{\prime }}[h\circ s\left]\right).\end{array}$$source

   The induction hypothesis is that for each $i$source, $h\left({⟦t_i⟧}^M\right[s\left]\right)={⟦t_i⟧}^{M^{\prime }}[h\circ s]$source. So,

   $$\begin{array}{cc}h\left({⟦t⟧}^M\right[s\left]\right)& =h\left(f^M\right({⟦t_1⟧}^M\left[s\right],\dots ,{⟦t_n⟧}^M\left[s\right]\left)\right)\\ & =f^{M^{\prime }}\left(h\right({⟦t_1⟧}^M\left[s\right]),\dots ,h({⟦t_n⟧}^M\left[s\right]\left)\right)\\ & =f^{M^{\prime }}\left({⟦t_1⟧}^{M^{\prime }}\right[h\circ s],\dots ,{⟦t_n⟧}^{M^{\prime }}[h\circ s\left]\right)\\ & ={⟦t⟧}^{M^{\prime }}[h\circ s]\end{array}$$source

   Here, reference iso-1 follows by reference defn:iso-func of reference defn:isomorphism and reference iso-2 by induction hypothesis.

Part (b) is left as an exercise.

If $A$source is a sentence, the assignments $s$source and $h\circ s$source are irrelevant, and we have $M\models A$source iff $M^{\prime }\models A$source.

Exercise completing isomorphism invariance

Carry out the proof of (b) of reference thm:isom in detail. Make sure to note where each of the five properties characterizing isomorphisms of reference defn:isomorphism is used.

Definition of automorphism

An automorphism of a structure $M$source is an isomorphism of $M$source onto itself.

Exercise on automorphism-invariant definable sets

Show that for any structure $M$source, if $X$source is a definable subset of $M$source, and $h$source is an automorphism of $M$source, then $X=\{h\left(x\right):x\in X\}$source (i.e., $X$source is fixed under $h$source).

Definition of the theory of a structure

Given a structure $M$source, the theory of $M$source is the set $\mathrm{Th}\left(M\right)$source of sentences that are true in $M$source, i.e., $\mathrm{Th}\left(M\right)=\{A:M\models A\}$source.

The theory of a structure is complete

For any $M$source, $\mathrm{Th}\left(M\right)$source is complete.

Proof

For any sentence $A$source either $M\models A$source or $M\models \neg A$source, so either $A\in \mathrm{Th}\left(M\right)$source or $\neg A\in \mathrm{Th}\left(M\right)$source.

Models of a complete structural theory are elementarily equivalent

If $N\models A$source for every $A\in \mathrm{Th}\left(M\right)$source, then $M\equiv N$source.

Proof

Since $N\models A$source for all $A\in \mathrm{Th}\left(M\right)$source, $\mathrm{Th}\left(M\right)\subseteq \mathrm{Th}\left(N\right)$source. If $N\models A$source, then $N⊭\neg A$source, so $\neg A\notin \mathrm{Th}\left(M\right)$source. Since $\mathrm{Th}\left(M\right)$source is complete, $A\in \mathrm{Th}\left(M\right)$source. So, $\mathrm{Th}\left(N\right)\subseteq \mathrm{Th}\left(M\right)$source, and we have $M\equiv N$source.

Definition of partial isomorphism

Given two structures $M$source and $N$source, a partial isomorphism from $M$source to $N$source is a finite partial function $p$source taking arguments in $\left|M\right|$source and returning values in $\left|N\right|$source, which satisfies the isomorphism conditions from reference defn:isomorphism on its domain:

1. $p$source is injective;

2. for every constant symbol $c$source: if $p\left(c^M\right)$source is defined, then $p\left(c^M\right)=c^N$source;

3. for every $n$source-place predicate symbol $P$source: if $a_1$source, dots, $a_n$source are in the domain of $p$source, then $⟨a_1,\dots ,a_n⟩\in P^M$source if and only if $⟨p\left(a_1\right),\dots ,p\left(a_n\right)⟩\in P^N$source;

4. for every $n$source-place function symbol $f$source: if $a_1$source, dots, $a_n$source are in the domain of $p$source, then $p\left(f^M\right(a_1,\dots ,a_n\left)\right)=f^N\left(p\right(a_1),\dots ,p(a_n\left)\right)$source.

That $p$source is finite means that $\mathrm{dom}\left(p\right)$source is finite.

Definition of partial isomorphism between structures

Two structures $M$source and $N$source, are partially isomorphic, written $M{\cong }_{p}N$source, if and only if there is a non-empty set $I$source of partial isomorphisms between $M$source and $N$source satisfying the back-and-forth property:

1. (Forth) For every $p\in I$source and $a\in \left|M\right|$source there is $q\in I$source such that $p\subseteq q$source and $a$source is in the domain of $q$source;

2. (Back) For every $p\in I$source and $b\in \left|N\right|$source there is $q\in I$source such that $p\subseteq q$source and $b$source is in the range of $q$source.

Enumerable partially isomorphic structures are isomorphic

If $M{\cong }_{p}N$source and $M$source and $N$source are enumerable, then $M\cong N$source.

Proof

Since $M$source and $N$source are enumerable, let $\left|M\right|=\{a_0,a_1,\dots \}$source and $\left|N\right|=\{b_0,b_1,\dots \}$source. Starting with an arbitrary $p_0\in I$source, we define an increasing sequence of partial isomorphisms $p_0\subseteq p_1\subseteq p_2\subseteq \cdots$source as follows:

1. if $n+1$source is odd, say $n=2r$source, then using the Forth property find a $p_{n+1}\in I$source such that $p_n\subseteq p_{n+1}$source and $a_r$source is in the domain of $p_{n+1}$source;

2. if $n+1$source is even, say $n+1=2r$source, then using the Back property find a $p_{n+1}\in I$source such that $p_n\subseteq p_{n+1}$source and $b_r$source is in the range of $p_{n+1}$source.

If we now put:

we have that $p$source is a an isomorphism between $M$source and $N$source.

Exercise checking the back-and-forth union map

Show in detail that $p$source as defined in reference thm:p-isom1 is in fact an isomorphism.

Partial isomorphism implies elementary equivalence in relational languages

Suppose $M$source and $N$source are structures for a purely relational language (a language containing only predicate symbols, and no function symbols or constants). Then if $M{\cong }_{p}N$source, also $M\equiv N$source.

Proof

By induction on formulas, one shows that if $a_1$source, dots, $a_n$source and $b_1$source, dots, $b_n$source are such that there is a partial isomorphism $p$source mapping each $a_i$source to $b_i$source and $s_1\left(x_i\right)=a_i$source and $s_2\left(x_i\right)=b_i$source (for $i=1$source, dots, $n$source), then $M,s_1\models A$source if and only if $N,s_2\models A$source. The case for $n=0$source gives $M\equiv N$source.

Quantifier rank and n equivalence

For any formula $A$source, the quantifier rank of $A$source, denoted by $\mathrm{qr}\left(A\right)\in \mathbb{N}$source, is recursively defined as the highest number of nested quantifiers in $A$source. Two structures $M$source and $N$source are $n$source-equivalent, written $M{\equiv }_{n}N$source, if they agree on all sentences of quantifier rank less than or equal to $n$source.

Finitely many bounded-rank sentences

Let $L$source be a finite purely relational language, i.e., a language containing finitely many predicate symbols and constant symbols, and no function symbols. Then for each $n\in \mathbb{N}$source there are only finitely many first-order sentences in the language $L$source that have quantifier rank no greater than $n$source, up to logical equivalence.

Proof

By induction on $n$source.

Finite sequences over a structure domain

Given a structure $M$source, let ${\left|M\right|}^{<\omega }$source be the set of all finite sequences over $\left|M\right|$source. We use $a,b,c,\dots$source to range over finite sequences of elements. If $a\in {\left|M\right|}^{<\omega }$source and $a\in \left|M\right|$source, then $aa$source represents the concatenation of $a$source with $a$source.

Recursive back-and-forth relations on finite sequences

Given structures $M$source and $N$source, we define relations $I_n\subseteq {\left|M\right|}^{<\omega }\times {\left|N\right|}^{<\omega }$source between sequences of equal length, by recursion on $n$source as follows:

1. $I_0(a,b)$source if and only if $a$source and $b$source satisfy the same atomic formulas in $M$source and $N$source; i.e., if $s_1\left(x_i\right)=a_i$source and $s_2\left(x_i\right)=b_i$source and $A$source is atomic with all variables among $x_1$source, dots, $x_n$source, then $M,s_1\models A$source if and only if $N,s_2\models A$source.

2. $I_{n+1}(a,b)$source if and only if for every $a\in \left|M\right|$source there is a $b\in \left|N\right|$source such that $I_n(aa,bb)$source, and vice-versa.

Definition of back-and-forth equivalence at level n

Write $M{\approx }_{n}N$source if $I_n(⟨⟩,⟨⟩)$source holds of $M$source and $N$source (where $⟨⟩$source is the empty sequence).

Back-and-forth agreement preserves bounded-rank formulas

Let $L$source be a purely relational language. Then $I_n(a,b)$source implies that for every $A$source such that $\mathrm{qr}\left(A\right)\le n$source, we have $M,a\models A$source if and only if $N,b\models A$source (where again $a$source satisfies $A$source if any $s$source such that $s\left(x_i\right)=a_i$source satisfies $A$source). Moreover, if $L$source is finite, the converse also holds.

Proof

The proof that $I_n(a,b)$source implies that $a$source and $b$source satisfy the same formulas of quantifier rank no greater than $n$source is by an easy induction on $A$source. For the converse we proceed by induction on $n$source, using reference prop:qr-finite, which ensures that for each $n$source there are at most finitely many non-equivalent formulas of that quantifier rank.

For $n=0$source the hypothesis that $a$source and $b$source satisfy the same quantifier-free formulas gives that they satisfy the same atomic ones, so that $I_0(a,b)$source.

For the $n+1$source case, suppose that $a$source and $b$source satisfy the same formulas of quantifier rank no greater than $n+1$source; in order to show that $I_{n+1}(a,b)$source suffices to show that for each $a\in \left|M\right|$source there is a $b\in \left|N\right|$source such that $I_n(aa,bb)$source, and by the inductive hypothesis again suffices to show that for each $a\in \left|M\right|$source there is a $b\in \left|N\right|$source such that $aa$source and $bb$source satisfy the same formulas of quantifier rank no greater than $n$source.

Given $a\in \left|M\right|$source, let ${T^a}_n$source be set of formulas $B(x,y)$source of rank no greater than $n$source satisfied by $aa$source in $M$source; ${T^a}_n$source is finite, so we can assume it is a single first-order formula. It follows that $a$source satisfies $\exists x{T^a}_n(x,y)$source, which has quantifier rank no greater than $n+1$source. By hypothesis $b$source satisfies the same formula in $N$source, so that there is a $b\in \left|N\right|$source such that $bb$source satisfies ${T^a}_n$source; in particular, $bb$source satisfies the same formulas of quantifier rank no greater than $n$source as $aa$source. Similarly one shows that for every $b\in \left|N\right|$source there is $a\in \left|M\right|$source such that $aa$source and $bb$source satisfy the same formulas of quantifier rank no greater than $n$source, which completes the proof.

Finite back-and-forth equivalence matches bounded elementary equivalence

If $M$source and $N$source are purely relational structures in a finite language, then $M{\approx }_{n}N$source if and only if $M{\equiv }_{n}N$source. In particular $M\equiv N$source if and only if for each $n$source, $M{\approx }_{n}N$source .

Definition of dense linear ordering without endpoints

A dense linear ordering without endpoints is a structure $M$source for the language containing a single 2-place predicate symbol $<$source satisfying the following sentences:

1. $\forall x\neg x<x$source;

2. $\forall x\forall y\forall z(x<y\to (y<z\to x<z\left)\right)$source;

3. $\forall x\forall y(x<y\vee x=y\vee y<x)$source;

4. $\forall x\exists yx<y$source;

5. $\forall x\exists yy<x$source;

6. $\forall x\forall y(x<y\to \exists z(x<z\wedge z<y))$source.

Cantor isomorphism theorem for countable dense orders

Any two enumerable dense linear orderings without endpoints are isomorphic.

Proof

Let $M_1$source and $M_2$source be enumerable dense linear orderings without endpoints, with ${<}_1={<}^{M_1}$source and ${<}_2={<}^{M_2}$source, and let $I$source be the set of all partial isomorphisms between them. $I$source is not empty since at least $\varnothing \in I$source. We show that $I$source satisfies the Back-and-Forth property. Then $M_1{\cong }_p{M}_2$source, and the theorem follows by reference thm:p-isom1.

To show $I$source satisfies the Forth property, let $p\in I$source and let $p\left(a_i\right)=b_i$source for $i=1$source, dots, $n$source, and without loss of generality suppose $a_1{<}_1{a}_2{<}_1\cdots {<}_1{a}_n$source. Given $a\in \left|M_1\right|$source, find $b\in \left|M_2\right|$source as follows:

1. if $a{<}_1{a}_1$source let $b\in \left|M_2\right|$source be such that $b{<}_2{b}_1$source;

2. if $a_n{<}_{1}a$source let $b\in \left|M_2\right|$source be such that $b_n{<}_{2}b$source;

3. if $a_i{<}_{1}a{<}_1{a}_{i+1}$source for some $i$source, then let $b\in \left|M_2\right|$source be such that $b_i{<}_{2}b{<}_2{b}_{i+1}$source.

It is always possible to find a $b$source with the desired property since $M_2$source is a dense linear ordering without endpoints. Define $q=p\cup \{⟨a,b⟩\}$source so that $q\in I$source is the desired extension of $p$source. This establishes the Forth property. The Back property is similar. So $M_1{\cong }_p{M}_2$source; by reference thm:p-isom1, $M_1\cong M_2$source.

Exercise verifying the back property for dense orders

Complete the proof of reference thm:cantorQ by verifying that $I$source satisfies the Back property.