© Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 4

Exercise 4.1

Exercise 4.2

Exercise 4.4

Exercise 4.5

Prove that there is no theory Σ such that every model of Σ is a wellordering and Σ has an infinite model.

Exercise 4.6

Assume that ( | A | , R^A ) is a wellordering.

1. Prove that if B and C are elementary substructures of A, then | B | ∩ | C | is the universe of an elementary substructure of A.

2. Let S = { x ∈ | A | ∣ there is a formula φ ( u ) in the language of A such that ( A , x ) ⊨ ∀ u ( φ ( u ) ↔ u ≈ c_x }
   1. Prove that S is the universe of an elementary substructure of A.
   2. Prove that for every structure B, if B ≼ A, then S ⊆ | B |.

Exercise 4.7

    A = ( ℝ , 0^A , 1^A, | ⋅ | ^A, +^A , -^A , ×^A , ÷^A , <^A )

be a structure with the standard zero, one, absolute value, addition, subtraction, multiplication and division (made total) and less than.

Let π : A ≈ A^* ≼ B be as in § 4.4.

Define a relation ≡ on | B | by setting x ≡ y iff y -^B x ∈ Finite ( B ).

1. Prove that ≡ is an equivalence relation on | B |.
2. Prove that Finite = [ 0^B ].

   (Here we write [ x ] for the equivalence class of x.)

3. Prove that for every x ∈ | B |,   ( [ x ] , <^B ) is a model of DLO.
4. Prove that for all x , y ∈ | B |,   ( [ x ] , <^B ) and ( [ y ] , <^B ) are isomorphic.
5. Find a function f : ℝ → | B | such that, for all x , y ∈ ℝ, if x <^A y, then
   • f ( x ) <^B f ( y )   and
   • [ f ( x ) ] ≠ [ f ( y ) ].

Exercise 4.8

Let A be as in Exercise 4.7.

Let π : A ≈ A^* ≼ B be as in § 4.4.

Let y ∈ Finite ( B ) - | A^* |.

Prove that there is a unique way to write y as x +^B δ where x ∈ | A^* | and δ is infinitesimal.

(x is called the standard part of y.)

Follow this hint:

Let S = { x ∈ | A^* | ∣ x <^B y }.

Say why S is nonempty and S has an upper bound in A^*.

We know that A has the least upper bound property. (Do not include a proof of this fact!)

Explain why A^* has the least upper bound property too.

Therefore, S has a least upper bound in A^*.

Let   x = lub ( S ).

Let   δ = y -^B x.

Prove that δ is an infinitesimal.

Prove that if   y = x' +^B δ'   where x' ∈ | A^* | and δ' is an infinitesimal, then   x' = x   and   δ' = δ.

Exercise 4.9

Use the language from Exercise 4.8 expanded by a unary function symbol F.

Use A from Exercise 4.8 expanded so that F^A = f.

Let π : A ≈ A^* ≼ B be as in § 4.4.

Prove that the following are equivalent.

1. f is continuous at zero according to the definition from your calculus course, namely:

   For every real number s > 0, there exists a real number r > 0 such that for every real number x, if | x | < r, then | f ( x ) - f ( 0 ) | < s.

2. F^B ( 0^B ) is the standard part of F^B ( ε ) for every infinitesimal ε.

Exercise 4.10

Let A_i for i ∈ I be structures with a common language.

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

Assume that U is principal.

In other words, there exists i ∈ I such that U = { X ⊆ I ∣ i ∈ X }

Prove that B is isomorphic to A_i.

Exercise 4.11

Let U be a nonprincipal ultrafilter over ω.

Let B = Ult ( A , U ).

Draw as accurate a picture of B as you can and justify the elements of your picture with proofs.

Exercise 4.12

Say A_Δ ⊨ Δ for all finite Δ ⊆ Σ.

Let I = { Δ ⊆ Σ ∣ Δ is finite }.

For Δ ∈ I, let X_Δ = { Γ ∈ I ∣ Δ ⊆ Γ }.

Let F = { Y ⊆ I ∣ Y ⊇ X_Δ for some Δ ∈ I }.

1. Prove that F is a filter over I.
2. Let U be an ultrafilter over I such that U ⊇ F.

   Let B = Ult ( < A_Δ ∣ Δ ∈ I > , U ).

   Prove that B ⊨ Σ.

Exercise 4.13

    A = ( ℝ , 0^A , 1^A, | ⋅ | ^A, +^A , -^A , ×^A , ÷^A , <^A )

be a structure with the standard zero, one, absolute value, addition, subtraction, multiplication and division (made total) and less than.

Let U be a nonprincipal ultrafilter over ω.

Let B = Ult ( A , U ) and π : A ≈ A^* ≼ B be as in § 4.7.

As a reminder, by definition, π ( x ) = [ n ↦ x ]_U where n ↦ x is the function from ω to ℝ with constant value x.

1. Consider the identity function n ↦ n from ω to ℝ.

   Prove that [ n ↦ n ]_U is an infinite element of | B | in the sense that for every x ∈ ℝ,

       π ( x )   <^B   [ n ↦ n ]_U.

2. Consider the function n ↦ ( 1 / n ) from ω to ℝ.

   Prove that [ n ↦ ( 1 / n ) ]_U is an infinitesimal element of | B | in the sense that for every positive x ∈ ℝ,

       π ( 0 )   <^B   [ n ↦ ( 1 / n ) ]_U   <^B   π ( x ).

Exercise 4.14

Atomless Boolean algebras

We make some definitions to be used in the four exercises that follow.

For us, the language of Boolean algebras will have two constant symbols, t and f, a unary function symbol N, two binary function symbols A and O, and a binary relation symbol I. The theory of Boolean algebras (BA) has the following ten axioms.

• Associativity
• ∀ u   ∀ v   ∀ w   A ( u , A ( v , w ) ) ≈ A ( A ( u , v ) , w )
• ∀ u   ∀ v   ∀ w   O ( u , O ( v , w ) ) ≈ O ( O ( u , v ) , w )
• Commutativity
• ∀ u   ∀ v   A ( u , v ) ≈ A ( v , u )
• ∀ u   ∀ v   O ( u , v ) ≈ O ( v , u )
• Distributivity
• ∀ u   ∀ v   ∀ w   A ( u , O ( v , w ) ) ≈ O ( A ( u , v ) , A ( u , w ) )
• ∀ u   ∀ v   ∀ w   O ( u , A ( v , w ) ) ≈ A ( O ( u , v ) , O ( u , w ) )
• Identity
• ∀ u   A ( u , t ) ≈ u
• ∀ u   O ( u , f ) ≈ u
• Complementation
• ∀ u   A ( u , N ( u ) ) ≈ f
• ∀ u   O ( u , N ( u ) ) ≈ t
• Order
• ∀ u   ∀ v   [ I ( u , v ) ↔ A ( u , v ) ≈ u ]

Intuitively, t stands for "true", f stands for "false", N stands for "not", A stands for "and", O stands for "or", and I stands for "implies".

The theory of atomless Boolean algebras (ABA) has one additional axiom:

∀ v   [ ¬ ( v ≈ F ) → ∃ u   [ I ( u , v ) ∧ ¬ ( f ≈ u ) ∧ ¬ ( u ≈ v ) ]

Exercise 4.15

Let Σ_n be the set of propositional sentences that involve only P_i for i < n.

Let ╞╡_n be the propositional logical equivalence relation restricted to Σ_n.

Recall that ╞╡_n is an equivalence relation on Σ_n.

Define structures B_n in the language of Boolean algebras by:

• The universe of B_n is

          | B_n | = Σ_n / ╞╡_n

  In other words, for each φ ∈ Σ_n, the equivalence class

          [ φ ]_n = {  ψ ∈ Σ_n  |   ψ ╞╡_n φ   }

  is a member of | B_n | , and these are all the members.

• t ^B_n = [ ⊤ ]_n
• f ^B_n = [ ⊥ ]_n
• For all propositional sentences φ , ψ ∈ Σ_n,
  • N ^B_n ( [ φ ]_n ) = [ ¬ φ ]_n
  • A ^B_n ( [ φ ]_n , [ ψ ]_n ) = [ φ ∧ ψ ]_n
  • O ^B_n ( [ φ ]_n , [ ψ ]_n ) = [ φ ∨ ψ ]_n
  • I ^B_n ( [ φ ]_n , [ ψ ]_n )   iff   φ ⊨ ψ

It is easy to see that these definitions of N ^B_n , A ^B_n , O ^B_n , and I ^B_n do not depend on the choice of representatives.

It is easy to see that each B_n is a finite model of the Associativity, Commutativity, Distributivity, Identity and Complementation axioms.

1. Explain why B_n satisfies the Order axiom of Boolean algebras.
2. Explain why B_n is not an atomless Boolean algebra.

Exercise 4.16

1. Give an example of a Boolean algebra C₃ of cardinality eight.

   Explain why C₃ is not isomorphic to any of the Boolean algebras B_n from Exercise 4.15.

2. More generally, explain why, for every a ∈ ω, there exists a Boolean algebra C_a whose universe is

           | C_a | = P ( a ) = { X   |   X ⊆ a }

   and, for all members X and Y of | C_a |,

           I ^C_a ( X , Y )   iff   X ⊆ Y.

3. Prove that each finite Boolean algebra D is isomorphic to exactly one C_a.

   Hint for 4.16.3     For y ∈ | D |, define y to be an atom of D   iff

           y ≠ f ^D and, for every x, if x I ^D y , then x = f ^D or x = y.

   Let a be the number of atoms of D.

Exercise 4.17

Let Σ be the set of propositional sentences.

Recall that the propositional logical equivalence relation ╞╡ is an equivalence relation on Σ.

Define structures B in the language of Boolean algebras by:

• The universe of B is

          | B | = Σ / ╞╡

  In other words, for each φ ∈ Σ , the equivalence class

          [ φ ] = {  ψ ∈ Σ  |   ψ ╞╡ φ   }

  is a member of | B | , and these are all the members.

• t ^B = [ ⊤ ]
• f ^B = [ ⊥ ]
• For all propositional sentences φ , ψ ∈ Σ ,
  • N ^B ( [ φ ] ) = [ ¬ φ ]
  • A ^B ( [ φ ] , [ ψ ] ) = [ φ ∧ ψ ]
  • O ^B ( [ φ ] , [ ψ ] ) = [ φ ∨ ψ ]
  • I ^B ( [ φ ] , [ ψ ] )   iff   φ ⊨ ψ

It is easy to see that these definitions of N ^B , A ^B , O ^B , and I ^B do not depend on the choice of representatives.

It is easy to see that B is a countable Boolean algebra.

Explain why B is an atomless.

Exercise 4.18

Let C and D be atomless Boolean algebras.

1. Suppose that π is an isomorphism from ( | C | , I ^C ) to ( | D | , I ^D ).

   Prove that π is an isomorphism from C to D.

2. Suppose that C and D are countable.

   Use a back and forth argument to prove there is an isomorphism from ( | C | , I ^C ) to ( | D | , I ^D ).

Hints for Exercise 4.18

For Part 1, start by proving that, for all x, y ∈ | C |,

        O^C ( x , y ) = the I ^C -least z such that x I ^C z and y I ^C z.

For Part 2, start by fixing enumerations of the two universes:

        | C | = { x₀ , x₁ , ... , x_n , ... }

        | D | = { y₀ , y₁ , ... , y_n , ... }

By recursion on n ∈ ω, define

        S_n   ⊆   | C |

        T_n   ⊆   | D |

        π_n   :   A ↾ S_n   ≈   B ↾ T_n

such that

        S_n , T_n and π_n are finite

        x_n ∈ S_{n + 1}

        y_n ∈ T_{n + 1}

        S_n is the universe of a substructure of C

        T_n is the universe of a substructure of D

More hints for both parts of Exercise 4.18 might be added later.

(As it stands, it is a bit harder than others.)

Exercise 4.19

1. Find an uncountable Boolean algebra that has atoms.
2. Find a countable Boolean algebra that has atoms.