Ernest Schimmerling ; Basic and Intermediate
Logic ; Chapter 6 exercises
Online textbook for Basic and Intermediate Logic
Exercises for Chapter 6
Exercise 6.1
Prove Lemma 6.2.
Exercise 6.2
Prove there is no
Δ_{1}^{ℕ} relation
that is universal for
Δ_{1}^{ℕ} sets.
Exercise 6.3
Let U be as in § 6.1.
Let V_{0} = { ( c , n )
∣ c is the code of a pair
( m_{0} , m_{1} ) and
( m_{0} , n ) ∈ U } .
Let V_{1} = { ( c , n )
∣ c is the code of a pair
( m_{1} , m_{1} ) and
( m_{1} , n ) ∈ U } .

It is easy to see that V_{0} and V_{1} are
Σ_{1}^{ℕ} relations.
Give a brief explanation.

It is easy to see that if ( A , B ) is a pair of
Σ_{1}^{ℕ} sets,
then there exists c ∈ ω such that
A = { n ∣ ( c , n ) ∈ V_{0} }
and
B = { n ∣ ( c , n ) ∈ V_{1} } .
Give a brief explanation.

It is easy to generalize the idea used in Exercise 5.10
to obtain Σ_{1}^{ℕ} relations
V_{0}^{*}
and
V_{1}^{*} such that
V_{0}^{*} ⊆ V_{0} ,
V_{1}^{*} ⊆ V_{1} ,
V_{0}^{*}
∩
V_{1}^{*} = { } and
V_{0}^{*}
∪
V_{1}^{*} =
V_{0}
∪
V_{1} .
Give a brief explanation.

Prove that there is no
Δ_{1}^{ℕ}
relation W
such that
V_{0}^{*} ⊆ W and
V_{1}^{*} ∩ W = { } .
Hint:
Consider the sets A
= { c ∣ ( c , c ) ∉ W }
and B = ω  A = { c ∣ ( c , c ) ∈ W } .
Exercise 6.4
Use Lemma 6.2 to give a different proof of Tarski's Undefinability
of Truth 6.6.