Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 4 exercises

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 4

Exercise 4.1

Prove that ( ℚ , < ) is an elementary substructure of ( ℝ , < ).

Exercise 4.2

Prove that ( ℝ , < ) and ( { x ∈ ℝ ∣ x ≠ 0 } , < ) are not isomorphic.

Exercise 4.3

Describe an algorithm that takes as an input a formula φ ( u̅ ) and outputs a quantifier-free formula ψ ( u̅ ) such that

    DLO ⊢ ∀ u̅ ( φ ↔ ψ ).

Exercise 4.4

Prove that there is no theory Σ such that every model of Σ is a model of DLO with the least upper bound property.

Exercise 4.5

A structure A = ( | A | , RA ) is a wellordering iff A is a linear ordering and, for every nonempty S ⊆ | A |, there exists x ∈ S such that for all y ∈ S, either   x RA y   or   x = y.

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

Exercise 4.6

Let A be a structure in a language that includes a binary relation symbol R. (There may be other symbols too.)

Assume that ( | A | , RA ) 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 ≈ cx }

    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

Let

    A = ( ℝ , 0A , 1A, | ⋅ | 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 = [ 0B ].

    (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

Let f : ℝ → ℝ be a function.

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

Use A from Exercise 4.8 expanded so that FA = 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. FB ( 0B ) is the standard part of FB ( ε ) for every infinitesimal ε.

Exercise 4.10

Let I be an infinite set and U be an ultrafilter over I.

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

Let B = Ult ( < Ai ∣ 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 Ai.

Exercise 4.11

Let A = ( ω , <A ) where <A is the usual ordering of ω.

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

Let Σ be a theory whose finite sub-theories are consistent.

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

Let

    A = ( ℝ , 0A , 1A, | ⋅ | 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

(This exercise is for those with more set theory background.)

The upward and downward Löwenheim-Skolem theorems in Chapter 4 only distinguish between finite, countable and uncountable languages, structures and sets. More generally, the cardinality of a structure is the cardinality of its universe.

  1. Let B be an infinite structure for a countable language and X be an infinite subset of | B |.

    Then there exists an elementary substructure A of B with X ⊆ | A | such that A has the same cardinality as X.

  2. Let A be an infinite structure.

    Say A has cardinality κ and λ > κ.

    Then there exists an elementary extension B of A such that the cardinality of B is λ.