© Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Chapter 4 : Model theory

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

Suppose that t is a term with variables among u₀ , … , u_n-1.

We might write t ( u₀ , … , u_n-1 ) or t ( u̅ ) to emphasize this.

Suppose that φ is a formula with free variables among u₀ , … , u_n-1.

We might write φ ( u₀ , … , u_n-1 ) or φ ( u̅ ) to emphasize this.

Also, if we have a model A and x₀ , … , x_n-1 ∈ | A |, then we could write

    A ⊨ φ ( u₀ / x_n-1 , … , u_n-1 / x_n-1 )

or

    A ⊨ φ ( u̅ / x̅ )

instead of

    ( A , x₀ , … , x_n-1 ) ⊨ φ ( u₀ / 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.

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.

§ 4.1   Downward Löwenheim-Skolem

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 |ⁿ for every n-ary function symbol F
• R^A = R^B ∩ | A |ⁿ 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 |ⁿ

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

Proof of Lemma 4.2

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

Define an increasing sequence of sets

    Y = Z₀ ⊆ Z₁ ⊆ ⋅ ⋅ ⋅ ⊆ Z_i ⊆ ⋅ ⋅ ⋅ ⊆ | B |

by putting

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

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₀ ⊆ Z for every constant symbol c.

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

Therefore, F^B ↾ Zⁿ 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ⁿ for every n-ary function symbol F

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

QED

Sketch of Lemma 4.3

First we claim that for every term t ( u̅ ) with n free variables, if x̅ ∈ | A |ⁿ, 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 |ⁿ,

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

Proof of Theorem 4.4

    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

Proof of Theorem 4.5

We may assume that B is infinite.

For each formula φ ( u̅ , v ) with n+1 free variables, choose a function f_φ : | B |ⁿ → | 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

§ 4.2   Upward Löwenheim-Skolem

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.

Proof of Lemma 4.6

Claim A

Let d be a constant symbol in the expanded language.

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

Proof of Claim A

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 symbol and x̅ ∈ | A |ⁿ.

Then π ( F^D ( x̅ ) ) = F^E ( π ( x₀ ) , … , π ( 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₀ ) , … , π ( 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^E ↾ ran ( π ) ⁿ for every n-ary function symbol F.

    R^D* = R^E ∩ ran ( π ) ⁿ 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 relation symbol and x̅ ∈ | A |ⁿ.

Then   R^D ( x̅ )   iff   R^E ( π ( x₀ ) , … , π ( 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 |ⁿ.

Then the following are equivalent.

1. A ⊨ φ ( x₀ , … , x_n-1 )
2. D ⊨ φ ( u₀ / c_x0 , … , u_n-1 / c_xn-1 )
3. E ⊨ φ ( u₀ / c_x0 , … , u_n-1 / c_xn-1 )
4. ( B , π ( x₀ ) , … , π ( x_n-1 ) ) ⊨ φ ( u₀ / c_{π ( x0 )} , … , u_n-1 / c_{π ( xn-1 )} )
5. B ⊨ φ ( π ( x₀ ) , … , π ( 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₀ / 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₀ ) , … , π ( x_n-1 ) )

iff (by Claim F and Lemma 4.1)

    A ⊨ φ ( x₀ , … , x_n-1 )  

iff (by Claim G)

    B ⊨ φ ( π ( x₀ ) , … , π ( 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̅ )

Proof of Lemma 4.7

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₀ , … , 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₀ , … , 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 |ⁿ and formula φ with n free variables.

Then

    A ⊨ φ ( x̅ )

iff   ( by Lemma 4.1 )

    A^* ⊨ φ ( π ( x₀ ) , … , π ( x_n-1 ) )

iff   ( since A^* ≼ B )

    B ⊨ φ ( π ( x₀ ) , … , π ( x_n-1 ) )

iff   ( since σ : B' ≈ B )

    B' ⊨ φ ( σ^-1 ( π ( x₀ ) ) , … , σ^-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

Proof of Theorem 4.8

{ 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₀ , … , d_n-1.

Pick distinct y₀ , … , y_n-1 ∈ | A | - { x₀ , … , 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

§ 4.3   Dense linear orderings

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.

Proof of Theorem 4.9

Let i ↦ b_i be a bijection from ω to | B |.

By recursion on n, we will define

1. a finite S_n ⊂ | A | such that S_i ∪ { a_i } ⊆ S_n for all i < n,
2. a finite T_n ⊂ | B | such that T_i ∪ { b_i } ⊆ T_n for all i < n and
3. an isomorphism f_n : A ↾ S_n ≈ B ↾ T_n such that f_n ↾ S_i = f_i for all i < n.

Let S₀ = S, T₀ = T and f₀ = 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₀ R^A x₁ 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₀ R^B y₁ 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^*₀ R^A x^*₁ R^A ⋅ ⋅ ⋅ R^A x^*_ℓ-1

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

    y^*₀ R^B y^*₁ R^B ⋅ ⋅ ⋅ R^B y^*_ℓ-1

There are four cases:

Case 1.   b_n R^B y^*_i   for all i < ℓ.

Since A has no left endpoint, there exists a ∈ | A | such that a R^A x^*_i for all i < ℓ.

Pick any such a and make f_n+1^-1 ( b_n ) = a.

Case 2.   y^*_i R^B b_n   for all i < ℓ.

Since A has no right endpoint, there exists a ∈ | A | such that x^*_i R^A a for all i < ℓ.

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 < ℓ.

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 < ℓ.

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.

Proof of Theorem 4.10

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

Proof of Theorem 4.11

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

• ψ is either atomic or negation of atomic,
• the free variables of ψ are among v̅ = (v₀, … v_n-1), and
• A ⊨ ψ ( v̅ / x̅ ).

type ( x̅ ) is called the atomic type of x̅ in A.

Note that each atomic formula in this language has either one or two free variables.

So there are only finitely many atomic formulas with free variables among v₀, … v_n-1.

From this, it is clear that type ( x̅ ) is finite for each natural number n and x̅ ∈ | A |ⁿ.

For each natural number n, the set { type ( x̅ ) ∣ x̅ ∈ | A |ⁿ } is also finite.

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

1. The map x_i ↦ y_i is an isomorphism from A ↾ { x_i ∣ i < n } to A ↾ { y_i ∣ i < n }.
2. By Theorem 4.9, there is an automorphism π of A such that π ( x_i ) = y_i. for all i < n.
3. By Lemma 4.1, for every formula χ whose free variables are among v̅,

       A ⊨ χ ( x̅ )   iff   A ⊨ χ ( y̅ ).

Assume for now that S is nonempty.

Then T is nonempty.

T is finite; say T = { τ₀ , … , τ_k-1 }.

Each τ_i is finite and nonempty, so we may let δ_i ( v̅ ) be the conjunction of all the formulas in τ_i.

Let ψ ( v̅ ) be the disjunction of the formulas δ_i ( v̅ ) for i < k.

If S is empty, then let ψ be ⊥.

Either way, ψ is quantifier-free.

Now, for all x̅ ∈ | A |ⁿ,

    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 ⊨ ∀ v̅ ( φ ↔ ψ )

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.

Least upper bound property

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 }, 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.

Sketch of Theorem 4.12

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

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

QED

§ 4.4   Nonstandard analysis

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₀ / c_x0 , … , u_n-1 / c_xn-1 )   iff   A^* ⊨ φ ( u₀ / c_{π ( x0 )} , … , u_n-1 / c_{π ( xn-1 )} )   iff   B ⊨ φ ( u₀ / 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.

§ 4.5   Universal theories

Proof of Lemma 4.13

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.

Proof of Theorem 4.14

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₀ / c_x0 , … , u_n-1 / c_xn-1 )

or

    ¬ ψ ( u₀ / c_x0 , … , u_n-1 / c_xn-1 )

that are satisfied by A where ψ is atomic and x̅ ∈ | A |ⁿ.

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 φ₀ , … , φ_k in Δ such that

    Σ ⊢ ¬ ( φ₀ ∧ ⋅ ⋅ ⋅ ∧ φ_k ).

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

    φ_i = χ_i ( u₀ / 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 χ₀ ∧ ⋅ ⋅ ⋅ ∧ χ_k.

Then

    Σ ⊢ ¬ ψ ( u₀ / 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₀ / c_x0 , … , u_n-1 / c_xn-1 ).

In other words, A ⊨ ¬ ( φ₀ ∧ ⋅ ⋅ ⋅ ∧ φ_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

Examples of universal theories

    ∀ 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 ) )

§ 4.6   Chains of structures

Appropriately:

Examples of theories that are not universal

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₀ ⊆ A₁ ⊆ ⋅ ⋅ ⋅ ⊆ 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^A_i   for every constant symbol c and i ∈ ω.

    F^B ( x̅ )   =   F^A_i ( x̅ )   for every n-ary function symbol F and x̅ ∈ | A_i |ⁿ.

    R^B ( x̅ )   iff   R^A_i ( x̅ )   for every n-ary relation symbol F and x̅ ∈ | A_i |ⁿ.

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

    c^A_i   =   c^A_i   for all i and j.

    | B |ⁿ   =   ∪_{i ∈ ω} | A_i |ⁿ.

    F^A_j ↾ | A_i |ⁿ   =   F^A_i   whenever i ≤ j.

    R^A_j ∩ | A_i |ⁿ   =   R^A_i   whenever i ≤ j.

Obviously, each A_i is a substructure of B.

Proof of Lemma 4.15

Consider an arbitrary x̅ ∈ | B |ⁿ.

Pick i large enough that x̅ ∈ | A_i |ⁿ.

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₀ ≼ A₁ ≼ ⋅ ⋅ ⋅ ≼ A_i ≼ A_i+1 ≼ ⋅ ⋅ ⋅

where, as we have indicated, A_i is an elementary substructure of A_i+1.

Proof of Lemma 4.16

    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 |ⁿ.

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

§ 4.7   Ultraproducts

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.

Examples

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 ω.

Intuition

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.

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.)

Reduced products of sets

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 ).

Reduced products of structures (ultraproducts)

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^A_i ]_U   for every constant symbol c.

    For every n-ary function symbol F,

        F^B ( [ f₀ ]_U , … , [ f_n-1 ]_U ) = [ g ]_U   iff   { i ∈ I ∣ F^A_i ( f₀ ( i ) , … , f_n-1 ( i ) ) = g ( i ) } ∈ U .

    For every n-ary function symbol R,

        R^B ( [ f₀ ]_U , … , [ f_n-1 ]_U )   iff   { i ∈ I ∣ R^A_i ( f₀ ( 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^A_i ( f '₀ ( i ) , … , f '_n-1 ( i ) ) = g ' ( i ) } ∈ U   iff   { i ∈ X ∣ F^A_i ( f '₀ ( i ) , … , f '_n-1 ( i ) ) = g ' ( i ) } ∈ U

    iff   { i ∈ X ∣ F^A_i ( f₀ ( i ) , … , f_n-1 ( i ) ) = g ( i ) } ∈ U   iff   { i ∈ I ∣ F^A_i ( f₀ ( i ) , … , f_n-1 ( i ) ) = g ( i ) } ∈ U

and

    { i ∈ I ∣ R^A_i ( f '₀ ( i ) , … , f '_n-1 ( i ) ) } ∈ U   iff   { i ∈ X ∣ R^A_i ( f '₀ ( i ) , … , f '_n-1 ( i ) ) } ∈ U

    iff   { i ∈ X ∣ R^A_i ( f₀ ( i ) , … , f_n-1 ( i ) ) } ∈ U   iff   { i ∈ I ∣ R^A_i ( f₀ ( 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.

Intuition

Sketch of Łoś's Theorem 4.18

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₀ ]_U , … , [ f_n-1 ]_U   iff   { i ∈ I ∣ A_i ⊨ R ( f₀ ( 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^A_i ] ) = [ g ]_U

iff

    { i ∈ I ∣ F^A_i ( f ( i ) , c^A_i ) = 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₀ ]_U , … , [ f_n-1 ]_U )

iff

    B ⊭ ψ ( [ f₀ ]_U , … , [ f_n-1 ]_U )

iff   (by the induction hypothesis)

    { i ∈ I ∣ A_i ⊨ ψ ( f₀ ( i ) , … , f_n-1 ( i ) ) } ∉ U

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

    I - { i ∈ I ∣ A_i ⊨ ψ ( f₀ ( i ) , … , f_n-1 ( i ) ) } ∈ U

iff

    { i ∈ I ∣ A_i ⊨ φ ( f₀ ( 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₀ ]_U , … , [ f_n-1 ]_U , v ).

Pick g so that B ⊨ ψ ( [ f₀ ]_U , … , [ f_n-1 ]_U , [ g ]_U ).

By the induction hypothesis, { i ∈ I ∣ A_i ⊨ ψ ( f₀ ( 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₀ ( 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₀ ( i ) , … , f_n-1 ( i ) , y ).

Let g be a function with dom ( g ) = X such that A_i ⊨ ψ ( f₀ ( 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₀ ( i ) , … , f_n-1 ( i ) , h ( i ) ) }.

Hence { i ∈ I ∣ A_i ⊨ ψ ( f₀ ( i ) , … , f_n-1 ( i ) , h ( i ) ) } ∈ U.

By the induction hypothesis, B ⊨ ψ ( [ f₀ ]_U , … , [ f_n-1 ]_U , [ h ]_U ).

Therefore, B ⊨ ∃ v ψ ( [ f₀ ]_U , … , [ f_n-1 ]_U , v ) and we are done with the reverse direction of the existential case.

QED

Ultrapowers

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

Proof of Theorem 4.19

Now we calculate:

    B ⊨ φ ( [ i ↦ x₀ ]_U , … , [ i ↦ x_n-1 ]_U )

iff   (by Theorem 4.18)

    { i ∈ I ∣ A ⊨ φ ( x₀ , … , x_n-1 ) } ∈ U

iff   (see reason below)

    A ⊨ φ ( x₀ , … , x_n-1 ).

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

QED

Ultrapowers as alternatives to compactness

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.