Recursion Theory

9 Independence results in recursion theory

9.1 Independent sets of Turing degrees

9.1.1 Locally countable partial ordering

Definition 9.1.1. A partially ordered set 〈P, ≤P〉 is locally countable if for any p ∈ P, |{q | q ≤P p}| ≤ ℵ0.

Definition 9.1.2. A function f : 〈P, ≤P〉 → 〈Q, ≤Q〉 is an embedding if (∀p0, p1 ∈ P) (p0 ≤ p1 ⇔ f(p0) ≤Q f(p1)).

Obviously 〈, ≤T〉, the partial ordering of the Turing degrees, is locally countable. Sacks made the following conjecture.

Conjecture 9.1.3 (Sacks [117]). Every locally countable partial ordering on 2ω is embeddable into 〈, ≤T〉.

A positive solution is known assuming the Continuum Hypothesis:

Theorem 9.1.4.