Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 4

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Chapter 4 : Model theory

In this chapter, we will develop general tools for comparing and constructing the models of a given theory. These techniques will be applied to some interesting theories.

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

Suppose that t is a term with variables among u0 , … , un-1.

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

Suppose that φ is a formula with free variables among u0 , … , un-1.

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

Also, if we have a model A and x0 , … , xn-1 ∈ | A |, then we could write

    A ⊨ φ ( u0 / xn-1 , … , un-1 / xn-1 )

or

    A ⊨ φ ( u̅ / x̅ )

instead of

    ( A , x0 , … , xn-1 ) ⊨ φ ( u0 / cx0 ) ⋅ ⋅ ⋅ ( un-1 / cxn-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.

    Lemma 4.1

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

    Then, for every formula φ, if φ has free variables u0, … , un-1,

    then for all x̅ ∈ | A |n,

        B ⊨ φ ( π ( x0 ) , … , π ( xn-1 ) )

   iff

        A ⊨ φ ( x0 , … , xn-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.

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

In this case, we write A ⊆ B.

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

    cB ∈ | A | for every constant symbol c

    FB ( 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.

    Lemma 4.2

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

Proof of Lemma 4.2

Without loss of generality, X is non-empty.

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

Define an increasing sequence of sets

    Y = Z0 ⊆ Z1 ⊆ ⋅ ⋅ ⋅ ⊆ Zi ⊆ ⋅ ⋅ ⋅ ⊆ | B |

by putting

    Zi+1 = Zi ∪ { FB ( x̅ ) ∣ F is an n-ary function symbol and x̅ ∈ Zin }.

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

Let Z = ∪i ∈ ω Zi.

Then Z is a countable subset of B.

And, cB ∈ Z0 ⊆ Z for every constant symbol c.

Also, for every n-ary function symbol F and every x̅ ∈ Zn, there exists i ∈ ω such that x̅ ∈ Zin and FB ( x̅ ) ∈ Zi+1 ⊆ Z.

Therefore, FB ↾ Zn is an n-ary function on Z.

Thus we obtain a countable substructure A of B by setting

    | A | = Z

    cA = cB for every constant symbol

    FA = FB ↾ Zn for every n-ary function symbol F

    RA = RB ∩ Zn for every n-ary function symbol R

QED

    Lemma 4.3

    Suppose A is a substructure of B.

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

Sketch of Lemma 4.3

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 | , cA , dA , FA , GA , RA )

and

    B = ( ℝ , 0 , 1 , + , × , < ) = ( | B | , cB , dB , FB , GB , RB )

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

    Tarski-Vaught Test 4.4

    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.

Proof of Theorem 4.4

We prove by induction on formulas φ ( u̅ ) that

    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

    Downward Löwenheim-Skolem Theorem 4.5

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

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

§ 4.2   Upward Löwenheim-Skolem

Consider a structure A.

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

Expand A to a structure D = ( A , x )x ∈ | A | that interprets cx by x.

In other words, D is the expansion of A with cxD = 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.

    Lemma 4.6

    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 → cxE is an isomorphism from A to an elementary substructure A* of B.

Proof of Lemma 4.6

Claim A

Let d be a constant symbol in the expanded language.

Then π ( dD ) = dE.

Proof of Claim A

Pick x ∈ | A | such that dD = x.

Then the sentence d ≈ cx belongs to Diagram ( A ).

Hence E ⊨ d ≈ cx.

Thus dE = cxE = π ( x ) = π ( dD ) .

Claim B

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

Then π ( FD ( x̅ ) ) = FE ( π ( x0 ) , … , π ( xn-1 ) ).

Proof of Claim B

Let y = FD ( x̅ ).

Then D ⊨ cy ≈ F ( cx0 , … , cxn-1 ).

So the sentence cy ≈ F ( cx0 , … , cxn-1 ) belongs to Diagram ( A ).

Hence E ⊨ cy ≈ F ( cx0 , … , cxn-1 ).

In other words, cyE = FE ( cx0E , … , cxn-1E ).

Equivalently, π ( y ) = FE ( π ( x0 ) , … , π ( xn-1 ) ).

Claim C

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

    D* = ran ( π )

    cD* = cE for every constant symbol c in the expanded language.

    FD* = FD* ↾ | ran ( π ) |n for every n-ary function symbol F.

    RD* = RD* ∩ | 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 ⊨ cx ≉ cy.

So the sentence cx ≉ cy belongs to Diagram ( A ).

Hence E ⊨ cx ≉ cy.

Thus π ( x ) = cxE ≠ cyE = π ( y ).

Claim E

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

Then   RD ( x̅ )   iff   RE ( π ( x0 ) , … , π ( xn-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.

  1. A ⊨ φ ( x0 , … , xn-1 )
  2. D ⊨ φ ( u0 / cx0 , … , un-1 / cxn-1 )
  3. E ⊨ φ ( u0 / cx0 , … , un-1 / cxn-1 )
  4. ( B , π ( x0 ) , … , π ( xn-1 ) ) ⊨ φ ( u0 / cπ ( x0 ) , … , un-1 / cπ ( xn-1 ) )
  5. B ⊨ φ ( π ( x0 ) , … , π ( xn-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 φ ( u0 / cx0 , … , un-1 / cxn-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 ) = cxE.

Thus,   cxE = cπ ( x )( E , π ( x ) ) .

In other words,   ( E , π ( x ) ) ⊨ cx ≈ cπ ( x ).

By Substitution Lemma 3.2, we conclude that   ( E , π ( x ) ) ⊨ φ ( u / cx ) ↔ φ ( u / cπ ( x ) ) .

Note that φ ( u / cx ) 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 / cx )   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* ⊨ φ ( π ( x0 ) , … , π ( xn-1 ) )

iff (by Claim F and Lemma 4.1)

    A ⊨ φ ( x0 , … , xn-1 )  

iff (by Claim G)

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

    Lemma 4.7

    Each infinite structure has a proper elementary extension.

Proof of Lemma 4.7

Let A be an infinite structure and d be a new constant symbol.

Let d be a new constant.

Let Σ be the theory Diagram ( A ) ∪ { d ≉ cx ∣ 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 x0 , … , xn-1 ∈ | A |.

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

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

Then B ⊨ Diagram ( A ) ∪ { d ≉ cx ∣ x = x0 , … , xn-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 ↦ cxE.

Let T = | B | - | A* |.

As E is a model of Σ we have that dE ∈ 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* ⊨ φ ( π ( x0 ) , … , π ( xn-1 ) )

iff   ( since A* ≼ B )

    B ⊨ φ ( π ( x0 ) , … , π ( xn-1 ) )

iff   ( since σ : B' ≈ B )

    B' ⊨ φ ( σ-1 ( π ( x0 ) ) , … , σ-1 ( π ( xn-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

    Upward Löwenheim-Skolem 4.8

    Each infinite structure has an uncountable elementary extension.

Proof of Theorem 4.8

The idea is to repeat the proof of Lemma 4.7 but instead of introducing just one new constant d, introduce uncountably many new constants and let Σ be the union of Diagram ( A ) and

{ d ≉ cx ∣ 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 d0 , … , dn-1.

Pick distinct y0 , … , yn-1 ∈ | A | - { x0 , … , xm-1 }.

Let B be the expansion of ( A , x̅ ) which interprets dj as yj for all j < n.

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

{ dj ≉ cxi ∣ i < m and j < n } ∪ { di ≉ dj ∣ 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

Consider the language with one binary relation symbol R.

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.

    Theorem 4.9

    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.

Proof of Theorem 4.9

Let i ↦ ai be a bijection from ω to | A |.

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

By recursion on n, we will define

  1. a finite Sn ⊂ | A | such that Si ∪ { ai } ⊆ Sn for all i < n,
  2. a finite Tn ⊂ | B | such that Ti ∪ { bi } ⊆ Tn for all i < n and
  3. an isomorphism fn : A ↾ Sn ≈ B ↾ Tn such that fn ↾ Si = fi for all i < n.

Let S0 = S, T0 = T and f0 = f.

Assume we have defined appropriate Si , Ti and fi for all i ≤ n.

Based on this, we must define appropriate Sn+1 , Tn+1 and fn+1.

List Sn in increasing order according to RA as

    x0 RA x1 RA ⋅ ⋅ ⋅ RA xk-1

where k is the size of Sn.

List Tn in increasing order according to RB as

    y0 RB y1 RB ⋅ ⋅ ⋅ RB yk-1.

Since fn is an isomorphism, it must be that yi = fn ( xi ) for all i < k.

First we decide the value of fn+1 ( an ).

There are four cases:

Case 1.   an RA xi   for all i < k.

Since B has no left endpoint, there exists b ∈ | B | such that b RB yi for all i < k.

Pick any such b and make fn+1 ( an ) = b.

Case 2.   xi RA an   for all i < k.

Since B has no right endpoint, there exists b ∈ | B | such that yi RB b for all i < k.

Pick any such b and make fn+1 ( an ) = b.

Case 3.   xi RA an RA xj   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 yi RB b RB yj.

Pick any such b and make fn+1 ( an ) = b.

Case 4   an = xi   for some i < k.

In this case, we let b = yi and fn+1 ( an ) = b.

Second, we decide the value of fn+1-1 ( bn ).

For this, we list Sn ∪ { an } in increasing order according to RA as

    x*0 RA x*1 RA ⋅ ⋅ ⋅ RA x*k-1 RA x*k

and Tn ∪ { b } in increasing order according to RB as

    y*0 RB y*1 RB ⋅ ⋅ ⋅ RB y*k-1 RB y*k

There are four cases:

Case 1.   bn RB y*i   for all i ≤ k.

Since A has no left endpoint, there exists a ∈ | A | such that a RA x*i for all i ≤ k.

Pick any such a and make fn+1-1 ( bn ) = a.

Case 2.   y*i RB bn   for all i ≤ k.

Since A has no right endpoint, there exists a ∈ | A | such that x*i RA a for all i ≤ k.

Pick any such a and make fn+1-1 ( bn ) = a.

Case 3.   y*i RB bn RB 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 RA a RA x*j.

Pick any such a and make fn+1-1 ( bn ) = a.

Case 4   bn = y*i   for some i ≤ k.

In this case, we let a = x*i and fn+1-1 ( bn ) = a.

To finish the recursive construction, put

    Sn+1 = Sn ∪ { an , a } = dom ( fn+1 )

and

    Tn+1 = Tn ∪ { bn , b } = ran ( fn+1 )

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

Now we finish the proof of the theorem.

Clearly, | A | is the union of the sets Sn for n < ω.

Also, | B | is the union of the sets Tn for n < ω.

So we can define a function π : | A | → | B | by setting π ( an ) = fn+1 ( an ).

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

    π ( am ) = fm+1 ( am ) = fn+1 ( am ) ≠ fn+1 ( an ) = π ( an ).

To see that π is a surjection, note that if am = fn+1-1 ( bn ) and k = max ( m , n ), then

π ( am ) = fm+1 ( am ) = fk+1 ( am ) = fn+1 ( am ) = bn.

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

am RA an   iff   fk+1 ( am ) RB fk+1 ( an )   iff   fm+1 ( am ) RB fn+1 ( an )   iff   π ( am ) RB π ( an ).

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.

    Theorem 4.10

    DLO is a complete theory.

Proof of Theorem 4.10

Otherwise, there is a sentence φ such that both DLO ∪ { φ } and DLO ∪ { ¬ φ } are consistent.

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

    Theorem 4.11

    Let φ be a formula whose free variables are among u̅ = ( u0 , … , un-1 ).

    Then there exists a quantifier-free formula ψ such that

        DLO ⊢ ∀ u̅ ( φ ↔ ψ )

Proof of Theorem 4.11

Let A be a countable model of DLO.

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

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:

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

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

Let S = { x̅ ∣ A ⊨ φ ( x̅ ) } and T = { type ( x̅ ) ∣ x̅ ∈ S }.

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.

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 ∈ ℚ ∣ x2 < 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 RA 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 RA 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.

    Theorem 4.12

    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 RB y RB 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 | = π.

Sketch of Theorem 4.12

For y ∈ | B |, define

    σ ( y ) = lub ( { π ( x ) ∣ x ∈ | A |   and   x RB 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 ) ∪ { cx < 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 cx R d rather than R ( cx , 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 ↦ cxE and find A* ≼ B such that π : A ≈ A*.

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

    A ⊨ φ ( u0 / cx0 , … , un-1 / cxn-1 )   iff   A* ⊨ φ ( u0 / cπ ( x0 ) , … , un-1 / cπ ( xn-1 ) )   iff   B ⊨ φ ( u0 / cπ ( x0 ) , … , un-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 dE 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 dE ∈ 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   0A* = 0B = π ( 0A )   and   1A* = 1B = π ( 1A ).

Let

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

and

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

Then

    Positive ( A* ) ⊂ Positive ( B )   but   dE ∈ 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   0A   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

    ε = 1B ÷B dE,

then

    0B   <B   ε   <B   x

for every x ∈ Positive ( A* ).

For δ ∈ | B |, we say that δ is an infinitesimal iff   0B <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

    Lemma 4.13

    Suppose A is a substructure of B.

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

    Let x̅ be from | A |.

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

Proof of Lemma 4.13

Assume B ⊨ ∀ 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.

    Theorem 4.14

    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.

Proof of Theorem 4.14

That 2) implies 1) is immediate from Lemma 4.13.

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

    ψ ( u0 / cx0 , … , un-1 / cxn-1 )

or

    ¬ ψ ( u0 / cx0 , … , un-1 / cxn-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 → cxE 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 ( u0 / cx0 , ... , un-1 / cxn-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

    Σ ⊢ ¬ ψ ( u0 / cx0 , … , un-1 / cxn-1 ).

By the Generalization Theorem 3.6,

    Σ ⊢ ∀ u̅ ¬ ψ.

Therefore, ∀ u̅ ¬ ψ belongs to Σ.

So A ⊨ ∀ u̅ ¬ ψ.

Hence A ⊨ ¬ ψ ( u0 / cx0 , … , un-1 / cxn-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

Examples of universal theories

The theory of equivalence relations:

    ∀ 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

The previous section ended with examples of universal theories.

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

    A0 ⊆ A1 ⊆ ⋅ ⋅ ⋅ ⊆ Ai ⊆ Ai+1 ⊆ ⋅ ⋅ ⋅

where, as we have indicated, Ai is substructure of Ai+1.

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

    | B |   =   ∪i ∈ ω | Ai |

    cB   =   cAi   for every constant symbol c and i ∈ ω.

    FB ( x̅ )   =   FAi ( x̅ )   for every n-ary function symbol F and x̅ ∈ | Ai |n.

    RB ( x̅ )   iff   RAi ( x̅ )   for every n-ary relation symbol F and x̅ ∈ | Ai |n.

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

    cAi   =   cAi   for all i and j.

    | B |n   =   ∪i ∈ ω | Ai |n.

    FAj ↾ | Ai |n   =   FAi   whenever i ≤ j.

    RAj ∩ | Ai |n   =   RAi   whenever i ≤ j.

Obviously, each Ai is a substructure of B.

    Lemma 4.15

    Let Σ be a theory.

    Assume that every sentence in Σ has the form

        ∀ u̅ ∃ v̅ φ

    where φ is quantifier-free.

    Let A0 ⊆ A1 ⊆ ⋅ ⋅ ⋅ ⊆ Ai ⊆ Ai+1 ⊆ ⋅ ⋅ ⋅ be a chain of models of Σ and B be the union.

    Then B is a model of Σ.

Proof of Lemma 4.15

Suppose that ∀ u̅ ∃ v̅ φ ( u̅ , v̅ ) is a sentence in Σ where u̅ is an n-tuple of variables and φ is quantifier-free.

Consider an arbitrary x̅ ∈ | B |n.

Pick i large enough that x̅ ∈ | Ai |n.

Then Ai ⊨ ∃ 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

    A0 ≼ A1 ≼ ⋅ ⋅ ⋅ ≼ Ai ≼ Ai+1 ≼ ⋅ ⋅ ⋅

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

    Lemma 4.16

    Let   A0 ≼ A1 ≼ ⋅ ⋅ ⋅ ≼ Ai ≼ Ai+1 ≼ ⋅ ⋅ ⋅   be an elementary chain of structures and B be the union.

    Then Ai ≼ B for every i ∈ ω.

Proof of Lemma 4.16

We prove by induction on the complexity of formulas φ that for all i ∈ ω and for all x̅ from | Ai |,

    Ai ⊨ φ ( 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̅ ∈ | Ai |n.

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

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

Pick j ≥ i large enough that y ∈ | Aj |.

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

Therefore, Aj ⊨ ∃ v ψ ( u̅ / x̅ ).

Since Ai is an elementary substructure of Aj, we conclude that Ai ⊨ ∃ v ψ ( u̅ / x̅ ).

QED

§ 4.7   Ultraproducts

As we saw in § 4.6, taking the union of a chain of structures is one way to combine infinitely many structures into a single structure. Of course, it depends on the structures we start with already fitting into a chain.

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 Ai 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

We define U to be an ultrafilter over I iff

Examples

Let S be a nonempty subset of I.

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

Filters are closely related to universal quantifiers in the following sense.

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.

    Tarski Ultrafilter Existence Theorem 4.17

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

Reduced products of sets

Suppose we have sets Si for i ∈ I.

As a reminder of common mathematical jargon, we might write   i ↦ Si   or   < Si ∣ i ∈ I >   and refer to this function as a sequence or an indexed family.

The producti ∈ I Si is the collection of functions f such that dom ( f ) = I and, for every i ∈ I, f ( i ) ∈ Si.

Let U be an ultrafilter over I.

We define a relation ≡U on ∏i ∈ I Si 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 Si / ≡U but we will write Ult ( < Si ∣ i ∈ I > , U ).

Reduced products of structures (ultraproducts)

Suppose we have structures Ai for i ∈ I.

Assume all Ai are structures in the same language.

Let U be an ultrafilter over I.

We define a structure B = Ult ( < Ai ∣ i ∈ I > , U ) called the ultraproduct as follows.

    | B | = Ult ( < | Ai | ∣ i ∈ I > , U ).

    cB = [ i ↦ cAi ]U   for every constant symbol c.

    For every n-ary function symbol F,

        FB ( [ f0 ]U , … , [ fn-1 ]U ) = [ g ]U   iff   { i ∈ I ∣ FAi ( f0 ( i ) , … , fn-1 ( i ) ) = g ( i ) } ∈ U .

    For every n-ary function symbol R,

        RB ( [ f0 ]U , … , [ fn-1 ]U )   iff   { i ∈ I ∣ RAi ( f0 ( i ) , … , fn-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 'mU fm   for all m < n and   g ' ≡U g , then, letting

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

we find that X ∈ U,

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

    iff   { i ∈ X ∣ FAi ( f0 ( i ) , … , fn-1 ( i ) ) = g ( i ) } ∈ U   iff   { i ∈ I ∣ FAi ( f0 ( i ) , … , fn-1 ( i ) ) = g ( i ) } ∈ U

and

    { i ∈ I ∣ RAi ( f '0 ( i ) , … , f 'n-1 ( i ) ) } ∈ U   iff   { i ∈ X ∣ RAi ( f '0 ( i ) , … , f 'n-1 ( i ) ) } ∈ U

    iff   { i ∈ X ∣ RAi ( f0 ( i ) , … , fn-1 ( i ) ) } ∈ U   iff   { i ∈ I ∣ RAi ( f0 ( i ) , … , fn-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

The ultraproduct is defined to be a kind of average of the structures we started with. What is true in the ultraproduct should be true in Ai for almost every i ∈ I. In fact, that is exactly what the next theorem tells us! In calculus, averages are computed using series or integrals. Here, the ultrafilter is a kind of measure and the ultraproduct is the integral of the function i ↦ Ai with respect to this measure.

    Łoś's Theorem 4.18

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

    Let U be an ultrafilter over I.

    Let B = Ult ( < Ai ∣ i ∈ I > , U ).

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

    Let   fm ∈ ∏i ∈ I | Ai |   for m < n.

    Then

        B ⊨ φ ( [ f0 ]U , … , [ fn-1 ]U )

    iff

        { i ∈ I ∣ Ai ⊨ φ ( f0 ( i ) , … , fn-1 ( i ) ) } ∈ U.

Sketch of Łoś's Theorem 4.18

By induction on the complexity of φ.

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 ∣ Ai ⊨ f ( i ) ≈ g ( i ) } ∈ U

and

    B ⊨ R ( [ f0 ]U , … , [ fn-1 ]U   iff   { i ∈ I ∣ Ai ⊨ R ( f0 ( i ) , … , fn-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

    FB ( [ f ]U , cB ) = [ g ]U

iff

    FB ( [ f ]U , [ i ↦ cAi ] ) = [ g ]U

iff

    { i ∈ I ∣ FAi ( f ( i ) , cAi ) = g ( i ) } ∈ U

iff

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

where we have used the definition of cB and FB 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 ⊨ φ ( [ f0 ]U , … , [ fn-1 ]U )

iff

    B ⊭ ψ ( [ f0 ]U , … , [ fn-1 ]U )

iff   (by the induction hypothesis)

    { i ∈ I ∣ Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) ) } ∉ U

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

    I - { i ∈ I ∣ Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) ) } ∈ U

iff

    { i ∈ I ∣ Ai ⊨ φ ( f0 ( i ) , … , fn-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 ψ ( [ f0 ]U , … , [ fn-1 ]U , v ).

Pick g so that B ⊨ ψ ( [ f0 ]U , … , [ fn-1 ]U , [ g ]U ).

By the induction hypothesis, { i ∈ I ∣ Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) , g ( i ) ) } ∈ U.

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

{ i ∈ I ∣ Ai ⊨ ∃ v ψ ( f0 ( i ) , … , fn-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 ∈ | Ai | such that Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) , y ).

Let g be a function with dom ( g ) = X such that Ai ⊨ ψ ( f0 ( i ) , … , fn-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 ) ∈ | Ai | 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 ∣ Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) , h ( i ) ) }.

Hence { i ∈ I ∣ Ai ⊨ ψ ( f0 ( i ) , … , fn-1 ( i ) , h ( i ) ) } ∈ U.

By the induction hypothesis, B ⊨ ψ ( [ f0 ]U , … , [ fn-1 ]U , [ h ]U ).

Therefore, B ⊨ ∃ v ψ ( [ f0 ]U , … , [ fn-1 ]U , v ) and we are done with the reverse direction of the existential case.

QED

Ultrapowers

We look at the special case in which Ai = A for all i ∈ I.

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

    Theorem 4.19

    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.

Proof of Theorem 4.19

As clarification, in the statement of the theorem, i ↦ x means the function with domain I and constant value x.

Now we calculate:

    B ⊨ φ ( [ i ↦ x0 ]U , … , [ i ↦ xn-1 ]U )

iff   (by Theorem 4.18)

    { i ∈ I ∣ A ⊨ φ ( x0 , … , xn-1 ) } ∈ U

iff   (see reason below)

    A ⊨ φ ( x0 , … , xn-1 ).

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

QED

Ultrapowers as alternatives to compactness

Recall Compactness Theorem 3.16 says that if every finite subtheory of Σ has a model, then so does Σ.

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.