Math 597B – Homework #3

February 23, 2007

Recall that ∨ and ∧ denote, respectively, join (i.e., the least upper bound operator) and meet (i.e., the greatest lower bound operator) in the partial ordering of Turing degrees. A Turing degree c is said to be join-reducible (respectively meet-reducible) if there exist Turing degrees a ≠ c and b ≠ c such that a ∨ b = c (respectively a ∧ b = c).

Note: For an arbitrary pair of Turing degrees a = deg_{T} (f) and b = deg_{T} (g), we always have a ∨ b = deg_{T} (f ⊕ g). On the other hand, a ∧ b may or may not exist. See Problem 7 below.

1. Prove that 0 is meet-reducible.

2. By relativizing Problem 1, prove that every Turing degree is meetreducible.

3. Prove that 0′ is join-reducible.

4. By relativizing Problem 3 and applying the Friedberg Jump Theorem, prove that every Turing degree c ≥ 0′ is join-reducible.

Note: It can be shown that not every Turing degree c > 0 is joinreducible.

5. Prove the following theorem.

Given an ascending sequence of Turing degrees

c_{1} < c_{2} < ⋯ < c_{n} < ⋯

we can find a pair of Turing degrees a, b such that for all d, ∃n (d ≤ c_{n}) if and only if d ≤ a and d ≤ b.

6. Use the result of Problem 5 to prove that no ascending sequence of Turing degrees has a least upper bound.

7. For any pair of Turing degrees a, b as in Problem 5, prove that a ∧ b does not exist.