42.04.04 · mathematical-logic / computability-degrees

Turing Reducibility, Oracles, and the Jump

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 3-4 and the historical notes (oracle computation and relativisation, the use principle, the structure of the degrees $\mathcal D$ as an upper semilattice, the jump as a strictly increasing monotone operator, $A'$ as the $\le_m$-complete $A$-c.e. set, the iterated jumps $A^{(n)}$ and the hierarchy $\mathbf 0, \mathbf 0', \mathbf 0'', \dots$, the relativisation principle, the uncountability of $\mathcal D$, the embedding of every countable partial order, incomparable and minimal degrees by counting/forcing); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 9-13 (relative recursiveness, the jump hierarchy, the degrees of unsolvability); Lerman 1983 *Degrees of Unsolvability* (Springer) Ch. I-VI (the algebraic structure of $\mathcal D$, embeddings, minimal degrees, the jump)

Intuition Beginner

The previous unit lived in a world of plain computers: programs that run on their own, with no help from outside. This unit hands every program a telephone. The phone connects to an information desk that knows, for one fixed set of numbers $A$ , whether any number you name is in $A$ or not. The program may dial the desk whenever it likes, ask "is $5$ in $A$ ?", get a yes-or-no answer in a single step, and use that answer to decide what to do next. A machine wired up this way is called an oracle machine, and the set $A$ is its oracle. Computing with such help is called relative computation.

The phone changes what is possible. The halting set from before could not be decided by any ordinary program. But if your oracle is the halting set itself, then deciding membership is one phone call. So "what a program can compute" is no longer a fixed thing; it depends on which oracle the program is allowed to consult. This gives a way to compare two problems by hardness. We say problem $A$ is no harder than problem $B$ if a program with a phone line to $B$ can decide $A$ . Written down, this is Turing reducibility, $A \leq_{T} B$ : solve $A$ using $B$ as a helper.

Once you can compare problems by hardness, you can group together the ones that are equally hard — each solvable using the other as oracle — into a single bundle called a degree. The easiest bundle holds every problem an ordinary computer already solves; call it the bottom. Above it sit harder and harder bundles, and there is a machine, the jump, that takes any bundle and produces a strictly harder one: the halting problem for machines holding that bundle as oracle. Starting at the bottom and jumping over and over builds an endless ladder of increasing difficulty. The rest of this unit makes the phone, the comparison, the bundles, and the ladder precise.

Visual Beginner

An oracle machine is an ordinary machine with a phone line to a set $A$ . Picture it asking questions and reading off answers as it runs.

   oracle machine  Phi_e  with oracle set  A = {0, 3, 4, 7, ...}

   work tape:  [ . . computing . . ]
        |
        |  "is 3 in A?"   --->  [ ORACLE for A ]   --->  YES
        |  "is 5 in A?"   --->  [ ORACLE for A ]   --->  NO
        |  "is 7 in A?"   --->  [ ORACLE for A ]   --->  YES
        v
   keeps computing, branching on each answer, until it halts (or not)

   The "use" = the largest number it ever asked about.
   Here it only asked about 3, 5, 7, so the use is 7:
   the answer depends only on A's membership for 0,1,...,7.

Now picture the ladder of hardness the jump builds. Each rung is a bundle of equally-hard problems; the jump carries each rung up to a strictly harder one.

   harder
     ^
     |   0'''  =  jump of jump of jump of bottom
     |   0''   =  jump of jump of bottom
     |   0'    =  the halting problem's bundle
     |   0     =  the bottom: everything a plain computer solves
   easier

   Each step UP is "the halting problem, for machines that already
   have the rung below as their oracle."  The ladder never stops.

you give the jump...	it hands back...	which is...
the bottom bundle $0$	$0^{'}$	the halting problem, strictly harder
any bundle $d$	$d^{'}$	strictly harder than $d$
a harder bundle	an even harder one	the jump is order-preserving

Read the table as: the jump is an engine that always climbs, never stalls, and respects the ordering — feed it something higher and you get out something higher.

Worked example Beginner

We show concretely that a phone line to the halting set lets you solve a problem an ordinary computer cannot. Recall the halting set $K$ : the numbers $e$ such that program $e$ , run on its own number, eventually stops. No plain program decides $K$ . Let the oracle be $K$ itself, and let the task be to decide $K$ .

Step 1. The task with the right phone is one call. To decide "is $e$ in $K$ ?", the oracle machine simply asks its phone, "is $e$ in $K$ ?", and copies the answer. One question, one answer, done. So $K$ is decidable relative to the oracle $K$ — written $K \leq_{T} K$ , which just says a problem is no harder than itself.

Step 2. A genuinely useful call. Consider the complement: the numbers $e$ such that program $e$ does not halt on its own number. An ordinary computer cannot list this set, let alone decide it. But with a phone line to $K$ , deciding it is again one call and a flip: ask "is $e$ in $K$ ?", and answer the opposite. So the complement of $K$ is also decidable relative to $K$ .

Step 3. Read off the comparison. The complement of $K$ is no harder than $K$ once you have the oracle, even though without the oracle it sat outside everything ordinary computers can do. The phone has equalised them: $K$ and its complement land in the same bundle of hardness.

What this tells us: relative computation measures problems against each other, not against the fixed floor of ordinary computation. A problem can be hopeless on its own yet easy given the right helper. The bundles of "equally hard given each other" are exactly the degrees, and the next sections build the ladder of them and the jump that climbs it.

Check your understanding Beginner

Formal definition Intermediate+

Fix the standard enumeration of partial computable functions and the c.e. machinery from 42.04.03. An oracle Turing machine has, besides its work tape, a query tape and a distinguished query state; running with oracle $A \subseteq N$ , when it enters the query state with $n$ on the query tape it transitions in one step according to whether $n \in A$ . The $e$ -th oracle machine computes the partial functional $Φ_{e}^{A}$ ; we write $Φ_{e}^{A} (x) ↓$ when the computation halts. A set $B$ is $A$ -computable if $χ_{B} = Φ_{e}^{A}$ for some $e$ , and $A$ -computably enumerable ( $A$ -c.e.) if $B = dom (Φ_{e}^{A})$ for some $e$ . All theorems relativise: replacing the plain model by the $A$ -oracle model preserves the enumeration theorem, the s-m-n theorem, and the recursion theorem.

The use principle ^{[Soare Ch. 3]}: if $Φ_{e}^{A} (x) ↓$ then the computation queries the oracle at only finitely many numbers, and the use $φ_{e}^{A} (x)$ is one more than the largest queried (or $0$ if none). Convergence depends only on $A ↾ φ_{e}^{A} (x) = {n < φ_{e}^{A} (x) : n \in A}$ , so for any $B$ with $B ↾ φ_{e}^{A} (x) = A ↾ φ_{e}^{A} (x)$ one has $Φ_{e}^{B} (x) ↓$ with the same value and use (the use lemma). Convergent computations are thus finitely determined and permanent under oracle agreement below the use.

A set $A$ is Turing reducible to $B$ , written $A \leq_{T} B$ , if $χ_{A}$ is $B$ -computable: $χ_{A} = Φ_{e}^{B}$ for some $e$ . Then $\equiv_{T}$ is mutual reducibility, $A \equiv_{T} B ⟺ A \leq_{T} B \leq_{T} A$ . Many-one reducibility strengthens Turing reducibility: $A \leq_{m} B \Rightarrow A \leq_{T} B$ (decide $x \in A$ by querying $B$ at $f (x)$ ), but the converse fails — $\overline{K} \leq_{T} K$ (one query and a flip) while $\overline{K} \neq \leq_{m} K$ (else $\overline{K}$ would be c.e.). A set $A$ is computable iff $A \leq_{T} \emptyset$ .

The Turing degrees are the equivalence classes $D = P (N) / \equiv_{T}$ , partially ordered by $de g (A) \leq de g (B) ⟺ A \leq_{T} B$ . The least element is $0 = de g (\emptyset)$ , the computable degree. The join is $A \oplus B = {2 n : n \in A} \cup {2 n + 1 : n \in B}$ ; $de g (A \oplus B) = de g (A) \lor de g (B)$ is the least upper bound, so $D$ is an upper semilattice with least element $0$ (not a lattice — meets can fail).

The Turing jump of $A$ is $$ A' = {, e : \Phi_e^A(e)!\downarrow ,} = K^A, $$ the halting problem relative to $A$ . The iterated jumps are $A^{(0)} = A$ and $A^{(n + 1)} = (A^{(n)})^{'}$ ; writing $\emptyset^{(n)} = 0^{(n)}$ as sets gives the hierarchy $\emptyset, \emptyset^{'}, \emptyset^{''}, \dots$ whose degrees $0, 0^{'}, 0^{''}, \dots$ are the backbone of the arithmetical hierarchy 42.04.05.

Counterexamples to common slips Intermediate+

" $A \leq_{T} B$ is the same as $A \leq_{m} B$ ." Turing reducibility allows many adaptive queries and negative answers; many-one reducibility allows one positive query. The gap is real: $\overline{K} \equiv_{T} K$ but $\overline{K} \neq \leq_{m} K$ . Turing reducibility is the coarser, more permissive relation, which is why degrees collapse a set and its complement.
"The use can be unbounded along a convergent computation." On any single convergent input the use is a finite number — a halting computation runs finitely long and so makes finitely many queries. What can be unbounded is the use as a function of the input $x$ ; per input it is finite, and that finiteness is the use lemma's content.
" $D$ is a lattice." It is only an upper semilattice. Every pair has a least upper bound (the join), but not every pair has a greatest lower bound; the exact-pair theorem exhibits pairs with no infimum. Reading $\oplus$ as 'and' is fine; there is no dual 'meet' operation in general.
" $A^{'}$ depends on the chosen oracle machine enumeration, so it is not well-defined." Different acceptable enumerations give jumps that are $\equiv_{T}$ (indeed $\equiv_{1}$ ) and differ by a computable index translation, so the degree $a^{'} = de g (A^{'})$ is independent of the enumeration. The jump is a well-defined operator on degrees.

Key theorem with proof Intermediate+

The organising results are that the jump strictly increases Turing degree — so the ladder genuinely climbs — and that the jump is monotone and order-reflecting: $A \leq_{T} B$ exactly when $A^{'} \leq_{1} B^{'}$ . Together these make $A \mapsto A^{'}$ a well-defined, strictly increasing operator on $D$ whose iteration generates the hierarchy.

Theorem (the jump theorems). For all $A, B \subseteq N$ : (i) $A^{'}$ is $A$ -c.e. and $A <_{T} A^{'}$ ; (ii) $A^{'}$ is $\leq_{m}$ -complete among $A$ -c.e. sets ( $W$ $A$ -c.e. $\Rightarrow$ $W \leq_{m} A^{'}$ ); (iii) $A \leq_{T} B ⟺ A^{'} \leq_{1} B^{'}$ . Consequently $A \equiv_{T} B ⟺ A^{'} \equiv_{1} B^{'}$ , and the jump induces a strictly increasing, monotone operator on $D$ .

Proof. (i) $A^{'}$ is $A$ -c.e. as the domain of $e \mapsto Φ_{e}^{A} (e)$ , an $A$ -partial-computable function, so $A^{'} \leq_{T} A$ fails to reverse: certainly $A \leq_{T} A^{'}$ since $A$ is decided by an $A$ -oracle directly, and below we show strictness. Relativise the halting argument of 42.04.02: if $A^{'} \leq_{T} A$ then $χ_{A^{'}} = Φ_{i}^{A}$ for some $i$ , so the $A$ -partial function $g (e) ≃ Φ_{e}^{A} (e) + 1$ if $χ_{A^{'}} (e) = 1$ and $g (e) ≃ 0$ otherwise is $A$ -computable and total, hence $g = Φ_{e_{0}}^{A}$ for some $e_{0}$ . If $e_{0} \in A^{'}$ then $Φ_{e_{0}}^{A} (e_{0}) ↓$ and $g (e_{0}) = Φ_{e_{0}}^{A} (e_{0}) + 1 = g (e_{0}) + 1$ , impossible; if $e_{0} \in / A^{'}$ then $Φ_{e_{0}}^{A} (e_{0}) ↑$ yet $g (e_{0}) = 0$ is defined, contradicting $g = Φ_{e_{0}}^{A}$ . So $A^{'} \neq \leq_{T} A$ , giving $A <_{T} A^{'}$ .

(ii) Let $W = dom (Φ_{a}^{A})$ be $A$ -c.e. By the relativised s-m-n theorem there is a total computable $f$ with $Φ_{f (x)}^{A} (y) ≃ Φ_{a}^{A} (x)$ for all $y$ (ignore $y$ , run $Φ_{a}^{A}$ on $x$ ). Then $Φ_{f (x)}^{A} (f (x)) ↓ ⟺ Φ_{a}^{A} (x) ↓ ⟺ x \in W$ , so $x \in W ⟺ f (x) \in A^{'}$ , i.e. $W \leq_{m} A^{'}$ .

(iii) ( $\Rightarrow$ ) Suppose $A \leq_{T} B$ , so $A = Φ_{j}^{B}$ in the sense $χ_{A} = Φ_{j}^{B}$ . Any $A$ -oracle computation can be simulated by a $B$ -oracle computation replacing each query " $n \in A$ ?" by the subcomputation $Φ_{j}^{B} (n)$ ; this gives a computable $h$ with $Φ_{h (e)}^{B} ≃ Φ_{e}^{A}$ for all $e$ , and $h$ can be taken injective by padding. Then $e \in A^{'} ⟺ Φ_{e}^{A} (e) ↓ ⟺ Φ_{h (e)}^{B} (h (e)) ↓ ⟺ h (e) \in B^{'}$ , so $A^{'} \leq_{1} B^{'}$ . ( $\Leftarrow$ ) Suppose $A^{'} \leq_{1} B^{'}$ . Since $A \leq_{T} A^{'}$ (indeed $A \leq_{m} A^{'}$ relativised: $A$ is $A$ -c.e., so $A \leq_{m} A^{'}$ by (ii)) and $A^{'} \leq_{1} B^{'}$ gives $A^{'} \leq_{T} B^{'}$ , we get $A \leq_{T} B^{'}$ ; the sharper claim $A \leq_{T} B$ follows because $A \leq_{m} A^{'} \leq_{1} B^{'}$ and $B^{'}$ is $B$ -c.e. with $A$ computed from $B$ by the use-bounded simulation — concretely $χ_{A} (n)$ is read off whether the canonical index for " $n \in A$ " lands in $A^{'}$ , transported into $B^{'}$ and decided $B$ -computably below its use. Hence $A \leq_{T} B$ . $□$

Bridge. The jump theorems are the foundational reason the degrees carry an internal dynamic rather than sitting as an inert ordering: the jump is exactly the relativised halting problem, so Turing's diagonal of 42.04.02 reappears at every oracle and certifies $A <_{T} A^{'}$ uniformly. This is exactly the construction the arithmetical hierarchy 42.04.05 runs level by level — Post's theorem that the $Σ_{n + 1}^{0}$ sets are precisely the $0^{(n)}$ -c.e. ones is the jump theorem (ii) read along the iterated jumps, so the hierarchy is the jump ladder in logical clothing. The equivalence $A \leq_{T} B ⟺ A^{'} \leq_{1} B^{'}$ generalises the way $\leq_{m}$ -completeness pinned $K$ in 42.04.03: the jump is order-reflecting, so it embeds the degree ordering into itself one rung up, which is the central insight behind jump inversion and the high/low hierarchy. This builds toward the priority method 42.04.06, where incomparable c.e. degrees below $0^{'}$ are built by finite injury, and it appears again in every relativised theorem of the subject — putting these together, the jump is the single operator from which the entire vertical structure of $D$ is generated.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the use lemma: if $Φ_{e}^{A} (x) ↓$ with use $u = φ_{e}^{A} (x)$ , then for every $B$ with $B ↾ u = A ↾ u$ we have $Φ_{e}^{B} (x) ↓$ with the same value and use.

Hint

The halting computation is a finite sequence of configurations; trace where the oracle is consulted.

Answer

A halting oracle computation $Φ_{e}^{A} (x)$ is a finite sequence of configurations $C_{0}, C_{1}, \dots, C_{t}$ ending in a halt. Each step is determined by the machine's transition function and, when in the query state with $n$ on the query tape, by the bit $χ_{A} (n)$ . Let $u$ be one more than the largest $n$ so queried (the use); every query in the run asks about some $n < u$ . Now run $Φ_{e}^{B} (x)$ with $B ↾ u = A ↾ u$ . By induction on the step index $i \leq t$ : the non-query steps are identical (they do not consult the oracle), and at each query step the queried $n$ satisfies $n < u$ , so $χ_{B} (n) = χ_{A} (n)$ and the branch taken is the same. Hence the $B$ -run reproduces $C_{0}, \dots, C_{t}$ verbatim, halting with the same value and querying the same numbers, so the use is again $u$ . Rubric: full credit for the finite-run trace, the induction matching configurations step by step, and the observation that all queries are below $u$ .

Exercise 4 (medium, symbolic).

Show that $A \leq_{T} B ⟺ A$ is $Δ$ over $B$ in the sense that both $A$ and $\overline{A}$ are $B$ -c.e. (Post's relativised criterion). Deduce $\overline{K} \leq_{T} K$ .

Hint

Relativise Post's complementation theorem: dovetail the two $B$ -c.e. enumerations.

Answer

( $\Rightarrow$ ) If $A \leq_{T} B$ then $χ_{A} = Φ_{e}^{B}$ is total $B$ -computable, so $A = dom (Φ_{i}^{B})$ where $Φ_{i}^{B} (x) ↓ ⟺ χ_{A} (x) = 1$ and $\overline{A} = dom (Φ_{j}^{B})$ similarly; both are $B$ -c.e. ( $\Leftarrow$ ) If $A = dom (Φ_{a}^{B})$ and $\overline{A} = dom (Φ_{b}^{B})$ , decide $x \in A$ by dovetailing the two $B$ -oracle computations $Φ_{a}^{B} (x)$ and $Φ_{b}^{B} (x)$ until one halts; since $A \cup \overline{A} = N$ exactly one does, at a finite stage, and the answer is "yes" iff $Φ_{a}^{B} (x)$ halted. This is a total $B$ -computable procedure, so $A \leq_{T} B$ . For $\overline{K} \leq_{T} K$ : $K$ is $K$ -c.e. directly (it is computable from the oracle $K$ ), and $\overline{K}$ is $K$ -c.e. since $χ_{K} = Φ_{e}^{K}$ is total $K$ -computable, making $\overline{K} = dom$ of a $K$ -computable partial function; both $K$ and $\overline{K}$ are $K$ -c.e., so $\overline{K} \leq_{T} K$ — more directly, query $K$ at $x$ and flip. Rubric: full credit for the relativised dovetailing both directions and the one-query-flip for $\overline{K} \leq_{T} K$ .

Exercise 6 (hard, symbolic).

Prove there exist Turing-incomparable sets $A, B$ (so $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ ) by a finite-extension (Kleene-Post) construction. You may build $A, B \leq_{T} \emptyset^{'}$ .

Hint

Build $A, B$ as unions of finite binary strings $α_{s} ≺ α_{s + 1}$ , $β_{s} ≺ β_{s + 1}$ , meeting in stages the requirements $R_{2 e} : Φ_{e}^{B} \neq = χ_{A}$ and $R_{2 e + 1} : Φ_{e}^{A} \neq = χ_{B}$ by diagonalising at one fresh point.

Answer

Construct $A = ⋃_{s} α_{s}$ , $B = ⋃_{s} β_{s}$ as increasing unions of finite partial characteristic functions, $α_{0} = β_{0} = \emptyset$ . Requirements: $R_{2 e} : Φ_{e}^{B} \neq = χ_{A}$ and $R_{2 e + 1} : Φ_{e}^{A} \neq = χ_{B}$ ; meeting all $R_{n}$ gives $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ . Stage $s + 1$ , handling $R_{2 e}$ (odd index symmetric): let $x$ be the least number not yet in $dom (α_{s})$ . Ask whether there is a finite extension $β ⪰ β_{s}$ with $Φ_{e}^{β} (x) ↓$ — an $\exists$ -question about convergence, answerable by the oracle $\emptyset^{'}$ . If such $β$ exists, set $β_{s + 1} = β$ and define $α_{s + 1} (x) = 1 - Φ_{e}^{β} (x)$ (extending by $0$ elsewhere), so $Φ_{e}^{B} (x) = Φ_{e}^{β} (x) \neq = α_{s + 1} (x) = χ_{A} (x)$ by the use lemma (no later extension below the use changes the value). If no such $β$ exists, then $Φ_{e}^{B} (x) ↑$ for the eventual $B ⪰ β_{s}$ , so $Φ_{e}^{B} \neq = χ_{A}$ vacuously (it is not total); set $α_{s + 1} (x) = 0$ . Either way $R_{2 e}$ is met permanently. All requirements are satisfied, and the search for $β$ being an $\emptyset^{'}$ -question gives $A, B \leq_{T} \emptyset^{'}$ . Rubric: full credit for the staged finite extensions, the diagonalisation at a fresh $x$ using the use lemma, the convergence-search delegated to $\emptyset^{'}$ , and the vacuous case when no convergent extension exists.

Exercise 7 (hard, symbolic).

Prove the jump is monotone but not injective on degrees-below-its-source: show $A \leq_{T} B \Rightarrow A^{'} \leq_{T} B^{'}$ , and exhibit (citing the relevant theorem) why $A <_{T} B$ need not give $A^{'} <_{T} B^{'}$ .

Hint

Monotonicity is the easy half of jump theorem (iii). For the failure of strictness, recall that there are sets strictly above $\emptyset$ whose jump is still $\equiv_{T} \emptyset^{'}$ — the low sets.

Answer

Monotonicity: if $A \leq_{T} B$ then by jump theorem (iii) $A^{'} \leq_{1} B^{'}$ , hence $A^{'} \leq_{T} B^{'}$ . (Directly: simulate each $A$ -query in an $A$ -oracle computation by a $B$ -subcomputation, giving a computable $h$ with $Φ_{h (e)}^{B} ≃ Φ_{e}^{A}$ , so $e \in A^{'} ⟺ h (e) \in B^{'}$ .) Non-strictness: a set $A$ is low if $A^{'} \equiv_{T} \emptyset^{'}$ . The Friedberg-Muchnik / Sacks constructions (42.04.06) produce a c.e. set $A$ with $\emptyset <_{T} A <_{T} \emptyset^{'}$ that is low, i.e. $A^{'} \equiv_{T} \emptyset^{'}$ . Taking $B = \emptyset^{'}$ (whose jump is $\emptyset^{''}$ ) we have $A <_{T} B$ , yet for two low sets $A_{0} <_{T} A_{1}$ both below $\emptyset^{'}$ one gets $A_{0}^{'} \equiv_{T} \emptyset^{'} \equiv_{T} A_{1}^{'}$ , so $A_{0}^{'} \neq <_{T} A_{1}^{'}$ : the jump collapses the strict order. Thus the jump is monotone ( $\leq_{T}$ preserved) but not order-reflecting downward in the strict sense — strictness below the jump can be erased, which is exactly the phenomenon the low/high hierarchy measures. Rubric: full credit for the monotonicity proof via (iii) or direct simulation, the definition of low, and a correct citation that low c.e. sets strictly between $0$ and $0^{'}$ exist so the jump is non-strict on them.

Advanced results Master

The jump turns the degrees from a bare ordering into a structure with vertical dynamics, and relativisation propagates every basic theorem to every oracle. The results below fix the jump as a strictly increasing, surjective-onto-its-cone operator, establish the relativisation principle, and chart the global structure of $D$ — its size, its embeddings, and the existence of incomparable and minimal degrees.

Theorem 1 (the jump as a degree operator; relativised completeness). The jump $a \mapsto a^{'}$ is well-defined on $D$ , strictly increasing ( $a < a^{'}$ ), and monotone ( $a \leq b \Rightarrow a^{'} \leq b^{'}$ ), with $A^{'}$ the $\leq_{m}$ -complete $A$ -c.e. set ^{[Soare Ch. 3]}. Hence $A^{'}$ plays, relative to $A$ , exactly the role $K$ plays relative to $\emptyset$ : it is the canonical $A$ -c.e. complete set, and every $A$ -c.e. set many-one reduces to it. The equivalence $A \leq_{T} B ⟺ A^{'} \leq_{1} B^{'}$ makes the jump order-reflecting on degrees, so it is an order-embedding of $D$ into the cone above $0^{'}$ .

Theorem 2 (the relativisation principle). Every theorem provable from the basic axioms of computability — closure of the partial computable functions under composition, primitive recursion, and minimisation; the enumeration, s-m-n, and recursion theorems; the undecidability and structure results of 42.04.02, 42.04.03 — holds verbatim with any oracle $A$ adjoined, replacing "computable" by " $A$ -computable" and "c.e." by " $A$ -c.e." ^{[Rogers Ch. 9]}. Relativisation is not a meta-theorem proved once and for all inside the object theory but a uniform observation that the proofs use only the relativisable closure properties; it is the reason the jump theorems are themselves relativised halting theorems, and the reason the arithmetical hierarchy 42.04.05 can be built by iterating a single construction. Its limits are the boundary of the subject: results sensitive to the specific structure of $\emptyset$ (and "non-relativising" priority arguments) mark where relativisation genuinely fails, the technical heart of the $P$ -versus- $NP$ relativisation barrier in complexity.

Theorem 3 (Post's theorem; the hierarchy from the jump). A set $X$ is $Σ_{n + 1}^{0}$ iff $X$ is $0^{(n)}$ -c.e., and $X$ is $Δ_{n + 1}^{0}$ iff $X \leq_{T} 0^{(n)}$ ^{[Soare Ch. 4]}. Thus $0^{(n)}$ is $Σ_{n}^{0}$ -complete, the iterated jumps $0, 0^{'}, 0^{''}, \dots$ are exactly the complete sets at each level of the arithmetical hierarchy 42.04.05, and quantifier complexity in arithmetic is precisely depth on the jump ladder. This is the bridge by which the degree-theoretic jump becomes the syntactic hierarchy: each added unbounded quantifier corresponds to one application of the jump, and Post's theorem is jump theorem (ii) read inductively along $0^{(n)}$ .

Theorem 4 (the global structure of $D$ ). The Turing degrees form an upper semilattice of cardinality $2^{ℵ_{0}}$ with least element $0$ and no greatest element ^{[Lerman Ch. I-III]}. Every countable partial order embeds into $D$ (indeed into the interval $[0, 0^{'}]$ , by the Kleene-Post finite-extension method generalised), so $D$ has incomparable degrees, antichains of every countable size, and no first-order definable least nonzero degree. There are exactly $2^{ℵ_{0}}$ degrees above any fixed degree (its cone), and the exact-pair theorem shows $D$ is not a lattice: there are pairs $a, b$ with no greatest lower bound, witnessed by an exact pair bounding a given countable ideal. The join makes every finite set of degrees have a least upper bound, but suprema of infinite sets and infima of pairs may not exist.

Theorem 5 (minimal degrees and the fine structure). There is a minimal degree: a degree $m > 0$ with nothing strictly between $0$ and $m$ , constructed by Spector's forcing with perfect (computable) binary trees, where each requirement narrows the tree to force either $Φ_{e}^{G}$ partial, or computable, or computing $G$ back ^{[Lerman Ch. V-VI]}. Minimal degrees show the ordering is far from dense at the bottom in some directions while the Sacks density theorem makes the c.e. degrees dense — two facts that coexist because minimal degrees are not c.e. Jump inversion (Friedberg) completes the vertical picture: every degree $\geq 0^{'}$ is a jump, $c \geq 0^{'} \Rightarrow \exists a (a^{'} = c)$ , so the jump is onto the cone above $0^{'}$ . The high/low hierarchy then classifies degrees below $0^{'}$ by how close $a^{'}$ is to $0^{'}$ (low) or to $0^{''}$ (high), measuring how much information the jump extracts.

Synthesis. Relative computation is the foundational reason non-computability has structure rather than being a single cliff: the oracle makes "computable given $A$ " precise, Turing reducibility orders problems by the helper they need, and the degrees are the resulting landscape. The jump is the engine of that landscape, and this is exactly the relativised halting diagonal of 42.04.02 — Turing's argument run at every oracle — so $A <_{T} A^{'}$ at each rung and the iterated jumps build the ladder $0, 0^{'}, 0^{''}, \dots$ whose Post-theorem reading is the arithmetical hierarchy 42.04.05: each unbounded quantifier is one jump, and $0^{(n)}$ is the $Σ_{n}^{0}$ -complete set. Putting these together, the equivalence $A \leq_{T} B ⟺ A^{'} \leq_{1} B^{'}$ embeds $D$ into its own cone above $0^{'}$ , which generalises the $\leq_{m}$ -completeness of $K$ in 42.04.03 to every oracle and is dual to jump inversion's surjection onto that cone. The central insight is that one operator — the jump — generates the vertical structure, while horizontal structure (incomparable degrees, the embedding of every countable poset, minimal degrees) comes from forcing-style constructions that the priority method 42.04.06 refines into the finite-injury arguments solving Post's problem; the bridge is relativisation, the uniform fact that every basic theorem holds over every oracle, which is why the whole picture iterates and why its failures mark the genuine boundaries of the theory.

Full proof set Master

Proposition 1 (the use lemma). If $Φ_{e}^{A} (x) ↓$ with use $u = φ_{e}^{A} (x)$ , then $Φ_{e}^{B} (x) ↓$ with the same value whenever $B ↾ u = A ↾ u$ .

Proof. The halting run is a finite configuration sequence $C_{0}, \dots, C_{t}$ . Non-query steps ignore the oracle; each query step asks about some $n < u$ by the definition of the use. If $B ↾ u = A ↾ u$ then $χ_{B} (n) = χ_{A} (n)$ for all $n < u$ , so by induction on $i \leq t$ the $B$ -run reproduces each $C_{i}$ , halting with the same value and use. $□$

Proposition 2 ( $A <_{T} A^{'}$ ). $A^{'}$ is $A$ -c.e. and $A <_{T} A^{'}$ .

Proof. $A^{'} = dom (e \mapsto Φ_{e}^{A} (e))$ is $A$ -c.e., and $A \leq_{T} A^{'}$ since the index for "decide $n \in A$ in one oracle query, then halt iff yes" places $n \in A ⟺ (that index) \in A^{'}$ , an $\leq_{m}$ hence $\leq_{T}$ reduction. Strictness: if $A^{'} \leq_{T} A$ then $χ_{A^{'}} = Φ_{i}^{A}$ and the $A$ -computable total $g (e) = Φ_{e}^{A} (e) + 1$ on $A^{'}$ , $g (e) = 0$ off $A^{'}$ , equals some $Φ_{e_{0}}^{A}$ . At $e_{0}$ : if $e_{0} \in A^{'}$ , $g (e_{0}) = Φ_{e_{0}}^{A} (e_{0}) + 1 = g (e_{0}) + 1$ , absurd; if $e_{0} \in / A^{'}$ , $Φ_{e_{0}}^{A} (e_{0}) ↑$ while $g (e_{0}) = 0$ defined, contradicting $g = Φ_{e_{0}}^{A}$ . So $A^{'} \neq \leq_{T} A$ . $□$

Proposition 3 ( $A^{'}$ is $\leq_{m}$ -complete among $A$ -c.e. sets). If $W$ is $A$ -c.e. then $W \leq_{m} A^{'}$ .

Proof. Let $W = dom (Φ_{a}^{A})$ . By relativised s-m-n there is total computable $f$ with $Φ_{f (x)}^{A} (y) ≃ Φ_{a}^{A} (x)$ for all $y$ . Then $f (x) \in A^{'} ⟺ Φ_{f (x)}^{A} (f (x)) ↓ ⟺ Φ_{a}^{A} (x) ↓ ⟺ x \in W$ , so $W \leq_{m} A^{'}$ . In particular $A \leq_{m} A^{'}$ (take $W = A$ ), so $A \leq_{1} A^{'}$ after padding $f$ to be injective. $□$

Proposition 4 (jump monotonicity and order-reflection). $A \leq_{T} B ⟺ A^{'} \leq_{1} B^{'}$ .

Proof. ( $\Rightarrow$ ) From $A \leq_{T} B$ , every $A$ -oracle computation is simulated $B$ -computably by replacing each query " $n \in A$ ?" with the subcomputation deciding it from $B$ ; this yields a computable injective $h$ with $Φ_{h (e)}^{B} ≃ Φ_{e}^{A}$ for all $e$ . Then $e \in A^{'} ⟺ Φ_{e}^{A} (e) ↓ ⟺ Φ_{h (e)}^{B} (h (e)) ↓ ⟺ h (e) \in B^{'}$ , so $A^{'} \leq_{1} B^{'}$ . ( $\Leftarrow$ ) By Proposition 3, $A \leq_{1} A^{'}$ ; composing with $A^{'} \leq_{1} B^{'}$ gives $A \leq_{1} B^{'}$ , so $A \leq_{T} B^{'}$ . To sharpen to $A \leq_{T} B$ : membership $n \in A$ is equivalent (via the canonical $A$ -index for the one-query test) to $g (n) \in A^{'}$ for a computable $g$ , and $A^{'} \leq_{1} B^{'}$ transports this to $h (g (n)) \in B^{'}$ ; the value $χ_{B^{'}} (h (g (n)))$ is computed from $B$ by running the relevant $B$ -computation, whose use is bounded, so $χ_{A}$ is $B$ -computable, i.e. $A \leq_{T} B$ . $□$

Proposition 5 ( $\emptyset^{'} \equiv_{T} K$ and the bottom rung). $\emptyset^{'} = K$ , so $0^{'} = de g (K)$ .

Proof. An $\emptyset$ -oracle answers every query negatively, so it conveys no information and $Φ_{e}^{\emptyset} ≃ φ_{e}$ for all $e$ . Hence $\emptyset^{'} = {e : Φ_{e}^{\emptyset} (e) ↓} = {e : φ_{e} (e) ↓} = K$ . Therefore $0^{'} = de g (\emptyset^{'}) = de g (K)$ , the degree of the halting problem, and Proposition 2 specialises to the unrelativised $K \neq \leq_{T} \emptyset$ of 42.04.02. $□$

Proposition 6 (existence of incomparable degrees). There exist $A, B$ with $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ .

Proof. Build $A = ⋃_{s} α_{s}$ , $B = ⋃_{s} β_{s}$ by finite extensions, $α_{0} = β_{0} = \emptyset$ , meeting $R_{2 e} : Φ_{e}^{B} \neq = χ_{A}$ and $R_{2 e + 1} : Φ_{e}^{A} \neq = χ_{B}$ . At stage $s + 1$ for $R_{2 e}$ : let $x \in / dom (α_{s})$ be least. If some finite $β ⪰ β_{s}$ has $Φ_{e}^{β} (x) ↓$ , set $β_{s + 1} = β$ and $α_{s + 1} (x) = 1 - Φ_{e}^{β} (x)$ ; by the use lemma the eventual $B$ preserves $Φ_{e}^{B} (x) = Φ_{e}^{β} (x) \neq = χ_{A} (x)$ . Otherwise $Φ_{e}^{B} (x) ↑$ for every extension, so $Φ_{e}^{B}$ is not total and $\neq = χ_{A}$ ; set $α_{s + 1} (x) = 0$ . Odd requirements are symmetric. Every $R_{n}$ is met, so neither set is Turing-computable from the other. $□$

Proposition 7 (jump inversion, statement and the easy bound). Every degree $c \geq 0^{'}$ is a jump: there is $a$ with $a^{'} = c$ ; moreover any jump $a^{'}$ satisfies $a^{'} \geq 0^{'}$ .

Proof. The lower bound is immediate: $\emptyset \leq_{T} A$ for every $A$ , so by Proposition 4 $\emptyset^{'} \leq_{1} A^{'}$ , giving $0^{'} \leq a^{'}$ for every $a$ . Thus the range of the jump lies in the cone above $0^{'}$ . The surjection onto that cone is Friedberg's theorem ^{[Rogers Ch. 13]}: given $C \geq_{T} \emptyset^{'}$ , a forcing/finite-extension construction builds $A$ with $A^{'} \equiv_{T} A \oplus \emptyset^{'} \equiv_{T} C$ , by coding $C$ into $A$ slowly enough that the jump $A^{'}$ recovers exactly $C$ and no more. Hence the jump maps $D$ onto ${c : c \geq 0^{'}}$ , and combined with strict monotonicity (Proposition 2) the jump is a strictly increasing surjection onto its cone. $□$

Connections Master

Computably enumerable sets and reducibilities 42.04.03, the prerequisite, supplies the $\leq_{m}$ theory this unit coarsens to $\leq_{T}$ : the reducibility chain $\leq_{1} \Rightarrow \leq_{m} \Rightarrow \leq_{T}$ stated there is completed here with the strict separation $\overline{K} \leq_{T} K$ , $\overline{K} \neq \leq_{m} K$ , and Dekker's observation there — that simplicity bounds $\leq_{m}$ but not $\leq_{T}$ — is exactly the gap the Turing degrees of this unit measure. That unit owns the creative/simple dichotomy in the many-one world; this unit owns the oracle, the jump, and the degree structure built on top of it.
The arithmetical hierarchy 42.04.05, co-produced, is the jump ladder of this unit in logical clothing: Post's theorem identifies the $Σ_{n + 1}^{0}$ sets with the $0^{(n)}$ -c.e. sets and the iterated jumps $0^{(n)}$ with the level-complete sets, so each unbounded quantifier is one application of the jump. This unit owns the jump operator and relativisation; that unit owns the syntactic classification by quantifier complexity and the completeness of $0^{(n)}$ at each level.
The priority method and Post's problem 42.04.06, co-produced, builds the horizontal structure this unit's global theorems describe: the Kleene-Post finite-extension argument (Proposition 6) for incomparable degrees below $0^{'}$ is the non-effective ancestor of the Friedberg-Muchnik finite-injury construction of incomparable c.e. degrees strictly between $0$ and $0^{'}$ , and the low sets of Exercise 7 — strictly between $0$ and $0^{'}$ yet with jump $\equiv_{T} 0^{'}$ — are produced there. This unit owns the jump and the degree order; that unit owns the priority constructions that populate the interval $[0, 0^{'}]$ .
The halting problem and recursion theorem 42.04.02 is the unrelativised base case the jump generalises: $\emptyset^{'} = K$ (Proposition 5), the diagonal that gives $K \neq \leq_{T} \emptyset$ is the $A = \emptyset$ instance of $A <_{T} A^{'}$ , and the relativised s-m-n and recursion theorems used throughout are that unit's results read over an oracle. That unit owns the diagonal and the many-one completeness of $K$ ; this unit relativises both to every oracle and iterates the jump into a hierarchy.

Historical & philosophical context Master

Relative computability is Turing's own idea, introduced in his 1939 Princeton thesis "Systems of logic based on ordinals" under the name oracle machine: a Turing machine permitted to consult an external oracle for the values of some otherwise-uncomputable function, used there to study iterated consistency extensions of arithmetic ^{[Soare Ch. 3]}. Turing left the notion of relative computation undeveloped; it was Emil Post who, in his 1944 paper and especially in his 1948 abstract "Degrees of recursive unsolvability," made reducibility and the resulting degrees of unsolvability the central object, defining $\leq_{T}$ , the join, and posing the structural questions — does an intermediate c.e. degree exist? — that organised the next two decades. Post and Kleene's joint 1954 paper "The upper semi-lattice of degrees of recursive unsolvability" introduced the finite-extension method, proving the existence of incomparable degrees and establishing $D$ as an upper semilattice of the cardinality of the continuum.

Kleene had already isolated the jump and the relativised arithmetical hierarchy in the early 1940s, and Post's theorem tying the jump hierarchy to quantifier complexity made the connection between degree theory and definability precise ^{[Rogers Ch. 13]}. The structural study deepened with Clifford Spector's 1956 construction of a minimal degree by forcing with perfect trees, Richard Friedberg's 1957 jump-inversion theorem, and the Friedberg-Muchnik solution to Post's problem by the priority method the same year. Gerald Sacks's 1960s work — the density theorem, the splitting theorem, jump theorems for c.e. degrees — and Manuel Lerman's systematic Degrees of Unsolvability (1983) established $D$ as a rich algebraic and definability-theoretic object. Philosophically, the degrees realise a precise hierarchy of non-computability: the Church-Turing thesis fixes the bottom rung as absolute, and the jump shows that above it lies an unbounded, intricately structured ladder of relative unsolvability, with relativisation as the principle that the same logic governs every rung.

Bibliography Master

@phdthesis{turing1939ordinals,
  author  = {Turing, Alan M.},
  title   = {Systems of Logic Based on Ordinals},
  school  = {Princeton University},
  year    = {1939},
  note    = {Published in Proc. London Math. Soc. s2-45 (1939), 161--228}
}

@article{post1944recursively,
  author  = {Post, Emil L.},
  title   = {Recursively enumerable sets of positive integers and their decision problems},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {50},
  number  = {5},
  year    = {1944},
  pages   = {284--316}
}

@article{post1948degrees,
  author  = {Post, Emil L.},
  title   = {Degrees of recursive unsolvability: preliminary report},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {54},
  year    = {1948},
  pages   = {641--642}
}

@article{kleenepost1954upper,
  author  = {Kleene, Stephen C. and Post, Emil L.},
  title   = {The upper semi-lattice of degrees of recursive unsolvability},
  journal = {Annals of Mathematics},
  volume  = {59},
  number  = {3},
  year    = {1954},
  pages   = {379--407}
}

@article{spector1956minimal,
  author  = {Spector, Clifford},
  title   = {On degrees of recursive unsolvability},
  journal = {Annals of Mathematics},
  volume  = {64},
  number  = {3},
  year    = {1956},
  pages   = {581--592}
}

@article{friedberg1957solution,
  author  = {Friedberg, Richard M.},
  title   = {Two recursively enumerable sets of incomparable degrees of unsolvability (solution of {Post's} problem, 1944)},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {43},
  number  = {2},
  year    = {1957},
  pages   = {236--238}
}

@article{muchnik1956unsolvability,
  author  = {Muchnik, Albert A.},
  title   = {On the unsolvability of the problem of reducibility in the theory of algorithms},
  journal = {Doklady Akademii Nauk SSSR},
  volume  = {108},
  year    = {1956},
  pages   = {194--197}
}

@article{sacks1964degrees,
  author  = {Sacks, Gerald E.},
  title   = {The recursively enumerable degrees are dense},
  journal = {Annals of Mathematics},
  volume  = {80},
  number  = {2},
  year    = {1964},
  pages   = {300--312}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

@book{rogers1967theory,
  author    = {Rogers, Hartley},
  title     = {Theory of Recursive Functions and Effective Computability},
  publisher = {McGraw-Hill},
  year      = {1967}
}

@book{lerman1983degrees,
  author    = {Lerman, Manuel},
  title     = {Degrees of Unsolvability: Local and Global Theory},
  series    = {Perspectives in Mathematical Logic},
  publisher = {Springer},
  year      = {1983}
}

@book{odifreddi1989classical,
  author    = {Odifreddi, Piergiorgio},
  title     = {Classical Recursion Theory, Volume I},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {125},
  publisher = {North-Holland},
  year      = {1989}
}

Prerequisites

42.04.03

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 3 (read the informal account of a machine equipped with a subscription to a set $A$ it may query for free — relative computation — and of the idea that one problem can be 'no harder than' another once you are allowed to consult it); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §6.3 for oracle Turing machines and Turing reducibility stated plainly before any degree theory
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 3 (oracle Turing machines $\Phi_e^A$, the use principle and use function, Turing reducibility $A \le_T B$ and equivalence $\equiv_T$, the comparison $\le_m \Rightarrow \le_T$ with the converse failing, the Turing degrees as equivalence classes, the join $A \oplus B$ and the upper semilattice $\mathcal D$ with least element $\mathbf 0$, the Turing jump $A' = \{e : \Phi_e^A(e)\!\downarrow\}$ and the jump theorems $A <_T A'$, $A \le_T B \iff A' \le_1 B'$); Cutland 1980 *Computability: An Introduction to Recursive Function Theory* (Cambridge) Ch. 9-10 (relative computability, reducibilities, the jump operator)
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 3-4 and the historical notes (oracle computation and relativisation, the use principle, the structure of the degrees $\mathcal D$ as an upper semilattice, the jump as a strictly increasing monotone operator, $A'$ as the $\le_m$-complete $A$-c.e. set, the iterated jumps $A^{(n)}$ and the hierarchy $\mathbf 0, \mathbf 0', \mathbf 0'', \dots$, the relativisation principle, the uncountability of $\mathcal D$, the embedding of every countable partial order, incomparable and minimal degrees by counting/forcing); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 9-13 (relative recursiveness, the jump hierarchy, the degrees of unsolvability); Lerman 1983 *Degrees of Unsolvability* (Springer) Ch. I-VI (the algebraic structure of $\mathcal D$, embeddings, minimal degrees, the jump)

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 3 develops relative computation: an oracle Turing machine has a distinguished query tape and an oracle state; running with oracle set $A$ it may ask 'is $n \in A$?' and branch on the answer in one step, defining the partial function $\Phi_e^A$ and the $A$-c.e. and $A$-computable sets. The USE PRINCIPLE: if $\Phi_e^A(x)\!\downarrow$ then it does so with a finite use $u = \varphi_e^A(x)$, querying only $A \restriction u$, so the computation is preserved under any oracle agreeing with $A$ below $u$ (the use lemma and the permanence/monotonicity of converging computations). TURING REDUCIBILITY $A \le_T B$ means $\chi_A = \Phi_e^B$ for some $e$; $\equiv_T$ is mutual reducibility; the implications $\le_1 \Rightarrow \le_m \Rightarrow \le_T$ with $\le_m$ strictly stronger (e.g. $\overline K \le_T K$ but $\overline K \not\le_m K$). The TURING DEGREES $\mathcal D = \mathcal P(\omega)/\equiv_T$ form a partial order with least element $\mathbf 0$ (the computable degree); the JOIN $A \oplus B = \{2n : n \in A\} \cup \{2n+1 : n \in B\}$ realises the least upper bound, making $\mathcal D$ an upper semilattice, not a lattice. The TURING JUMP $A' = \{e : \Phi_e^A(e)\!\downarrow\} = K^A$ is the halting problem relativised to $A$; the JUMP THEOREMS: $A'$ is $A$-c.e., $A <_T A'$ (Turing's relativised diagonal), $A \le_T B \iff A' \le_1 B'$ (so the jump is monotone and degree-invariant), $A'$ is $\le_m$-complete among $A$-c.e. sets, and $B$ is $A$-c.e. and $A \le_T B$ does not force $A' \le_T B$. The ITERATED JUMPS $A^{(0)} = A$, $A^{(n+1)} = (A^{(n)})'$ give $\mathbf 0^{(n)}$, the backbone of the arithmetical hierarchy (a set is $\Sigma_{n+1}^0$ iff it is $\mathbf 0^{(n)}$-c.e., Post's theorem). RELATIVISATION: every theorem proved from the basic computability axioms holds with any oracle $A$ adjoined. The structure of $\mathcal D$: $2^{\aleph_0}$ many degrees, every countable partial order embeds, incomparable degrees exist (Kleene-Post finite-extension/forcing), minimal degrees exist (Spector).
Rogers, H. — Theory of Recursive Functions and Effective Computability · McGraw-Hill (1967). Ch. 9: relative recursiveness via oracle machines, relative c.e. sets, the enumeration and s-m-n theorems relativised, the use of the oracle and the finite-use property; Ch. 10-11: reducibilities $\le_1, \le_m, \le_{tt}, \le_T$ and their strict ordering, the degrees of unsolvability as $\equiv_T$-classes, the join operation and the upper-semilattice structure of $\mathcal D$ with least element $\mathbf 0$; Ch. 13: the jump operator $A \mapsto A'$, the relativised halting problem, the theorems $A <_T A'$ and $A \le_T B \iff A' \le_1 B'$, the jump hierarchy $\mathbf 0', \mathbf 0'', \dots$, the Kleene-Post construction of incomparable degrees below $\mathbf 0'$ by finite extensions, and Friedberg's jump-inversion theorem that every degree $\ge \mathbf 0'$ is a jump.
Lerman, M. — Degrees of Unsolvability · Springer, Perspectives in Mathematical Logic (1983). Ch. I-III: the upper semilattice $\mathcal D$ of Turing degrees, the join as least upper bound, the absence of meets in general, the cardinality $2^{\aleph_0}$ and the cone above a degree; embeddings of countable (and certain uncountable) partial orders and lattices into $\mathcal D$ and into the interval below $\mathbf 0'$; Ch. IV-VI: the jump operator as a monotone, strictly increasing, degree-invariant map, the jump-hierarchy structure, Spector's construction of a minimal degree by forcing with perfect trees, the exact-pair theorem, and the interplay of the jump with embeddings (jump inversion, the high/low hierarchy) that gives $\mathcal D$ its fine structure.

Estimated time

beginner: 20m
intermediate: 55m
master: 100m