Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 5 exercises

# Online textbook for Basic and Intermediate Logic

## Exercises for Chapter 5

#### Exercise 5.1

Let A be a Σ1 set.

Prove that there is a function f : A → ω such that f is a Δ0 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 v0 and v1, then define f ( m ) = 0.
• Otherwise, let ψ ( v0 , v1 ) 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 Δ0 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 Δ1 function.

Give a direct description of a Σ1 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 v0 and v1 }

is appropriately definable over ℕ .

The set happens to be a Δ0 set but showing that it is Δ1 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 n ( Z ) , S m ∸ n ( Z ) )

and

Q ⊢ ∀ w ( SUB ( S m ( Z ) , S n ( 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 ⟨ fi ∣ 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 ) > fi ( n ).

#### Exercise 5.6

Let U be a nonprincipal ultrafilter over ω and ℕ' = Ult ( ℕ , U ).

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

Prove that there exists x̅' ∈ | ℕ' |n 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 Σ1 sets.

Find Σ1 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 Σ1 sets.

#### Exercise 5.10

Let A and B be disjoint Π1 sets.

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

Hint: Use Exercise 5.9.

Remark on terminology: This is the separation property for Π1 sets.

#### Exercise 5.11

Let A be a Δ1 set.

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

n ∈ A   iff   Q ⊢ φ ( Sn ( Z ) )

and

n ∉ A   iff   Q ⊢ ψ ( Sn ( 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 ) , Sn ( Z ) )

and

if ( m , n ) ∉ R, then Q ⊢ ¬ φ ( S m ( Z ) , Sn ( 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 Δ1 binary relation.

#### Exercise 5.13

Prove that for every function Σ1 function from ωk to ω is a Δ1 function.

#### Exercise 5.14 [ Tweak this ]

Suppose that   f : ωk → ω   and   g : ω × ω × ωk → ω   are Σ1 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 Σ1 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 ) ↦ mn .
• The characteristic function   char< : ω2 → ω   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̅ ) = mi .

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

h ( m̅ ) = g ( f0 ( m̅ ) , … , fk-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 Σ1.
2. Prove that for every function f : ωk → ω , if f is Σ1 , 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 .