Results on relative computability, category, and automorphisms of the Turing degrees

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Reductions: composition, computable sets, countability — Lemma 2.1. A reduction is a computably enumerable set of triples (string, argument, value). There is a reduction computing A from A; reductions compose; a set is computable iff it is computable from the empty set; at most countably many sets are computable from a given set.
• Automorphisms of the degrees preserve the least degree and joins — Lemma 3.3. An order automorphism of the Turing degrees fixes the degree of the computable sets and satisfies pi(a v b) = pi(a) v pi(b); its inverse is an automorphism.
• Uniform computation of a sequence computed step by step — Lemma 4.1. If X_0 is computable from T and each X_(n+1) is computed from X_n + T by one of two fixed reductions, selected by one fixed bit of X_n, then the whole sequence, and the sequence of the selections, is computable from T by one reduction.
• Real numbers as cuts — Lemma 5.1. The cut map is one-to-one; the degree of a rational affine combination of reals is at most the join of their degrees; every noncomputable degree is the degree of an irrational number in (0,1).
• Baire's theorem in the line and the plane — Theorem 1.1. A nonempty open subset of R or R^2 is not meager; a comeager set is dense.
• A Borel function is continuous on a comeager set — Lemma 2.2. For a Borel function from R or R^2 to the Cantor space or to the natural numbers there is a comeager set on which its restriction is continuous.
• The least index of a reduction for sums is a Borel function — Lemma 3.2. If F is a Borel function from the reals to sets with F(x+y) computable from F(x) + F(y) for all x, y, then the least index of a reduction computing F(x+y) from F(x) + F(y) is a Borel function of (x,y).
• The avoidance lemma — Lemma 4.1. If Y is not computable from A, then the set of pairs (u,v) of reals such that Y is computable from A and the cuts of u and v is meager.
• Recovery from four values — Theorem 1.1. Let F be a Borel function from the reals to sets with countable fibres and F(x+y) computable from F(x) + F(y). For an irrational t in (0,1) and all (u,v) in a comeager set there is a rational delta in (0,1) such that the cut of t is computable from F(u) + F(u-v) + F(v-u+delta t) + F(v-u+delta(t-1)).
• The bounded walk — Lemma 3.1. The walk s_(n+1) = s_n + delta(t - r_n), with r_n read from one bit of F(u+s_n) that sends the walk inwards near both ends, stays in [b_-, b_+], and s_n = delta(n t - sum of r_k).
• From a Borel representation to a function on the line — Lemma 2.1. If a Borel function Fhat represents an automorphism pi, then F = Fhat o C is Borel on the reals, deg F(x) = pi(d(x)), F has countable fibres, and F(x+y) is computable from F(x) + F(y).
• An automorphism with a Borel representation moves no degree downwards — Theorem 3.1. If an automorphism pi of the Turing degrees is represented by a Borel function, then a <= pi(a) for every degree a. No hypothesis is used.
• Rigidity of the Turing degrees — Theorem 3.2. Assume the theorem of Slaman and Woodin that every automorphism of the Turing degrees has a Borel representation (hypothesis (SW), not proved in the course). Then every automorphism of the Turing degrees is the identity.

Reading order

Four lessons with complete proofs, except for one named hypothesis in the fourth lesson: the theorem of Slaman and Woodin that every automorphism of the Turing degrees is represented by a Borel function. The first two lessons give the tools (relative computability; category). The third proves the recovery theorem, the new part of the argument. The fourth proves without a hypothesis that an automorphism with a Borel representation moves no degree downwards, and derives rigidity from the hypothesis.