To ease the notation, we begin by introducing a few abbreviations.

Suppose that t is a term with variables among
u_{0} , … , u_{n-1}.

We might write t ( u_{0} , … , u_{n-1} )
or t ( u̅ ) to emphasize this.

Suppose that φ is a formula with free variables among
u_{0} , … , u_{n-1}.

We might write
φ ( u_{0} , … , u_{n-1} )
or φ ( u̅ ) to emphasize this.

Also, if we have a model A and x_{0} , … , x_{n-1}
∈ | A |, then we could write

A ⊨
φ ( u_{0} / x_{n-1} , … ,
u_{n-1} / x_{n-1} )

or

A ⊨ φ ( u̅ / x̅ )

instead of

( A , x_{0} , … , x_{n-1} )
⊨ φ (
u_{0} / c_{x0} )
⋅
⋅
⋅
( u_{n-1} / c_{xn-1} ).

Sometimes, if we are working with a fixed u̅, then we might abbreviate this further to just

A ⊨ φ ( x̅ )

but it is risky!

(We need both u̅ and x̅ to know which constant gets substituted for which variable.)

With these abbreviations, we can rewrite the result from Exercise 3.5 as follows.

Let π : A ≈ B be an isomorphism between structures.

Then, for every formula φ,
if φ has free variables u_{0}, … , u_{n-1},

then for all x̅ ∈ | A |^{n},

B
⊨
φ
( π ( x_{0} ) , … , π ( x_{n-1} ) )

iff

A
⊨
φ ( x_{0} , … , x_{n-1} ).

The usual way of expressing the conclusion of Lemma 4.1 is to say that
π is an __elementary embedding__ from A to B.
Thus every isomorphism is an elementary embedding.
The converse is false because elementary embeddings need not be surjections.

We have already seen two ways that structures might be related. At the end of the proof of Model Existence Theorem 3.14, we took the reduct of a structure in an expanded language to obtain a structure in the original language. In the exercises for Chapter 3, we defined isomorphism between structures and saw various instances and consequences. Here is another way to compare structures.

Let A and B be structures in the same language. We say that A is a substructure of B iff:

- | A | ⊆ | B |
- c
^{A}= c^{B}for every constant symbol c - F
^{A}= F^{B}↾ | A |^{n}for every n-ary function symbol F - R
^{A}= R^{B}∩ | A |^{n}for every n-ary function symbol R

(There is no risk of confusing this with "A is a subset of B" because A and B are assumed to be structures.)

Notice two things:

c^{B} ∈ | A | for every constant symbol c

F^{B} ( x̅ ) ∈ | A |
for every n-ary function symbol F and every x̅ ∈ | A |^{n}

In particular, not every subset of | B | is the universe of a substructure of B.

Let B be an infinite structure in a countable language.

Let X be a countable subset of | B |.

Then there exists a countable substructure A of B such that X ⊆ | A |.

First let Y = X ∪ { c^{B} ∣ c is a constant symbol }.

Define an increasing sequence of sets

Y = Z_{0}
⊆
Z_{1} ⊆
⋅
⋅
⋅
⊆
Z_{i} ⊆
⋅
⋅
⋅
⊆ | B |

by putting

Z_{i+1} =
Z_{i} ∪
{ F^{B} ( x̅ ) ∣
F is an n-ary function symbol and x̅ ∈
Z_{i}^{n} }.

By induction on i ∈ ω, we see that
Z_{i} is a countable subset of | B |.

Let Z = ∪_{i ∈ ω} Z_{i}.

Then Z is a countable subset of B.

And, c^{B} ∈ Z_{0} ⊆ Z
for every constant symbol c.

Also, for every n-ary function symbol F
and every x̅ ∈ Z^{n},
there exists i ∈ ω such that
x̅ ∈ Z_{i}^{n}
and
F^{B} ( x̅ ) ∈ Z_{i+1} ⊆ Z.

Therefore, F^{B} ↾ Z^{n}
is an n-ary function on Z.

Thus we obtain a countable substructure A of B by setting

| A | = Z

c^{A} = c^{B} for every constant symbol

F^{A} = F^{B} ↾ Z^{n}
for every n-ary function symbol F

R^{A} = R^{B} ∩ Z^{n}
for every n-ary function symbol R

**QED**

Let φ be a quantifier-free formula.

Say u̅ is an n-tuple of free variables of φ.

Let x̅ ∈ | A |^{n}.

Then A ⊨ φ ( u̅ / x̅ ) iff B ⊨ φ ( u̅ / x̅ )

First we claim that for every term t ( u̅ ) with n free variables,
if x̅ ∈ | A |^{n}, then
t ( u̅ / x̅ )^{A} =
t ( u̅ / x̅ )^{B} .

The proof of the claim is an easy induction using the assumption that A is a substructure of B.

Using this assumption again, we see that Lemma 4.3 holds for atomic formulas.

Now we complete the proof of Lemma 4.3 by induction.

The conjunction, disjunction, conditional and biconditional cases use the induction hypothesis and are trivial.

There is no quantifier case.

**QED**

In general, we cannot expect to do better than Lemma 4.3. For example, consider the structures

A = ( ℚ , 0 , 1 , + , × , < )
= ( | A | , c^{A} ,
d^{A} ,
F^{A} ,
G^{A} ,
R^{A} )

and

B
= ( ℝ , 0 , 1 , + , × , < )
= ( | B | , c^{B} ,
d^{B} ,
F^{B} ,
G^{B} ,
R^{B} )

Then A is a substructure of B.

However, because the square root of 2 is irrational,

A ⊨ ¬ ∃ u ( G ( u , u ) ≈ F ( d , d ) )

while

B ⊨ ∃ u ( G ( u , u ) ≈ F ( d , d ) )

But there are special situations in which we can do better than Lemma 4.3.

We say that A is an __elementary__ substructure of B
and write A ≼ B iff

for every formula φ
with n free variables u̅
and every
x̅ ∈ | A |^{n},

A ⊨ φ ( u̅ / x̅ ) iff B ⊨ φ ( u̅ / x̅ )

Let A be a substructure of B.

Assume that for every formula ψ with free variables u̅ and v, and every x̅ from | A |,

if B ⊨ ∃ v ψ ( u̅ / x̅ , v ), then there exists y ∈ | A | such that B ⊨ ψ ( u̅ / x̅ , v / y ).

Then A is an elementary substructure of B.

for every x̅ from | A |,

A ⊨ φ ( u̅ / x̅ ) iff B ⊨ φ ( u̅ / x̅ ).

Call this property (*).

Lemma 4.3 says (*) holds for φ which are quantifier free.

The induction hypothesis easily implies (*) holds for φ which are negations, conjunctions, disjunctions, conditionals or biconditionals.

Now consider the case in which φ is ∃ v ψ ( u̅ , v ).

First suppose that B ⊨ φ ( u̅ / x̅ ) where x̅ is from | A |.

By the assumption of Theorem 4.4, there exists y ∈ | A | such that B ⊨ ψ ( u̅ / x̅ , v / y ).

By the induction hypothesis, A ⊨ ψ ( u̅ / x̅ , v / y ).

Thus A ⊨ φ ( u̅ / x̅ ).

Now suppose that A ⊨ φ ( u̅ / x̅ ).

Then there exists y ∈ | A | such that A ⊨ ψ ( u̅ / x̅ , y ).

By the induction hypothesis, B ⊨ ψ ( u̅ / x̅ , y ).

Hence B ⊨ φ ( u̅ / x̅ ).

The final case in which φ is ∀ v ψ ( u̅ , v ) follows from what we have already proved.

**QED**

Let B be a structure in a countable language.

Let X be a countable subset of | B |.

Then there exists a countable elementary substructure A of B such that X ⊆ | A |.

We may assume that B is infinite.

For each formula φ ( u̅ , v ) with n+1 free variables,
choose a function f_{φ} : | B |^{n} → | B |
so that,

for every x̅ from B,
if B ⊨ ∃ v φ ( u̅ / x̅ , v ),
then
B ⊨ φ ( u̅ / x̅ , f_{φ} ( x̅ ) ).

(Since | B | is nonempty, we can give f_{φ} ( x̅ ) some default
value otherwise.)

Expand the language to include new n-ary function symbols F_{φ}.

Expand B to a structure B^{*} which interprets F_{φ}
as f_{φ}.

In other words,
F_{φ}^{B*} = f_{φ}.

By Lemma 4.2, B^{*} has a countable substructure
A^{*}
such that
X ⊆ | A^{*} |.

Let A be the reduct of A^{*} to the language of B.

Clearly A is a substructure of B.

Also clear is that A passes the Tarski-Vaught Test for being an elementary substructure of B.

**QED**

Consider a structure A.

As usual,
we let c_{x} be a new constant symbol for each x ∈ | A |.

Expand A to a structure D = ( A , x )_{x ∈ | A |}
that interprets c_{x} by x.

In other words,
D is the expansion of A with c_{x}^{D} = x
for every x ∈ | A |.

By the __elementary diagram__ of A we mean the theory
Diagram ( A ) = { φ ∣ D ⊨ φ }.

Obviously, D ⊨ Diagram ( A ).

In the expanded language, Diagram ( A ) is a complete theory and closed under deduction.

Let A be a structure and D = ( A , x )_{x ∈ | A |}.

Suppose that E is a model of Diagram ( A ).

Let B be the reduct of E to the language of A.

Then the map π : x → c_{x}^{E}
is an isomorphism from A to an elementary substructure A^{*} of B.

**Claim A**

Let d be a constant symbol in the expanded language.

Then π ( d^{D} ) = d^{E}.

Then the sentence d ≈ c_{x} belongs to Diagram ( A ).

Hence E ⊨ d ≈ c_{x}.

Thus d^{E} = c_{x}^{E}
= π ( x ) = π ( d^{D} ) .

**Claim B**

Let F be an arbitrary n-ary function and x̅ ∈ | A |^{n}.

Then
π ( F^{D} ( x̅ ) )
= F^{E}
( π ( x_{0} ) , … , π ( x_{n-1} ) ).

**Proof of Claim B**

Let y = F^{D} ( x̅ ).

Then D ⊨ c_{y} ≈
F ( c_{x0} , … , c_{xn-1} ).

So the sentence
c_{y} ≈ F ( c_{x0} , … ,
c_{xn-1} )
belongs to Diagram ( A ).

Hence
E ⊨
c_{y} ≈
F ( c_{x0} , … , c_{xn-1} ).

In other words,
c_{y}^{E} =
F^{E} ( c_{x0}^{E} , … ,
c_{xn-1}^{E} ).

Equivalently,
π ( y ) =
F^{E} ( π ( x_{0} ) , … , π ( x_{n-1} ) ).

**Claim C**

We may define a substructure D^{*} of E by setting:

D^{*} = ran ( π )

c^{D*} = c^{E}
for every constant symbol c in the expanded language.

F^{D*} =
F^{D*} ↾ | ran ( π ) |^{n}
for every n-ary function symbol F.

R^{D*} =
R^{D*} ∩ | ran ( π ) |^{n}
for every n-ary relation symbol R.

**Proof of Claim C**

Immediate from Claims A and B.

**Claim D**

π is an injection.

**Proof of Claim D**

Let x, y ∈ | A | such that x ≠ y.

Then D ⊨ c_{x} ≉ c_{y}.

So the sentence c_{x} ≉ c_{y} belongs to Diagram ( A ).

Hence E ⊨ c_{x} ≉ c_{y}.

Thus π ( x ) = c_{x}^{E} ≠
c_{y}^{E} = π ( y ).

**Claim E**

Let R be an arbitrary n-ary function and x̅ ∈ | A |^{n}.

Then
R^{D} ( x̅ )
iff
R^{E}
( π ( x_{0} ) , … , π ( x_{n-1} ) ).

**Proof of Claim E**

Similar to the proofs above.

Let A^{*} be the reduct of D^{*}
to the language of A.

**Claim F**

π : A ≈ A^{*}
and
π : D ≈ D^{*}

**Proof of Claim F**

π is a bijection from | A | = | D |
to | A^{*} | = | A^{*} |
by Claim D.

π preserves constants, functions and relations by Claims A, B and E.

**Claim G**

Let φ ( u̅ ) be a formula in the language of A.

Let x̅ ∈ | A |^{n}.

Then the following are equivalent.

- A ⊨ φ ( x
_{0}, … , x_{n-1}) -
D ⊨ φ
( u
_{0}/ c_{x0}, … , u_{n-1}/ c_{xn-1}) -
E ⊨
φ ( u
_{0}/ c_{x0}, … , u_{n-1}/ c_{xn-1}) -
( B , π ( x
_{0}) , … , π ( x_{n-1}) ) ⊨ φ ( u_{0}/ c_{π ( x0 )}, … , u_{n-1}/ c_{π ( xn-1 )}) -
B ⊨
φ (
π ( x
_{0}) , … , π ( x_{n-1}) )

In particular, π is an elementary embedding from A to B.

**Proof of Claim G**

Condition 1 is an abbreviation for Condition 2.

Condition 5 is an abbreviation for Condition 4.

Condition 2 holds iff the sentence
φ ( u_{0} / c_{x0} , … ,
u_{n-1} / c_{xn-1} )
belongs to Diagram ( A ).

The same is true of the Condition 3, so it is equivalent to Condition 2.

The meaning of the fourth condition needs some elaboration.

Imagine that we have just one x instead of an n-tuple x̅.

which is interpreted as π ( x ) in ( E , π ( x ) ).

In other words,
c_{π ( x )}^{( E , π ( x ) ) }
= π ( x )

By definition, π ( x ) =
c_{x}^{E}.

Thus,
c_{x}^{E}
=
c_{π ( x )}^{( E , π ( x ) ) } .

In other words,
( E , π ( x ) ) ⊨
c_{x} ≈
c_{π ( x )}.

By Substitution Lemma 3.2,
we conclude that ( E , π ( x ) ) ⊨
φ ( u /
c_{x} ) ↔
φ ( u /
c_{π ( x )} ) .

Note that φ ( u /
c_{x} ) is a sentence in the language of E.

Also that φ ( u /
c_{π ( x )} )
is a sentence in the language of ( B , π ( x ) ).

And both E and ( B , π ( x ) ) are reducts of ( E , π ( x ) ).

Therefore,
E ⊨ φ ( u / c_{x} )
iff
( B , π ( x ) ) ⊨ φ ( u / c_{π ( x )} ) .

This shows Conditions 3 and 4 are equivalent when n = 1.

For n > 1 make the obvious changes.

**Claim H**

A^{*} ≼ B.

**Proof of Claim H**

Let φ ( u̅ ) be a formula in the language of A^{*},
which is the language of A.

Let x̅ ∈ | A |.

Then

A^{*} ⊨ φ ( π ( x_{0} ) , … ,
π ( x_{n-1} ) )

iff (by Claim F and Lemma 4.1)

A ⊨ φ ( x_{0} , … ,
x_{n-1} )

iff (by Claim G)

B ⊨ φ ( π ( x_{0} ) , … ,
π ( x_{n-1} ) ).

**
QED
**

It is worth noting that, in the proof of Lemma 4.6, we could have proved Claim G first, then used it to prove Claims A, B, D and E by considering the four formulas:

u ≈ d

F ( u̅ ) ≈ v

u ≉ v

R ( u̅ )

Each infinite structure has a proper elementary extension.

Let d be a new constant.

Let Σ be the theory
Diagram ( A ) ∪
{ d ≉ c_{x} ∣ x ∈ | A | }.

We claim that Σ has a model.

By Compactness Theorem 3.16, it suffices to show every finite subtheory of Σ has a model.

Consider any x_{0} , … , x_{n-1} ∈ | A |.

Since | A | is infinite,
there exists y ∈ | A | such that y ≠ x_{i} for all i < n.

Let B be the expansion of ( A , x̅ ) that interprets d as y.

Then B ⊨
Diagram ( A ) ∪
{ d ≉ c_{x} ∣ x = x_{0} , …
, x_{n-1} }.

This proves the claim.

Let E be a model of Σ

By Lemma 4.6, we have
π : A ≈ A^{*} ≼ B
where B is the reduct of E to the language of A
and π : x ↦ c_{x}^{E}.

Let T = | B | - | A^{*} |.

As E is a model of Σ we have that d^{E} ∈ T.

In particular, T is nonempty.

We can "replace" each y ∈ T with a distinct x that does not belong to | A |.

More precisely, there is a set S that is disjoint from | A | together with a bijection f : S → T.

Let σ = π ∪ f.

In other words, σ ( x ) = π ( x ) if x ∈ | A | and σ ( x ) = f ( x ) if x ∈ S.

Then σ : | A | ∪ S → | B | is a bijection and σ ↾ | A | = π.

Next we define a structure B' such that σ : B' ≈ B.

There is only one obvious way to do this and it works!

Consider any x̅ ∈ | A |^{n}
and formula φ with n free variables.

Then

A ⊨ φ ( x̅ )

iff ( by Lemma 4.1 )

A^{*} ⊨ φ (
π ( x_{0} ) , … , π ( x_{n-1} ) )

iff
( since A^{*} ≼ B )

B ⊨ φ (
π ( x_{0} ) , … , π ( x_{n-1} ) )

iff ( since σ : B' ≈ B )

B' ⊨ φ (
σ^{-1} ( π ( x_{0} ) ) , … ,
σ^{-1} ( π ( x_{n-1} ) ) )

iff ( since σ ↾ | A | = π )

B' ⊨ φ ( x̅ )

The equivalence between the first and final lines of the calculation above directly implies that A is an elementary substructure of B'.

**QED**

Each infinite structure has an uncountable elementary extension.

{ d ≉ c_{x} ∣ x ∈ | A | and d is a new constant }
∪
{ d ≉ e ∣ d and e are distinct new constants }.

Then every finite subset of Σ has a model.

To see this, consider any
x̅ ∈ | A |^{m}
and
new constants d_{0} , … , d_{n-1}.

Pick distinct
y_{0} , … , y_{n-1} ∈ | A | -
{ x_{0} , … , x_{m-1} }.

Let B be the expansion of ( A , x̅ ) which interprets
d_{j} as y_{j} for all j < n.

Then B is a model of the union of Diagram ( A ) with

{ d_{j} ≉ c_{xi} ∣ i < m and j < n }
∪
{ d_{i} ≉ d_{j} ∣ i , j < n and i ≠ j }.

By Compactness Theorem 3.16, Σ has a model E.

The rest of the proof is identical to that of Lemma 4.7.

**QED**

The theory DLO consists of the following sentences.

∀ u ¬ R ( u , u )

∀ u ∀ v ∀ w ( ( R ( u , v ) ∧ R ( v , w ) ) → R ( u , w ) )

∀ u ∀ v ( R ( u , v ) ∨ u ≈ v ∨ R ( v , u ) )

∀ u ∀ w ( R ( u , w ) → ∃ v ( R ( u , v ) ∧ R ( v , w ) ) )

∀ u ∃ v R ( v , u )

∀ u ∃ v R ( u , v )

The models of DLO are dense linear orderings without endpoints.

The most familiar examples are ( ℚ , < ) and ( ℝ , < ).

These structures are not isomorphic because ℚ is countable while ℝ is uncountable so there is no bijection between them.

Another example is the unit interval ( { x ∈ ℝ ∣ 0 < x < 1 } , < ).

The function x ↦ tan ( ( x - ( 1 / 2 ) ⋅ π ) is an order preserving bijection from the unit interval to the real line. In other words, an isomorphism.

Here are a few more dense linear orderings without endpoints:

( { x ∈ ℚ ∣ 0 < x < 1 } , < )

( { x ∈ ℝ ∣ x ≠ 0 } , < )

( { x ∈ ℚ ∣ x < 0 } ∪ { x ∈ ℝ ∣ 0 < x } , < )

( { x ∈ ℝ ∣ x ∉ ℤ } , < )

( { x ∈ ℝ ∣ x ∉ ℚ } , < )

Notice that if A is a structure in a this (or any) relational language, then every subset of | A | is the universe of a substructure of A. We introduce the notation A ↾ S = ( S , R ∩ ( S × S ) ) whenever S is a subset of | A |.

Obviously, every dense linear ordering without endpoints is infinite. So A ↾ S is definitely not a model of DLO if S is finite.

The first result in this section is often taught in courses on analysis, as well as courses on set theory. It is due to Georg Cantor. The proof technique, known as a "back and forth" argument, has many applications throughout mathematics.

Let A and B be countable models of DLO.

Let S and T be finite subsets of A and B respectively.

Suppose f : A ↾ S ≈ B ↾ T.

Then there exists a π : A ≈ B such that π ↾ S = f.

In particular, A and B are isomorphic.

Let i ↦ b_{i} be a bijection from ω to | B |.

By recursion on n, we will define

- a finite S
_{n}⊂ | A | such that S_{i}∪ { a_{i}} ⊆ S_{n}for all i < n, - a finite T
_{n}⊂ | B | such that T_{i}∪ { b_{i}} ⊆ T_{n}for all i < n and -
an isomorphism f
_{n}: A ↾ S_{n}≈ B ↾ T_{n}such that f_{n}↾ S_{i}= f_{i}for all i < n.

Let S_{0} = S, T_{0} = T and f_{0} = f.

Assume we have defined appropriate
S_{i} , T_{i} and f_{i}
for all i ≤ n.

Based on this, we must define appropriate
S_{n+1} , T_{n+1} and f_{n+1}.

List S_{n} in increasing order according to R^{A} as

x_{0} R^{A} x_{1} R^{A} ⋅ ⋅ ⋅ R^{A} x_{k-1}

where k is the size of S_{n}.

List
T_{n} in increasing order according to R^{B} as

y_{0} R^{B} y_{1} R^{B} ⋅ ⋅ ⋅ R^{B} y_{k-1}.

Since f_{n} is an isomorphism,
it must be that
y_{i} = f_{n} ( x_{i} ) for all i < k.

First we decide the value of f_{n+1} ( a_{n} ).

There are four cases:

**Case 1.** a_{n} R^{A} x_{i} for all i < k.

Since B has no left endpoint, there exists b ∈ | B | such that
b R^{B} y_{i} for all i < k.

Pick any such b and make f_{n+1} ( a_{n} ) = b.

**Case 2.** x_{i} R^{A} a_{n} for all i < k.

Since B has no right endpoint, there exists b ∈ | B | such that
y_{i} R^{B} b for all i < k.

Pick any such b and make f_{n+1} ( a_{n} ) = b.

**Case 3.** x_{i} R^{A} a_{n} R^{A} x_{j} for some i < j < k.

Let i be as large as possible and j be as small as possible.

Since B is dense, there exists b ∈ | B | such that
y_{i} R^{B} b R^{B} y_{j}.

Pick any such b and make f_{n+1} ( a_{n} ) = b.

**Case 4** a_{n} = x_{i} for some i < k.

In this case, we let b = y_{i}
and f_{n+1} ( a_{n} ) = b.

Second, we decide the value of f_{n+1}^{-1} ( b_{n} ).

For this, we
list S_{n} ∪ { a_{n} } in increasing order
according to R^{A} as

x^{*}_{0} R^{A} x^{*}_{1} R^{A} ⋅ ⋅ ⋅
R^{A} x^{*}_{k-1}
R^{A} x^{*}_{k}

and T_{n} ∪ { b } in increasing order
according to R^{B} as

y^{*}_{0} R^{B} y^{*}_{1} R^{B} ⋅ ⋅ ⋅
R^{B} y^{*}_{k-1}
R^{B} y^{*}_{k}

There are four cases:

**Case 1.** b_{n} R^{B} y^{*}_{i} for all i ≤ k.

Since A has no left endpoint, there exists a ∈ | A | such that
a R^{A} x^{*}_{i} for all i ≤ k.

Pick any such a and make f_{n+1}^{-1} ( b_{n} ) = a.

**Case 2.** y^{*}_{i} R^{B} b_{n} for all i ≤ k.

Since A has no right endpoint, there exists a ∈ | A | such that
x^{*}_{i} R^{A} a for all i ≤ k.

Pick any such a and make f_{n+1}^{-1} ( b_{n} ) = a.

**Case 3.** y^{*}_{i} R^{B} b_{n} R^{B} y^{*}_{j} for some i < j ≤ k.

Let i be as large as possible and j be as small as possible.

Since A is dense, there exists a ∈ | A | such that
x^{*}_{i} R^{A} a R^{A} x^{*}_{j}.

Pick any such a and make f_{n+1}^{-1} ( b_{n} ) = a.

**Case 4** b_{n}
= y^{*}_{i} for some i ≤ k.

In this case, we let a = x^{*}_{i}
and f_{n+1}^{-1} ( b_{n} ) = a.

To finish the recursive construction, put

S_{n+1} = S_{n} ∪ { a_{n} , a } = dom ( f_{n+1} )

and

T_{n+1} = T_{n} ∪ { b_{n} , b } = ran ( f_{n+1} )

We have already determined the values of f_{n+1} on these
sets in a way that preserves order.
And we defined f_{n+1} to extend f_{n}.

Now we finish the proof of the theorem.

Clearly, | A | is the union of the sets S_{n} for n < ω.

Also, | B | is the union of the sets T_{n} for n < ω.

So we can define a function π : | A | → | B | by setting
π ( a_{n} ) = f_{n+1} ( a_{n} ).

To see that π is an injection, note that if m < n, then

π ( a_{m} )
= f_{m+1} ( a_{m} )
= f_{n+1} ( a_{m} )
≠
f_{n+1} ( a_{n} )
= π ( a_{n} ).

To see that π is a surjection,
note that if
a_{m} = f_{n+1}^{-1} ( b_{n} )
and
k = max ( m , n ),
then

π ( a_{m} )
= f_{m+1} ( a_{m} )
= f_{k+1} ( a_{m} )
= f_{n+1} ( a_{m} )
= b_{n}.

To see that π is order preserving, note that if k = max ( m , n ), then

a_{m} R^{A} a_{n}
iff
f_{k+1} ( a_{m} ) R^{B} f_{k+1} ( a_{n} )
iff
f_{m+1} ( a_{m} ) R^{B} f_{n+1} ( a_{n} )
iff
π ( a_{m} ) R^{B} π ( a_{n} ).

**QED**

A theory Σ is __countably categorical__ iff
all pairs of countable models of Σ are isomorphic.

DLO is countably categorical by Theorem 4.9.

This does not extend to uncountable models of DLO.

For example, even though there is a bijection between ℝ and { x ∈ ℝ ∣ x ≠ 0 }, the structures ( ℝ , < ) and ( { x ∈ ℝ ∣ x ≠ 0 } , < ) are not isomorphic.

(See the exercises for Chapter 4.)

A structure A is __homogeneous__ iff
every isomorphism between finite substructures of A extends
to an isomorphism from A to A.

Every countable model of DLO is homogeneous by Theorem 4.9.

DLO is a complete theory.

Let A and B be models of DLO such that A ⊨ φ and B ⊨ ¬ φ.

By Downward Löwenheim-Skolem Theorem 4.5,
there are countable elementary substructures
A^{*} of A and B^{*} of B.

Then
A^{*} ⊨ φ and B^{*} ⊨ ¬ φ.

By Theorem 4.9,
A^{*} and B^{*} are isomorphic.

By Lemma 4.1,
A^{*} and B^{*} satisfy exactly the same sentences,
which is a contradiction.

**QED**

Let φ be a formula whose free variables are among u̅
= ( u_{0} , … , u_{n-1} ).

Then there exists a quantifier-free formula ψ such that

DLO ⊢ ∀ u̅ ( φ ↔ ψ )

For x̅ ∈ | A |^{n},
define type ( x̅ ) to be the set of formulas ψ
such that

- ψ is either atomic or negation of atomic,
- the free variables of ψ are among u̅ and
- A ⊨ ψ ( u̅ / x̅ ).

Then type ( x̅ ) is finite for each x̅ ∈ | A |^{n}.

The set { type ( x̅ ) ∣ x̅ ∈ | A |^{n} } is also finite.

**Fact A. ** If type ( x̅ ) = type ( y̅ ),
then:

- The map x
_{i}↦ y_{i}is an isomorphism from A ↾ { x_{i}∣ i < n } to A ↾ { y_{i}∣ i < n }. - By Theorem 4.9,
there is an automorphism π
of A such that π ( x
_{i}) = y_{i}. for all i < n. - By Lemma 4.1,
for every formula χ whose free variables are among u̅,
A ⊨ χ ( x̅ ) iff A ⊨ χ ( y̅ ).

Assume for now that S is nonempty.

T is finite; say T = { τ_{0} , … , τ_{k-1} }.

Each τ_{i} is finite
so we may let δ_{i} ( u̅ ) be the conjunction of
all the formulas in τ_{i}.

Let
ψ ( u̅ ) be the disjunction of the formulas
δ_{i} ( u̅ ) for i < k.

If S is empty, then let ψ be ⊥.

Either way, ψ is quantifier-free.

Now, for all x̅ ∈ | A |^{n},

A ⊨ φ ( x̅ ) iff x̅ ∈ S iff type ( x̅ ) ∈ T iff A ⊨ ψ ( x̅ ).

The forward direction is obvious. The reverse direction uses Fact A, part 3.

Thus A ⊨ ∀ u̅ ( φ ↔ ψ )

Theorem 4.10 and the Completeness Theorem 3.15 imply that every sentence satisfied by A is satisfied by every model of DLO and, therefore, is deducible from DLO.

**QED**

A theory is said to admit __quantifier elimination__
if every formula is provably equivalent to a quantifier-free formula.

Thus DLO admits quantifier elimination by Theorem 4.11.

At the beginning of this section, we said that ℚ is countable while ℝ is uncountable, so there is no bijection between them.

Another reason that ( ℚ , < ) and ( ℝ , < ) are not isomorphic is that ( ℝ , < ) has the least upper bound property but ( ℚ , < ) does not.

For example, if S = { x ∈ ℚ ∣ x^{2} < 2 },
then S does not have a least upper bound in ℚ whereas
lub ( S ) = √2
in ℝ

Consider an arbitrary linear ordering A.

If S ⊆ | A | and y ∈ | A |,
then y is an __upper bound__ for S in A iff
x R^{A} y or x = y for every x ∈ | A |.

y is the __least upper bound__ for S iff
y is an upper bound for S and
y R^{A} z or y = z
for every upper bound z for S.

A has the __least upper bound property__ iff
for every nonempty S ⊆ | A |,
if S has an upper bound, then S has a least upper bound.

It is a basic fact about ( ℝ , < ) that it has the least upper bound property.

Another basic fact is that between any two real numbers, there is a rational number. This says ℚ is dense in ℝ.

Our collection of facts characterizes ( ℝ , < ) up to isomorphism in the following strong sense.

Let A and B be models of DLO.

Assume that A is a countable substructure of B.

Assume that A is dense in B in the sense that
for all x , z ∈ | B |,
there exists y ∈ | A | such that x R^{B} y R^{B} z.

Assume that B has the least upper bound property.

Let π be an isomorphism from A to ( ℚ , < ).

Then there is an isomorphism σ from B to ( ℝ , < ) such that σ ↾ | A | = π.

σ ( y ) = lub ( { π ( x ) ∣ x ∈ | A |
and
x R^{B} y } )

where the least upper bound is taken in ( ℝ , < ).

**QED**

Let A be any of the "standard" structures whose universe is the set of real numbers.

For example, A might be the dense linear ordering

( ℝ , < ).

Or, we might include some important subsets as unary predicates:

( ℝ , ℚ , ℤ , < ) .

We might also include some popular functions:

( ℝ , + , - , x , ÷ , ℚ , ℤ , < )

where division is modified to be a total function on ℝ × ℝ.

Or more functions and related constants:

( ℝ , e , π , + , - , x , ÷ , exp , log , sin , arcsin , ℚ , ℤ , < )

where logarithm and arcsine are modified to be total functions.

In fact, we could include all constants, functions and relations should we be willing to move to an uncountable language.

Much like in the proof of Lemma 4.7, let d be a new constant symbol
and
Σ =
Diagram ( A ) ∪
{ c_{x} < d ∣ x ∈ | A | }.

We are abusing notation here by using < as a binary relation symbol.

When we want to refer to the usual ordering of ℝ we will write
<^{A}.

Also, we are writing c_{x} R d rather than R ( c_{x} , d ).

Like in the proof of Lemma 4.7, we find E ⊨ Σ and let B be the reduct of E to the language of A.

Also, we define π : x ↦ c_{x}^{E}
and find A^{*} ≼ B such that π : A ≈ A^{*}.

We have that for every formula φ ( u̅ ) in the language of A,

A ⊨ φ ( u_{0} / c_{x0} , … ,
u_{n-1} / c_{xn-1} )
iff
A^{*} ⊨
φ ( u_{0} / c_{π ( x0 )} , … ,
u_{n-1} / c_{π ( xn-1 ) } )
iff
B ⊨
φ ( u_{0} / c_{π ( x0 )} , … ,
u_{n-1} / c_{π ( xn-1 ) } )

Since A^{*} is isomorphic to A,
we consider A^{*} standard too.

Even though B satisfies all the same sentences as A^{*},
it is not isomorphic to A so we think of B as nonstandard.

To start to see how different B is from A,
recall that B has a member d^{E} which is greater than
every member of A^{*}.

Define Finite ( B ) to be the set of y ∈ B such that there
exist x , z ∈ A^{*} with x <^{B} y <^{B} z.

Also, define Infinite ( B ) = | B | - Finite ( B ).

Then d^{E} ∈ Infinite ( B )
because E ⊨ Σ.

Let us abuse notation by assuming that 0 and 1 are constant symbols that A interprets as the numbers zero and one respectively.

So
0^{A*} = 0^{B} = π ( 0^{A} )
and
1^{A*} = 1^{B} = π ( 1^{A} ).

Let

Positive ( A^{*} ) = { x ∈ | A^{*} |
∣ 0^{A*} <^{A*} x }
= { π ( x )
∣ x ∈ ℝ and 0^{A} <^{A} x }

and

Positive ( B ) = { x ∈ B ∣ 0^{B} <^{B} x }.

Then

Positive ( A^{*} ) ⊂ Positive ( B )
but
d^{E} ∈ Positive ( B ) - Positive ( A^{*} ).

Abuse notation more by assuming that A has binary function symbols + , - , × and ÷ which A interprets as addition, subtraction, multiplication and division. Also, A has a unary functions symbol written using the strange notation | ⋅ | which A interprets as absolute value.

(We make some reasonable convention on the value of
x ÷^{A} 0^{A}
so that ÷^{A} is a total binary function.)

Now A satisfies the first-order versions of the sentences "if 1 < x < y, then 0 < 1/y < 1/x" and "if z ≠ 0, then z = 1/(1/z)".

So A^{*} and B do too.

In particular, we see that if we let

ε = 1^{B} ÷^{B} d^{E},

then

0^{B} <^{B} ε
<^{B} x

for every x ∈ Positive ( A^{*} ).

For δ ∈ | B |,
we say that δ is an __infinitesimal__
iff
0^{B} <^{B}
| δ |^{B} <^{B} x
for every x ∈ Positive ( A^{*} ).

(Here | δ |^{B} is the absolute value of δ
computed in B.)

Above we saw that ε is a positive infinitesimal of B
because it is positive but less than every positive member of | A^{*} |.

In fact, we showed that the reciprocal of any positive infinite member of B is a positive infinitesimal member of B.

You might have heard or seen the word
"infinitesimal" used in your calculus course
but the teacher or textbook almost certainly did not justify its use
with logic! In fact, infinitesimals were introduced by
Gottfried Wilhelm Leibniz
with a kind of cook book recipe for how to use them in calculations.
Isaac Newton
discovered a similar calculus around the same time.
Their methods were used to make correct predictions about physics
and astronomy but were very controversial. After all, there are no real
numbers greater than zero but smaller than every positive real number!
About four hundred years later,
Abraham Robinson
discovered this way of thinking about infinitesimals as nonstandard
real numbers
and used this to explain why calculations that involve infinitesimals
can be used to make accurate statements about real numbers.
It all boils down to π : A ≈ A^{*} ≼ B.

More information about B can be found in the exercises for this chapter.

Let φ ( u̅ , v̅ ) be a quantifier-free formula.

Let x̅ be from | A |.

Then B ⊨ ∀ v̅ φ ( u̅ / x̅ ) implies A ⊨ ∀ v̅ φ ( u̅ / x̅ )

Then B ⊨ φ ( u̅ / x̅ , v̅ / y̅ ) for all y̅ from | B |.

By Lemma 4.3, A ⊨ φ ( u̅ / x̅ , v̅ / y̅ ) for all y̅ from | A |.

Therefore A ⊨ ∀ v̅ φ ( u̅ / x̅ ).

**QED**

Formulas of the form ∀ v̅ φ where φ
is quantifier-free are called __universal__.

A theory is __universal__ iff all of its axioms are universal sentences.

Let Σ be a theory.

Let Σ^{ ∀} =
{ φ ∣ φ is universal and Σ ⊨ φ }.

The following are equivalent.

1) For all structures A and B, if B ⊨ Σ and A ⊆ B, then A ⊨ Σ.

2)
Σ and Σ^{ ∀}
have exactly the same models.

Assume that 1) holds.

Obviously, if A ⊨ Σ, then
A ⊨ Σ^{ ∀}.

Assume A ⊨ Σ^{ ∀}.

Let Δ be the __atomic diagram__ of A, by which we mean
the set of sentences of the form

ψ (
u_{0} / c_{x0} , … ,
u_{n-1} / c_{xn-1} )

or

¬ ψ (
u_{0} / c_{x0} , … ,
u_{n-1} / c_{xn-1} )

that are satisfied by A
where
ψ is atomic and x̅ ∈ | A |^{n}.

In other words, Δ = Diagram ( A ) ∩ { φ ∣ φ is atomic or negation of atomic }.

**Claim A**

Suppose that E is a model of Δ.

Let B be the reduct of E to the language of A.

Then the map π : x → c_{x}^{E}
is an isomorphism from A to a substructure A^{*} of B.

**Proof of Claim A**

Just repeat the proof of Lemma 4.6 through Claims A-F.

**Claim B**

Every finite subtheory of Σ ∪ Δ is consistent.

**Proof of Claim B**

Suppose otherwise.

Then there are sentences φ_{0} , …
, φ_{k} in Δ
such that

Σ ⊢
¬ ( φ_{0} ∧ ⋅ ⋅ ⋅
∧ φ_{k} ).

Pick an n-tuple of variables u̅ and x̅ ∈ | A |^{n}
such that

φ_{i} =
χ_{i}
( u_{0} / c_{x0} ,
... , u_{n-1} / c_{xn-1} ).

for all i < k
where each χ_{i} is a formula in the language of A.

(Each χ_{i} is atomic or negation of atomic
and has free variables among u̅.)

Let ψ be χ_{0} ∧ ⋅ ⋅ ⋅
∧ χ_{k}.

Then

Σ ⊢ ¬ ψ
( u_{0} / c_{x0} ,
… , u_{n-1} / c_{xn-1} ).

By the Generalization Theorem 3.6,

Σ ⊢ ∀ u̅ ¬ ψ.

Therefore, ∀ u̅ ¬ ψ belongs to Σ^{ ∀}.

So A ⊨ ∀ u̅ ¬ ψ.

Hence
A ⊨ ¬ ψ
( u_{0} / c_{x0} ,
… , u_{n-1} / c_{xn-1} ).

In other words,
A ⊨ ¬ ( φ_{0} ∧ ⋅ ⋅ ⋅
∧ φ_{k} ).

But this contradicts that A ⊨ Δ
and every φ_{i} belongs to Δ.

Now Claim B and the Compactness Theorem imply that Σ ∪ Δ has a model E.

By Claim A, there is a model B of Σ and
there is a substructure A^{*}
of B such that A is isomorphic to A^{*}.

Then A^{*} is a model of Σ since we assumed 1).

By Lemma 4.1, A is a model of Σ

**QED**

∀ u R ( u , u )

∀ u ∀ v R ( u , v ) → R ( v , u )

∀ u ∀ v ∀ w ( ( R ( u , v ) ∧ R ( v , w ) ) → R ( u , w ) )

The theory of unary injections:

∀ u ∀ v ( u ≉ v → f ( u ) ≉ f ( v ) )

The theory of linear orderings:

∀ u ¬ R ( u , u )

∀ u ∀ v ∀ w ( ( R ( u , v ) ∧ R ( v , w ) ) → R ( u , w ) )

∀ u ∀ v ( R ( u , v ) ∨ u ≈ v ∨ R ( v , u ) )

Appropriately:

DLO, which we studied in § 4.3, is not universal because of the "density" and "no endpoints" axioms.

The theory of a unary surjection is not universal:

∀ v ∃ u F ( u ) = v

The theory of groups is not universal:

∀ u ∀ v ∀ w F ( F ( u , v ) , w ) ≈ F ( u , F ( u , w ) )

∀ u ( F ( c , u ) ≈ u ∧ F ( u , c ) ≈ u )

∀ u ∃ v ( F ( u , v ) ≈ c ∧ F ( v , u ) ≈ c )

Notice that the three theories listed above have axioms of the form ∀ ∃ φ where φ is quantifier-free.

(Some axioms have no alternations of quantifiers but we could add dummy quantifiers if we wanted.)

We begin this section with half of a characterization of ∀ ∃ theories that is analogous to how Theorem 4.14 characterized ∀ theories.

But first we need to introduce another important model theoretic construction: unions of chains.

A __chain__ of structures is a sequence

A_{0} ⊆
A_{1} ⊆
⋅ ⋅ ⋅ ⊆
A_{i} ⊆
A_{i+1} ⊆
⋅ ⋅ ⋅

where, as we have indicated, A_{i} is substructure of A_{i+1}.

Given such a chain,
we define its __union__ to be the structure B with:

| B |
=
∪_{i ∈ ω} | A_{i} |

c^{B}
=
c^{Ai}
for every constant
symbol c and i ∈ ω.

F^{B} ( x̅ )
=
F^{Ai} ( x̅ )
for every n-ary function symbol F
and x̅ ∈ | A_{i} |^{n}.

R^{B} ( x̅ )
iff
R^{Ai} ( x̅ )
for every n-ary relation symbol
F and x̅ ∈ | A_{i} |^{n}.

To justify the definition above, we are using the facts:

c^{Ai}
=
c^{Ai}
for all i and j.

| B |^{n}
=
∪_{i ∈ ω} | A_{i} |^{n}.

F^{Aj} ↾ | A_{i} |^{n}
=
F^{Ai}
whenever i ≤ j.

R^{Aj} ∩ | A_{i} |^{n}
=
R^{Ai}
whenever i ≤ j.

Obviously,
each A_{i} is a substructure of B.

Let Σ be a theory.

Assume that every sentence in Σ has the form

∀ u̅ ∃ v̅ φ

where φ is quantifier-free.

Let A_{0} ⊆
A_{1}
⊆
⋅ ⋅ ⋅
⊆
A_{i} ⊆
A_{i+1} ⊆
⋅ ⋅ ⋅
be a chain of models of Σ and B be the union.

Then B is a model of Σ.

Consider an arbitrary x̅ ∈ | B |^{n}.

Pick i large enough that x̅ ∈ | A_{i} |^{n}.

Then
A_{i} ⊨
∃ v̅
φ ( u̅ / x̅ ).

Lemma 4.13 easily implies that B ⊨ ∃ v̅ φ ( u̅ / x̅ ).

Since x̅ was arbitrary, B ⊨ ∀ u̅ ∃ v̅ φ.

**QED**

There is an interesting converse to Lemma 4.15 that is analogous to Theorem 4.14.

Namely, suppose that Σ is a theory with the property that unions of chains of models are also models.

Let Σ^{∀ ∃}
=
{ φ ∣ φ is a sentence of the form ∀ ∃ and Σ ⊢ φ }

Then Σ and Σ^{∀ ∃}
have exactly the same models.

You are encouraged to figure out the proof!

An __elementary__ chain of structures is a chain

A_{0} ≼
A_{1}
≼
⋅ ⋅ ⋅
≼
A_{i} ≼
A_{i+1} ≼
⋅ ⋅ ⋅

where, as we have indicated, A_{i} is an
elementary substructure of A_{i+1}.

Let
A_{0} ≼
A_{1}
≼
⋅ ⋅ ⋅
≼
A_{i} ≼
A_{i+1} ≼
⋅ ⋅ ⋅
be an elementary chain of structures and B be the union.

Then
A_{i} ≼ B for every i ∈ ω.

A_{i} ⊨ φ ( x̅ )
iff
B ⊨ φ ( x̅ )

The proof is trivial when φ is atomic, negation, conjunction, disjunction, conditional or biconditional. The universal case will follow from the existential case. Moreover, only the reverse direction is nontrivial in the existential case. That is what we verify here.

Say φ is ∃ v ψ where the free variables of ψ are among the n+1 variables u̅ and v.

Consider any x̅ ∈ | A_{i} |^{n}.

Assume B ⊨ ∃ v ψ ( u̅ / x̅ ).

Pick y ∈ | B | such that B ⊨ ψ ( u̅ / x̅ , v / y ).

Pick j ≥ i large enough that y ∈ | A_{j} |.

By the induction hypothesis,
A_{j} ⊨ ψ ( u̅ / x̅ , v / y ).

Therefore,
A_{j} ⊨ ∃ v ψ ( u̅ / x̅ ).

Since A_{i} is an elementary substructure of A_{j},
we conclude that
A_{i} ⊨ ∃ v ψ ( u̅ / x̅ ).

**QED**

In this section, we introduce another method which does not depend on the structures fitting together in any particular way other than having the same language.

The starting point is an infinite set I and a collection of structures
A_{i} indexed by i ∈ I.

We need to make several definitions.

Recall from Chapter 1 that P ( I ) is the family of all subsets of I.

That is, P ( I ) = { X ∣ X ⊆ I }.

We define F to be a __filter__ over I iff

- F ⊆ P ( I ) ,
- { } ∉ F and I ∈ F, and
- for all X , Y ∈ P ( I ),
- if X ∈ F and X ⊆ Y, then Y ∈ F, and
- if X , Y ∈ F, then X ∩ Y ∈ F.

We define U to be an __ultrafilter__ over I iff

- U is a filter over I , and
- for every X ∈ P ( I ), either X ∈ U or I - X ∈ U.

Then { X ∈ P ( I ) ∣ S ⊆ X } is a filter over I.

Fix i ∈ I.

Then { X ∈ P ( I ) ∣ i ∈ X } is an ultrafilter over I.

The second example is a special case of the first with S = { i }.

The kinds examples so far are called __principal__.

An example of a nonprincipal filter is { X ∈ P ( ω ) ∣ ω - X is finite }.

This last example is called the __Fréchet__ filter over ω.

To say that a property holds for every natural number is the same as saying

{ n ∈ ω ∣ the property holds for n } ∈ { ω }.

To say that a property holds for F-almost every natural number is the same as saying

{ n ∈ ω ∣ the property holds for n } ∈ F.

So "every" is just the special case of "F-almost every" corresponding to the smallest filter over ω, namely F = { ω }.

Read the definition of filter again with this intuition in mind to better understand the motivation.

Is there an ultrafilter that contains the Fréchet filter? The next result answers this question positively and more.

Let I be a set and F be a filter over I.

Then there exists an ultrafilter U over I such that U ⊇ F.

We omit the proof of Theorem 4.17 because it uses set theory that is not assumed as background for this course.

(It is taught in 21-329 and is in many textbooks.)

Suppose we have sets S_{i} for i ∈ I.

As a reminder of common mathematical jargon,
we might write
i ↦ S_{i}
or
< S_{i} ∣ i ∈ I >
and refer to this function
as a __sequence__ or an __indexed family__.

The __product__ ∏_{i ∈ I} S_{i}
is the collection of functions f such that dom ( f ) = I
and, for every i ∈ I,
f ( i ) ∈ S_{i}.

Let U be an ultrafilter over I.

We define a relation ≡_{U}
on ∏_{i ∈ I} S_{i} by setting
f ≡_{U} g iff
{ i ∈ I ∣ f ( i ) = g ( i ) } ∈ U.

(Another way to read this is: f ≡_{U} g iff
f ( i ) = g ( i ) for U-almost every i ∈ I.)

Here is the verification that ≡_{U} is an equivalence relation:

f ≡_{U} f because { i ∈ I ∣ f ( i ) = f ( i ) } = I ∈ U.

If f ≡_{U} g ,
then g ≡_{U} f
because { i ∈ I ∣ g ( i ) = f ( i ) }
= { i ∈ I ∣ f ( i ) = g ( i ) } ∈ U.

If f ≡_{U} g and g ≡_{U} h,
then f ≡_{U} h because

{ i ∈ I ∣ f ( i ) = g ( i )} ∩ { i ∈ I ∣ g ( i ) = h ( i )} ⊆ { i ∈ I ∣ f ( i ) = h ( i )} ∈ U,

(A set that contains the intersection of two sets in U also belongs to U by the definition of filter.)

The equivalence classes would normally be written [ f ]_{≡U}
but we will use the simpler notation [ f ]_{U}.

The set of equivalence classes would normally be
∏_{i ∈ I} S_{i} / ≡_{U}
but we will write
Ult ( < S_{i} ∣ i ∈ I > , U ).

Suppose we have structures A_{i} for i ∈ I.

Assume all A_{i} are structures in the same language.

Let U be an ultrafilter over I.

We define a structure B
= Ult ( < A_{i} ∣ i ∈ I > , U ) called the
__ultraproduct__ as follows.

| B | = Ult ( < | A_{i} | ∣ i ∈ I > , U ).

c^{B} = [ i ↦ c^{Ai} ]_{U}
for every constant symbol c.

For every n-ary function symbol F,

F^{B} (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} )
=
[ g ]_{U}
iff
{ i ∈ I ∣
F^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) )
=
g ( i ) } ∈ U .

For every n-ary function symbol R,

R^{B} (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} )
iff
{ i ∈ I ∣
R^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) )
} ∈ U .

We need to justify the function and relation clauses of this definition because they look like they depend on the choice of representatives of equivalence classes.

The point is that if
f '_{m} ≡_{U} f_{m}
for all m < n and
g ' ≡_{U} g ,
then, letting

X = { i ∈ I ∣
f '_{m} ( i ) = f_{m} ( i ) for all m < n and
g '_{m} ( i ) = g_{m} ( i ) } ,

we find that X ∈ U,

{ i ∈ I ∣
F^{Ai} (
f '_{0} ( i )
, … ,
f '_{n-1} ( i ) ) = g ' ( i )
} ∈ U
iff
{ i ∈ X ∣
F^{Ai} (
f '_{0} ( i )
, … ,
f '_{n-1} ( i ) ) = g ' ( i )
} ∈ U

iff
{ i ∈ X ∣
F^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) = g ( i )
} ∈ U
iff
{ i ∈ I ∣
F^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) = g ( i )
} ∈ U

and

{ i ∈ I ∣
R^{Ai} (
f '_{0} ( i )
, … ,
f '_{n-1} ( i ) )
} ∈ U
iff
{ i ∈ X ∣
R^{Ai} (
f '_{0} ( i )
, … ,
f '_{n-1} ( i ) )
} ∈ U

iff
{ i ∈ X ∣
R^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) )
} ∈ U
iff
{ i ∈ I ∣
R^{Ai} (
f_{0} ( i )
, … ,
f_{n-1} ( i ) )
} ∈ U .

This justifies the definition of ultraproduct.

Notice that the calculation above does not use the "ultra" in "ultrafilter. All we have used so far is that filters are closed under finite intersections and supersets, and that { } ∉ U.

Let < A_{i} ∣ i ∈ I > be an indexed family of structures
in a common language.

Let U be an ultrafilter over I.

Let B = Ult ( < A_{i} ∣ i ∈ I > , U ).

Let φ be a formula whose free variables are among the n-tuple of variables u̅.

Let
f_{m} ∈ ∏_{i ∈ I} | A_{i} |
for m < n.

Then

B ⊨ φ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} )

iff

{ i ∈ I ∣
A_{i} ⊨ φ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) } ∈ U.

We may assume that φ is built up from atomic formulas using ¬ , ∧ and ∃.

The definition of the ultraproduct says that

B ⊨ [ f ]_{U} ≈ [ g ]_{U}
iff
{ i ∈ I ∣ A_{i} ⊨ f ( i ) ≈ g ( i ) } ∈ U

and

B ⊨
R ( [ f_{0} ]_{U} , … , [ f_{n-1} ]_{U}
iff
{ i ∈ I ∣ A_{i} ⊨
R ( f_{0} ( i ) , … , f_{n-1} ( i ) ) } ∈ U

for every n-ary relation symbol R.

This covers the atomic case if the only terms are variables.

But there might be more complex terms.

Substituting terms for free-variables in atomic formulas gives rise to additional atomic formulas.

For example, F ( u , c ) ≈ v is an atomic formula if F is a binary function symbol and c is a constant symbol.

We see why the theorem holds for this particular atomic formula by calculating:

B ⊨ F ( [ f ]_{U} , c ) ≈ [ g ]_{U}

iff

F^{B} ( [ f ]_{U} , c^{B} ) = [ g ]_{U}

iff

F^{B} ( [ f ]_{U} , [ i ↦ c^{Ai} ] )
= [ g ]_{U}

iff

{ i ∈ I ∣
F^{Ai} ( f ( i ) , c^{Ai} )
= g ( i ) } ∈ U

iff

{ i ∈ I ∣
A_{i} ⊨ F ( f ( i ) , c ) ≈ g ( i ) } ∈ U

where we have used the definition of c^{B} and F^{B} above.

This example indicates how to work the general atomic case using an induction on the complexity of terms.

We leave the rest of the atomic case as an exercise.

The conjunction case is immediate from the induction hypothesis and the definition of filter.

We also leave the conjunction case as an exercise.

We still have not used the "ultra" in "ultrafilter".

Suppose that φ is ¬ ψ.

Then,

B ⊨ φ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} )

iff

B ⊭ ψ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} )

iff (by the induction hypothesis)

{ i ∈ I ∣
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) } ∉ U

iff (by the "ultra" in "ultrafilter")

I - { i ∈ I ∣
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) } ∈ U

iff

{ i ∈ I ∣
A_{i} ⊨ φ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) ) } ∈ U

To finish the proof of the theorem, it suffices to handle the existential case.

So assume φ ( u̅ ) is ∃ v ψ ( u̅ , v ).

First assume that
B ⊨
∃ v ψ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} , v ).

Pick g so that
B ⊨
ψ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} ,
[ g ]_{U} ).

By the induction hypothesis,
{ i ∈ I ∣
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , g ( i ) ) } ∈ U.

A set that contains a set in U also belongs to U, so

{ i ∈ I ∣
A_{i} ⊨ ∃ v ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , v ) } ∈ U.

That finishes the forward direction of the existential case. Now we work backwards from the last line above.

Call the displayed set X.

Then X ∈ U and,
for every i ∈ X,
there exists y ∈ | A_{i} |
such that
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , y ).

Let g be a function with dom ( g ) = X
such that
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , g ( i ) ) for all i ∈ X.

Let h be a function with dom ( h ) = I
such that h ↾ X = g
and h ( i ) ∈ | A_{i} | is arbitrary for i ∉ X.

(Recall that the universe of a structure is nonempty so we can a function h that extends g with dom ( h ) = I.)

Then
X ⊆
{ i ∈ I ∣
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , h ( i ) ) }.

Hence
{ i ∈ I ∣
A_{i} ⊨ ψ (
f_{0} ( i )
, … ,
f_{n-1} ( i ) , h ( i ) ) }
∈ U.

By the induction hypothesis,
B ⊨
ψ
(
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} ,
[ h ]_{U} ).

Therefore,
B ⊨
∃ v ψ (
[ f_{0} ]_{U}
, … ,
[ f_{n-1} ]_{U} ,
v ) and we are done with the reverse direction of the existential case.

**QED**

In this case, we say __ultrapower__ instead of ultraproduct
and write Ult ( A , U ) instead of Ult ( ( A ∣ i ∈ I ) , U ).

Let U be an ultrafilter on I.

Let A be a structure and B = Ult ( A , U ).

Let π : | A | → | B |
be defined by π ( x ) = [ i ↦ x ]_{U}.

Then π is an elementary embedding from A to B.

Now we calculate:

B ⊨ φ (
[ i ↦ x_{0} ]_{U}
, … ,
[ i ↦ x_{n-1} ]_{U}
)

iff (by Theorem 4.18)

{ i ∈ I ∣
A ⊨ φ ( x_{0} , … , x_{n-1} )
} ∈ U

iff (see reason below)

A ⊨ φ ( x_{0} , … , x_{n-1} ).

The reason for the second "iff" is that the set
{ i ∈ I ∣
A ⊨ φ ( x_{0} , … , x_{n-1} )
}
is either { } or I
but { } ∉ U while I ∈ U.

**QED**

Like any existence theorem, it tells us there is a model but gives us no additional information about it.

Ultraproducts can be used instead of compactness to obtain models that seem more concrete and easier to understand.

Here we give explain the idea of this technique. Applications are included in the exercises.

Fix an infinite structure A.

Let U be an ultrafilter over ω that extends the Fréchet filter F = { X ⊆ ω ∣ ω - X is finite }.

Then every member of U is infinite.

Let B = Ult ( A , U ) and π : x ↦ [ i ↦ x ]_{U} .

The situation is just like in Theorem 4.19.

Let e be an injection from ω to | A |.

Then, for every x ∈ | A |, the set

{ j ∈ ω ∣ e ( j ) = ( i ↦ x ) ( j ) }

is either empty or a singleton, so it does not belong to U, thus

[ e ]_{U} ≠ [ i ↦ x ]_{U} .

Therefore,

[ e ]_{U} ∉ ran ( π ) .

Thus π is an elementary embedding from A to B but ran ( π ) ≠ B.

This means we can form a structure A^{*} by restricting
the functions and relation of B to ran ( π ) and end up with

π : A ≈ A^{*} ≼ B but A^{*} ≠ B.

The same conclusion was the basis for Lemmas 4.6 and 4.7, as well as the development of nonstandard analysis in § 4.4. There we used the Compactness Theorem 3.16 whereas here we took an ultraproduct which gives more concrete information.

In fact, there is a slick proof of the Compactness Theorem that uses ultraproducts which you will find in the exercises.