Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 6 exercises

# Online textbook for Basic and Intermediate Logic

## Exercises for Chapter 6

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 V0 = { ( c , n ) ∣ c is the code of a pair ( m0 , m1 ) and ( m0 , n ) ∈ U } .

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

1. It is easy to see that V0 and V1 are Σ1 relations. Give a brief explanation.
2. 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 ) ∈ V0 }   and   B = { n ∣ ( c , n ) ∈ V1 } .

Give a brief explanation.

3. It is easy to generalize the idea used in Exercise 5.10 to obtain Σ1 relations V0* and V1* such that

V0* ⊆ V0 ,

V1* ⊆ V1 ,

V0* ∩ V1* = { }   and

V0* ∪ V1* = V0 ∪ V1 .

Give a brief explanation.

4. Prove that there is no Δ1 relation W such that V0* ⊆ W and V1* ∩ 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.