© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 5

Exercise 5.1

Prove that there is a function f : A → ω such that f is a Δ₀^ℕ relation.

Exercise 5.2

• If m is not the Gödel number of a bounded formula whose free variables are v₀ and v₁, then define f ( m ) = 0.
• Otherwise, let ψ ( v₀ , v₁ ) be the bounded formula such that m = ⌜ ψ ⌝ .
  • If ℕ ⊨ ψ ( m , m ) , then define f ( m ) = m + 1 .
  • If ℕ ⊨ ¬ ψ ( m , m ) , then define f ( m ) = m .

Clearly, f is not a Δ₀^ℕ function.

It is pretty clear that we could write a program to compute values of f.

By Lemma 5.6, which we did not prove, f is a Δ₁^ℕ function.

Give a direct description of a Σ₁ formula that defines f over ℕ.

Note:

"Direct" means do not go through computer programs at all.

To build φ , part of what you need to explain is why the set

    { ⌜ ψ ⌝ ∣ ψ is a formula whose free variables are v₀ and v₁ }

is appropriately definable over ℕ .

The set happens to be a Δ₀^ℕ set but showing that it is Δ₁^ℕ would be enough for this application.

Exercise 5.3

    Q ⊢ SUB ( S ^m ( Z ) , S ⁿ ( Z ) , S ^{m ∸ n} ( Z ) )

and

    Q ⊢ ∀ w ( SUB ( S ^m ( Z ) , S ⁿ ( Z ) , w ) → w ≈ S ^{m ∸ n} ( Z ) ) .

Prove your formula has this property.

Exercise 5.4

Exercise 5.5

Hint: Start by proving the following combinatorial fact. For every sequence ⟨ f_i ∣ i ∈ ω ⟩ of functions on ω, there exists a function g on ω such that for every i ∈ ω there exists m ∈ ω such that for every n ∈ ω, if m ≤ n, then g ( n ) > f_i ( n ).

Exercise 5.6

Let ℕ'' be a model of Theory ( ℕ ) and x̅'' ∈ | ℕ'' |ⁿ.

Prove that there exists x̅' ∈ | ℕ' |ⁿ such that, for every formula φ ( u̅ ) in the language of arithmetic,

    ℕ'' ⊨ φ ( x̅'' )

iff

    ℕ' ⊨ φ ( x̅' ).

Remarks on terminology:

The set of formulas true about x̅'' in ℕ'' is called a complete n-type for Theory ( ℕ ).

Recall that atomic types were used in the proof of Theorem 4.11.

Exercise 5.6 shows that every consistent n-type for Theory ( ℕ ) is realized by an n-tuple in the ultrapower.

Because of this, one says that the ultrapower is saturated.

Exercise 5.7

Prove there is a bounded formula φ^* ( u̅ ) in which all the bounded quantifiers lead a quantifier-free subformula such that

    ⊢ ∀ u̅ ( φ ↔ φ^* ).

Hint: Use induction on the complexity of φ. You may assume that φ is built-up from atomic formulas using just negation, disjunction and bounded quantification.

Exercise 5.9

Find Σ₁^ℕ sets A^* and B^* such that   A ⊇ A^* ,   B ⊇ B^* ,   A^* ∩ B^* = { }   and   A^* ∪ B^* = A ∪ B .

Hint: Intuitively, let A^* be the set of n that get into A before they get into B.

Remark on terminology: This is the reduction property for Σ₁^ℕ sets.

Exercise 5.10

Find a Δ₁^ℕ set C such that   A ⊆ C   and   B ⊆ ℕ - C .

Hint: Use Exercise 5.9.

Remark on terminology: This is the separation property for Π₁^ℕ sets.

Exercise 5.11

Prove that there are Σ₁ formulas φ ( u ) and ψ ( u ) such that, for every n ∈ ω ,

    n ∈ A   iff   Q ⊢ φ ( Sⁿ ( Z ) )

and

    n ∉ A   iff   Q ⊢ ψ ( Sⁿ ( Z ) ) .

Hint: An idea from the proof of Lemma 5.16 is relevant here.

Exercise 5.12

For R : ω × ω , we say that R is a binary relation that is representable in Q iff there is a formula φ ( u , v ) such that for every m , n ∈ ω,

    if ( m , n ) ∈ R, then Q ⊢ φ ( S ^m ( Z ) , Sⁿ ( Z ) )

    and

    if ( m , n ) ∉ R, then Q ⊢ ¬ φ ( S ^m ( Z ) , Sⁿ ( Z ) ) .

1. Prove that the following are equivalent.
   • f is a unary function and f is a binary relation that is representable in Q.
   • f is a unary function that is representable in Q.

2. Prove that the following are equivalent.
   • R is a binary relation that is representable in Q.
   • R is a Δ₁^ℕ binary relation.

Exercise 5.13

Exercise 5.14 [ Tweak this ]

Recursively define   h : ω × ω^k → ω   by the equations

    h ( 0 , n̅ ) = f ( n̅ )

    and

    h ( m + 1 , n̅ ) = g ( h ( m , n̅ ) , m , n̅ ) .

Prove that h is a Σ₁^ℕ function.

Exercise 5.15 [ Tweak this ]

• The following functions are recursive:
  • Successor   m ↦ m + 1 .
  • Addition   ( m , n ) ↦ m + n .
  • Multiplication   ( m , n ) ↦ m × n .
  • Exponentiation   ( m , n ) ↦ mⁿ .
  • The characteristic function   char_< : ω² → ω   given by

        char_< ( m , n ) = 1   if m < n

        char_< ( m , n ) = 0   otherwise .

  • The various projection functions   proj _{k , i} : ω^k → ω   given by

        proj _{k , i} ( m̅ ) = m_i .

• Given recursive functions   g : ω^k → ω   and   f_i : ω^k → ω   for i < k , the composition function h : ω^k → ω defined by

          h ( m̅ ) = g ( f₀ ( m̅ ) , … , f_k-1 ( m̅ ) )

  is also recursive.

• If f : ω^k → ω is recursive and for every m̅ ∈ ω^k , there exists n ∈ ω such that f ( m̅ , n ) = 0 , then the function g : ω^k → ω defined by

          g ( m̅ ) = the least n such that f ( m̅ , n ) = 0

  is also recursive.

1. Prove that for every function f : ω^k → ω , if f is recursive, then f is Σ₁^ℕ.
2. Prove that for every function f : ω^k → ω , if f is Σ₁^ℕ , then f is recursive.

Exercise 5.16 [ Not sure ]

Vague hint:

Let ℕ'' be a nonstandard model of Theory ( ℕ ) .

Let x and y be infinite members of | ℕ' | .

Try to define a model ℕ' of Q with

• | ℕ' | = | ℕ'' | ,
• Z^ℕ' = Z^ℕ'' ,
• S^ℕ' = S^ℕ'' and
• A^ℕ' ( Z^ℕ' , x ) = y .