Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 5 exercises

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 5

Exercise 5.1

Let A be a Σ₁^ℕ set.

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

Exercise 5.2

Define a function f : ω ↔ ω as follows.

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

Find a formula SUB ( u , v , w ) in the language of arithmetic such that for every m , n ∈ ω

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

Finish the proofs of the facts mentioned in § 5.3.

Exercise 5.5

Prove that | ℕ' | is uncountable where ℕ' = Ult ( ℕ , U ) and U is a nonprincipal ultrafilter over ω.

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 U be a nonprincipal ultrafilter over ω and ℕ' = Ult ( ℕ , U ).

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

Let φ ( u̅ ) be a bounded formula.

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

Let A and B be Σ₁^ℕ sets.

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

Let A and B be disjoint Π₁^ℕ sets.

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

Let A be a Δ₁^ℕ set.

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

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.
Prove that the following are equivalent.
- R is a binary relation that is representable in Q.
- R is a Δ₁^ℕ binary relation.

Exercise 5.13

Prove that for every function Σ₁^ℕ function from ω^k to ω is a Δ₁^ℕ function.

Exercise 5.14 [ Tweak this ]

Suppose that f : ω^k → ω and g : ω × ω × ω^k → ω are Σ₁^ℕ functions.

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 ]

Recursive functions are built up according to the following scheme.

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.

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

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

Exercise 5.16 [ Not sure ]

Define a model ℕ' of Q with some x ∈ | ℕ' | with A^ℕ' ( Z^ℕ' , x ) ≠ x.

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 .