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 pP, |{q | qP p}| ≤ ℵ0.

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

Obviously 〈image, ≤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.

Get Recursion Theory now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.