© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Exercises for Chapter 6

Exercise 6.1

Exercise 6.2

Exercise 6.3

Let V₀ = { ( c , n ) ∣ c is the code of a pair ( m₀ , m₁ ) and ( m₀ , n ) ∈ U } .

Let V₁ = { ( c , n ) ∣ c is the code of a pair ( m₁ , m₁ ) and ( m₁ , n ) ∈ U } .

1. It is easy to see that V₀ and V₁ are Σ₁^ℕ relations. Give a brief explanation.
2. It is easy to see that if ( A , B ) is a pair of Σ₁^ℕ sets, then there exists c ∈ ω such that

       A = { n ∣ ( c , n ) ∈ V₀ }   and   B = { n ∣ ( c , n ) ∈ V₁ } .

   Give a brief explanation.

3. It is easy to generalize the idea used in Exercise 5.10 to obtain Σ₁^ℕ relations V₀^* and V₁^* such that

       V₀^* ⊆ V₀ ,

       V₁^* ⊆ V₁ ,

       V₀^* ∩ V₁^* = { }   and

       V₀^* ∪ V₁^* = V₀ ∪ V₁ .

   Give a brief explanation.

4. Prove that there is no Δ₁^ℕ relation W such that V₀^* ⊆ W and V₁^* ∩ W = { } .

   Hint: Consider the sets A = { c ∣ ( c , c ) ∉ W } and B = ω - A = { c ∣ ( c , c ) ∈ W } .

Exercise 6.4