Prove that there is a function f : A → ω such that f is a Δ_{0}^{ℕ} relation.
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 v_{0} and v_{1} }
is appropriately definable over ℕ .
The set happens to be a Δ_{0}^{ℕ} set but showing that it is Δ_{1}^{ℕ} would be enough for this application.
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.
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 ).
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.
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.
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.
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.
Prove that there are Σ_{1} formulas φ ( u ) and ψ ( u ) such that, for every n ∈ ω ,
n ∈ A iff Q ⊢ φ ( S^{n} ( Z ) )
and
n ∉ A iff Q ⊢ ψ ( S^{n} ( Z ) ) .
Hint: An idea from the proof of Lemma 5.16 is relevant here.
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^{n} ( Z ) )
and
if ( m , n ) ∉ R, then Q ⊢ ¬ φ ( S^{ m} ( Z ) , S^{n} ( Z ) ) .
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.
char_{<} ( m , n ) = 1 if m < n
char_{<} ( m , n ) = 0 otherwise .
proj_{ k , i} ( m̅ ) = m_{i} .
h ( m̅ ) = g ( f_{0} ( m̅ ) , … , f_{k-1} ( m̅ ) )
is also recursive.
g ( m̅ ) = the least n such that f ( m̅ , n ) = 0
is also recursive.
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