42.04.06 · mathematical-logic / computability-degrees

The Turing Degrees and the Priority Method

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 6-12 and the historical notes (the finite-injury priority method and the solution to Post's problem; the c.e. degrees $\mathcal R$ as an upper semilattice with $\mathbf 0$ and $\mathbf 0'$ — the Sacks density and splitting theorems, minimal pairs, the failure of distributivity, the embedding of every finite lattice; infinite-injury and the $\mathbf 0'''$-priority / tree method, the Sacks jump theorem; the global structure $\mathcal D$ — Spector minimal degrees by forcing with perfect trees, the Posner-Robinson join theorem, automorphism and definability questions; the decidability of the $\Sigma_2$ theory of $\mathcal R$ and the undecidability of richer fragments); Soare 1987 *Recursively Enumerable Sets and Degrees* (Springer) Ch. VII-XII (the priority method systematised, finite and infinite injury, the lattice $\mathcal R$); Lerman 1983 *Degrees of Unsolvability* (Springer) Ch. VII-IX (minimal degrees, the global theory of $\mathcal D$)

Intuition Beginner

The previous unit built a ladder of difficulty and showed there are problems strictly above the everyday computable ones and strictly below the halting problem could exist by abstract counting. But Post asked a sharper question, and it stayed open for twelve years: among the sets a computer can list but not decide, is there one of genuinely middling hardness — harder than anything ordinary computers solve, yet easier than the halting problem? Post tried to find one by making the listable set "thin" in clever ways, but every thinness trick he invented still left the set either easy or as hard as halting. The middle stayed empty by his methods.

The answer turned out to be yes, and the way to get it is a new style of construction. You build your set in stages, adding numbers one at a time, and you keep a numbered to-do list of demands the finished set must satisfy. The demands compete: satisfying a later one can undo what an earlier one set up. So you rank them by priority — lower-numbered demands win. When a high-priority demand needs to act, it acts, even if that spoils a lower-priority demand that had looked settled. The spoiled demand simply starts over.

The reason this does not loop forever is a counting fact. A given demand can only be spoiled by the demands ranked above it, and there are finitely many of those, and each of them acts at most a bounded number of times once its own situation settles. So every demand is spoiled only finitely often, and after its last spoiling it stays satisfied for good. That single observation — finitely many interferences, so eventual peace — is the engine. It is called the priority method, and Post's middle ground is its first triumph.

Visual Beginner

Picture the requirements stacked by priority, highest at the top. Each one watches for its moment, acts, and then guards a stretch of small numbers it needs left untouched. A higher requirement may reach down and disturb that stretch — an injury — and the lower one resets and tries again later.

   priority list (top = most urgent), set A built in stages:

   R0 :  acts at stage 4, guards {0..6}        -> never disturbed, met forever
   R1 :  acts at stage 7, guards {0..9}        -> R0 cannot reach it (higher)
   R2 :  acts at stage 9, guards {0..12}  --.
                                            |  injured at stage 15
   R2 :  RESET, re-picks a fresh witness  <-'  by R1 acting again
   R2 :  acts at stage 22, guards {0..20}      -> now never disturbed, met

   Rule: only HIGHER requirements (smaller index) can injure a lower one.
   Each higher one acts finitely often, so each requirement is injured
   finitely often, then is met permanently.  That is "finite injury."

Now read off why the whole thing terminates into a satisfied state, requirement by requirement.

requirement $R_{n}$	who can injure it	how many injuries	outcome
top, $R_{0}$	nobody above it	$0$	met at its first action
middle, $R_{n}$	the $n$ requirements above	at most finitely many	met after its last injury
any $R_{n}$	only higher priority	always finite	eventually permanently met

Read the table downward: the top requirement is never disturbed; each lower one is disturbed only by the finitely many above it; so every requirement reaches a last injury and then stays met. The set the stages build satisfies the entire list.

Worked example Beginner

We watch a tiny priority construction satisfy two competing demands, to see injury and recovery concretely. We build a set $A$ of numbers in stages. Demand $R_{0}$ (top priority) wants the number $5$ to be in $A$ . Demand $R_{1}$ (lower priority) wants $A$ to avoid the whole block ${4, 5, 6}$ — but $R_{1}$ only cares about a block that does not already contain a number a higher demand has claimed.

Step 1. Stage one, $R_{0}$ acts. It puts $5$ into $A$ and guards it: $5$ must stay in. Now $A = {5}$ .

Step 2. Stage two, $R_{1}$ looks at the block ${4, 5, 6}$ . It sees $5$ is already claimed by the higher demand $R_{0}$ , which it cannot override. So $R_{1}$ is blocked on this block and shifts its attention to a fresh, untouched block, say ${10, 11, 12}$ , which it can keep empty. No conflict remains.

Step 3. Read off the finished set. $R_{0}$ got its way permanently — $5$ is in and guarded. $R_{1}$ got its way too, on a block it was free to control, by stepping aside from the number a higher demand owned. Both demands are satisfied at once, with the higher one winning the contested spot.

What this tells us: the priority rule resolves every clash by letting the more urgent demand keep its claim and making the less urgent one retreat to fresh ground. Because the urgent demands are few and settle early, the retreats stop happening, and the construction lands on a set that meets every demand. Scaling this picture up — with the demands being "do not let program $e$ compute my set from the other set" — is exactly how Post's middle ground gets built.

Check your understanding Beginner

Exercise (easy, multiple-choice).

Why does each requirement end up satisfied permanently in a finite-injury construction?

Because no requirement is ever injured.
Because each requirement is injured only finitely often, so after its last injury it stays met.
Because the set being built is finite.
Because all requirements have equal priority.

Hint

Count how many requirements can disturb a given one, and how often each does so.

Answer

B. Only the finitely many higher-priority requirements can injure a given one, and each does so only finitely often, so the total number of injuries is finite and there is a last one, after which the requirement is met for good. Feedback-correct: "finite injury" names exactly this. Feedback-wrong: requirements are injured (so A is wrong), the set is generally infinite (C), and the priorities are strictly ranked (D).

Formal definition Intermediate+

Work with the oracle machinery, Turing reducibility $\leq_{T}$ , the jump, and the c.e. degree language of 42.04.04, and the c.e. sets $W_{e}$ with stage approximations $W_{e, s}$ of 42.04.03. Post's problem asks whether there is a c.e. set $A$ with $\emptyset <_{T} A <_{T} \emptyset^{'}$ , equivalently a c.e. Turing degree strictly between $0$ and $0^{'}$ . The c.e. degrees $R = {de g (A) : A c.e.}$ form a sub-upper-semilattice of $D$ with least element $0$ and greatest element $0^{'} = de g (K)$ , ordered by $\leq_{T}$ with join induced by $\oplus$ .

A finite-injury priority construction of c.e. sets $A = ⋃_{s} A_{s}$ , $B = ⋃_{s} B_{s}$ (with $A_{0} = B_{0} = \emptyset$ and $A_{s + 1} ∖ A_{s}$ at most a single number, computable in $s$ ) is specified by: a list of requirements ${R_{n}}_{n \in N}$ ranked by priority ( $R_{m}$ higher than $R_{n}$ when $m < n$ ); for each $R_{n}$ a partial-computable strategy reading the current approximations and possibly enumerating a number into $A$ or $B$ ; and a restraint function $r (n, s)$ naming a threshold below which $R_{n}$ asks that the relevant set be frozen at stage $s$ . Requirement $R_{n}$ acts at $s$ when its strategy enumerates a number or raises its restraint. $R_{n}$ is injured at $s$ if a higher-priority requirement $R_{m}$ ( $m < n$ ) enumerates a number $\leq r (n, s)$ into the set $R_{n}$ is restraining, invalidating a computation $R_{n}$ was protecting. The injury set is $I_{n} = {s : R_{n} injured at s}$ .

The Friedberg-Muchnik requirements for incomparability are, for $A \neq = B$ c.e., $$ R_{2e} : \Phi_e^B \ne \chi_A, \qquad R_{2e+1} : \Phi_e^A \ne \chi_B, $$ meeting all of which gives $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ . Each $R_{2 e}$ owns a witness $x = x (2 e)$ (a fresh number reserved for $A$ ): if at some stage $Φ_{e, s}^{B_{s}} (x) ↓= 0$ , the strategy enumerates $x$ into $A$ (so $χ_{A} (x) = 1 \neq = 0 = Φ_{e}^{B} (x)$ by use-preservation) and sets restraint $r (2 e, s) =$ the use of that computation, freezing $B$ below it. The construction is finite-injury when $∣ I_{n} ∣ < \infty$ for every $n$ ; the **finite-injury lemma** then yields, by induction on $n$ , that each $R_{n}$ acts finitely often and is met. A set $A$ is **low** if $A^{'} \equiv_{T} \emptyset^{'}$ ; a **minimal pair** is a pair of c.e. degrees $a, b > 0$ whose only common lower bound is $0$ ( $a \land b = 0$ ).

Counterexamples to common slips Intermediate+

"Each requirement acts at most once, so there is no injury." The witness $x (2 e)$ for $R_{2 e}$ can be chosen fresh and never re-chosen, so $R_{2 e}$ enumerates at most once — but its restraint can still be violated by a higher-priority requirement enumerating below the use into $B$ . Injury is the violation of restraint by others, not repeated action by oneself; finitely many higher requirements cause finitely many injuries.
"Injured means failed." Injury is temporary: a requirement injured at stage $s$ re-initialises (picks a new witness larger than all current restraints) and tries again. The finite-injury lemma guarantees a last injury, after which the (re-initialised) requirement succeeds. A requirement fails only if injured infinitely often, which finite injury rules out.
"Post's problem is solved by a simple or hypersimple set." Those were Post's own attempts and they fail: by Dekker every nonzero c.e. degree contains a simple set, so simplicity constrains $\leq_{m}$ and $\leq_{tt}$ hardness but is compatible with Turing-completeness (42.04.03). Intermediate Turing degree needs the direct priority construction, not a structural thinness property.
"The c.e. degrees are dense, so there are no minimal pairs." Density (Sacks) says no two c.e. degrees are immediately adjacent; minimal pairs say two c.e. degrees can have infimum $0$ . Both hold: density is about the order between comparable degrees, minimal pairs about meets of incomparable ones. $R$ is dense and has minimal pairs and is non-distributive all at once.

Key theorem with proof Intermediate+

The organising result is the Friedberg-Muchnik theorem: Post's problem has a positive answer, supplied by the finite-injury priority method. Its proof is the prototype every later priority argument refines.

Theorem (Friedberg-Muchnik). There exist computably enumerable sets $A$ and $B$ with $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ . Consequently there are c.e. degrees $a, b$ with $0 <_{T} a, b <_{T} 0^{'}$ and $a, b$ incomparable; in particular Post's problem has a solution. ^{[Soare Ch. 7]}

Proof. Build $A = ⋃_{s} A_{s}$ , $B = ⋃_{s} B_{s}$ by stages, $A_{0} = B_{0} = \emptyset$ , to meet $$ R_{2e} : \Phi_e^B \ne \chi_A, \qquad R_{2e+1} : \Phi_e^A \ne \chi_B, $$ ranked $R_{0}, R_{1}, R_{2}, \dots$ by priority. Each $R_{n}$ controls one witness; it is satisfied once it has diagonalised, and requires attention at stage $s$ when it is unsatisfied and a suitable convergent computation appears. Each requirement, when first considered or when injured, is assigned a fresh witness larger than every number mentioned so far (so larger than all current restraints).

Strategy for $R_{2 e}$ (odd indices symmetric, swapping $A, B$ ): let $x$ be its current witness. If $R_{2 e}$ is unsatisfied and $Φ_{e, s}^{B_{s}} (x) ↓= 0$ with use $u$ , then $R_{2 e}$ acts: enumerate $x$ into $A_{s + 1}$ and set restraint $r (2 e, s) = u$ , freezing $B$ below $u$ . Now $χ_{A} (x) = 1$ , while $Φ_{e}^{B} (x) = 0$ provided $B ↾ u$ is preserved (use lemma, 42.04.04); the restraint asks exactly that no number $< u$ later enters $B$ .

Stage $s + 1$ . Find the highest-priority requirement $R_{n}$ with $n \leq s$ that requires attention; let it act per its strategy. Acting may enumerate one number and reset the restraints of all lower-priority requirements, injuring any lower $R_{k}$ whose protected computation used the number just enumerated; each injured $R_{k}$ is re-assigned a fresh witness exceeding all current restraints. Only one requirement acts per stage.

Verification. By induction on $n$ we show $R_{n}$ acts finitely often, is eventually never injured, and is met. Suppose this holds for all $m < n$ ; let $s_{0}$ be a stage after which no $R_{m}$ ( $m < n$ ) ever acts again (it exists since each acts finitely often). After $s_{0}$ no higher-priority requirement enumerates anything, so $R_{n}$ is never again injured and its current witness $x$ is permanent. Consider $R_{n} = R_{2 e}$ . If $Φ_{e}^{B} (x) ↓= 0$ , the computation appears at some stage $> s_{0}$ (its use is in $B$ , which is frozen below the relevant restraint), $R_{n}$ acts once enumerating $x$ into $A$ , and the frozen $B ↾ u$ preserves $Φ_{e}^{B} (x) = 0 \neq = 1 = χ_{A} (x)$ : $R_{n}$ is met. If $Φ_{e}^{B} (x) \neq = 0$ — it diverges or converges to a nonzero value — then since $x \in / A$ (it was never enumerated) $χ_{A} (x) = 0$ , so $Φ_{e}^{B} (x) \neq = 0 = χ_{A} (x)$ unless $Φ_{e}^{B} (x) = 0$ , which we excluded; either way $Φ_{e}^{B} \neq = χ_{A}$ . So $R_{n}$ is met in every case, and it acted at most once after $s_{0}$ . By induction every requirement is met, so $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ . Both $A, B$ are c.e. (the construction is an effective stage enumeration), and $A, B \leq_{T} \emptyset^{'}$ since the search for convergent computations is $\emptyset^{'}$ -decidable; with $A \neq \leq_{T} B$ giving $A \neq = \emptyset$ -degree and $A \neq \leq_{T} \emptyset^{'}$ -complete forced by incomparability, $0 <_{T} de g (A), de g (B) <_{T} 0^{'}$ . $□$

Bridge. The finite-injury lemma is the foundational reason the construction converges: each requirement is injured only by the finitely many higher-priority ones, each of which acts at most once after its witness settles, so the injury set $I_{n}$ is finite and a last injury exists. This is exactly the relativised diagonal of 42.04.04 deployed against every potential reduction at once — where the Kleene-Post finite-extension argument there diagonalised against $Φ_{e}$ with full oracle freedom, here the set is c.e. so numbers can only be added, and the priority ranking is what buys back the freedom the one-sidedness costs. The construction builds toward the Sacks density and splitting theorems, where the same skeleton — requirements, restraint, injury — runs with infinitely many injuries controlled by a true path, and it appears again in every $0^{''}$ - and $0^{'''}$ -priority argument of the subject. This generalises Post's failed thinness programme: where simplicity could only bound $\leq_{m}$ hardness, the priority method controls $\leq_{T}$ directly, which is the central insight that finally populated the interval $(0, 0^{'})$ . Putting these together, the bridge is the finite-injury lemma itself — countable interference forcing eventual satisfaction — the single combinatorial fact from which the entire local theory of $R$ is generated.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the finite-injury lemma for the Friedberg-Muchnik construction: every requirement $R_{n}$ is injured only finitely often and acts only finitely often.

Hint

Induct on $n$ . Use that $R_{n}$ is injured only when a higher-priority requirement acts, and that each higher requirement, once it has its permanent witness, acts at most once.

Answer

Induct on the priority index $n$ . Base/step together: assume every $R_{m}$ with $m < n$ acts only finitely often (vacuous for $n = 0$ ). Then there is a stage $s_{0}$ after which no $R_{m}$ , $m < n$ , ever acts. $R_{n}$ is injured only when some higher-priority $R_{m}$ enumerates a number below $R_{n}$ 's restraint; after $s_{0}$ no such $R_{m}$ acts, so $R_{n}$ is never injured after $s_{0}$ , giving $∣ I_{n} ∣ < \infty$ . After its last injury (at or before $s_{0}$ ), $R_{n}$ holds a fixed witness $x$ . $R_{n}$ acts at most once thereafter: a single enumeration of $x$ diagonalises it (if the triggering computation appears), and once satisfied it never acts again; if no triggering computation ever appears it acts zero further times. Hence $R_{n}$ acts finitely often, completing the induction. Therefore every requirement is injured and acts finitely often. Rubric: full credit for the induction on priority, the existence of $s_{0}$ from the inductive hypothesis, the finiteness of $I_{n}$ after $s_{0}$ , and the at-most-once action of the settled requirement.

Exercise 4 (medium, symbolic).

Show that the sets $A, B$ produced by Friedberg-Muchnik satisfy $A, B \leq_{T} \emptyset^{'}$ and are noncomputable, hence $0 <_{T} de g (A) <_{T} 0^{'}$ (and symmetrically for $B$ ).

Hint

The whole construction asks $\emptyset^{'}$ -questions ("does $Φ_{e, s}^{B_{s}} (x)$ ever converge?"). Noncomputability follows from incomparability: a computable set is below everything.

Answer

$A \leq_{T} \emptyset^{'}$ : the construction is effective except for detecting convergent computations $Φ_{e, s}^{B_{s}} (x) ↓$ , which is a $Σ_{1}$ (halting-style) question answerable by the oracle $\emptyset^{'}$ ; so the entire stage function, and thus $χ_{A}$ , is computable from $\emptyset^{'}$ . Symmetrically $B \leq_{T} \emptyset^{'}$ . Noncomputability: if $A$ were computable then $A \leq_{T} B$ (a computable set reduces to every set), contradicting $A \neq \leq_{T} B$ ; so $A$ is noncomputable, i.e. $de g (A) >_{T} 0$ . Strictly below $0^{'}$ : if $de g (A) = 0^{'}$ then $A \equiv_{T} \emptyset^{'} \geq_{T} B$ (since $B \leq_{T} \emptyset^{'}$ ), giving $B \leq_{T} A$ , contradicting $B \neq \leq_{T} A$ ; so $de g (A) <_{T} 0^{'}$ . Hence $0 <_{T} de g (A) <_{T} 0^{'}$ , and symmetrically for $B$ ; both are intermediate c.e. degrees, solving Post's problem. Rubric: full credit for the $\emptyset^{'}$ -bound from the convergence search, noncomputability from incomparability, and the strict-below- $0^{'}$ argument from incomparability with $B$ .

Exercise 5 (medium, multiple-choice).

The Sacks density theorem states that for c.e. degrees $a <_{T} b$ there is a c.e. degree $c$ with $a <_{T} c <_{T} b$ . Which structural consequence follows immediately?

$\mathcal R$ is a lattice.
$\mathcal R$ has no maximal element.
$\mathcal R$ has no two distinct comparable c.e. degrees that are order-adjacent (no covers).
Every c.e. degree is minimal.

Hint

"Adjacent" / "covering" means nothing strictly in between. What does density say about that?

Answer

C. Density says that whenever $a <_{T} b$ are c.e. there is a c.e. degree strictly between, so no c.e. degree covers another — there are no order-adjacent pairs in $R$ . Option B is false ( $0^{'}$ is the greatest c.e. degree), A is false ( $R$ is not a lattice and not distributive), and D is false (minimal degrees are not c.e.; density is precisely the opposite phenomenon for $R$ ).

Exercise 6 (hard, symbolic).

Prove the minimal pair theorem (sketch the priority strategy): there exist c.e. degrees $a, b > 0$ with $a \land b = 0$ , i.e. c.e. sets $A, B$ noncomputable with $C \leq_{T} A$ and $C \leq_{T} B \Rightarrow C$ computable.

Hint

Besides noncomputability requirements ( $A \neq = Φ_{e}$ , $B \neq = Φ_{e}$ ), add for each pair $(i, j)$ a requirement $N_{i, j}$ : if $Φ_{i}^{A} = Φ_{j}^{B}$ is total, that common function is computable. The strategy preserves agreement by restraining one side at a time.

Answer

Build c.e. $A, B$ to meet positive requirements $P_{e}^{A} : A \neq = Φ_{e}$ and $P_{e}^{B} : B \neq = Φ_{e}$ (making both noncomputable, by the usual follower/diagonalisation), and meet requirements $N_{i, j}$ : if $Φ_{i}^{A} = Φ_{j}^{B}$ is total, then it is computable. Strategy for $N_{i, j}$ at stage $s$ : watch for arguments $x$ where $Φ_{i, s}^{A_{s}} (x) ↓= Φ_{j, s}^{B_{s}} (x) ↓$ (the two sides agree). When a new agreement at $x$ appears, $N_{i, j}$ imposes restraint preserving one of the two computations — whichever side a higher-priority $P$ -requirement is not currently trying to change — so that the agreed value at $x$ is frozen on at least one side.

The minimal-pair combinatorics: if $Φ_{i}^{A} = Φ_{j}^{B} = f$ is total, then to compute $f (x)$ search for any stage $s$ with $Φ_{i, s}^{A_{s}} (x) ↓= Φ_{j, s}^{B_{s}} (x) ↓$ ; the key lemma is that the least such agreement value is the true value $f (x)$ , because the restraint scheme ensures that whenever both sides converge at $x$ at a stage where neither side is subsequently injured below the use, the value persists — and at least one side is always preservable since $A$ and $B$ are injured by different $P$ -requirements, never simultaneously below the relevant use. Thus $f$ is computable, so any $C \leq_{T} A$ and $C \leq_{T} B$ is computed by both and hence equals such an $f$ , giving $C$ computable; $a \land b = 0$ . The injuries are finite per requirement (finite-injury priority), so all requirements are met. Rubric: full credit for the $P$ / $N$ requirement split, the agreement-preservation restraint on one side, the least-agreement-stage computation of $f$ , and the conclusion that the common infimum is $0$ .

Exercise 7 (hard, symbolic).

Show that the existence of a minimal pair makes the c.e. degrees $R$ non-distributive, and contrast with the global degrees $D$ where Spector minimal degrees exist but the c.e. analogue (minimal c.e. degree) does not.

Hint

Minimal pairs plus Sacks splitting give a copy of a non-distributive lattice; density forbids any c.e. degree from being minimal in $R$ .

Answer

Non-distributivity: take a minimal pair $a, b$ ( $a \land b = 0$ ) and, by Sacks splitting applied to $a \lor b$ or by a direct construction, arrange a c.e. degree $c$ with $c \leq a \lor b$ , $c \neq \leq a$ , $c \neq \leq b$ . Then $c \land a$ and $c \land b$ are both $0$ (each lies under the minimal pair from one side), so $(c \land a) \lor (c \land b) = 0$ , while $c \land (a \lor b) = c \neq = 0$ ; distributivity would force these equal, so $R$ is non-distributive — it embeds the diamond $N_{5}$ / $M_{3}$ -type failure. Contrast with $D$ : in the global degrees there is a minimal degree $m > 0$ (Spector, by perfect-tree forcing) with nothing strictly below it but $0$ ; but in $R$ no c.e. degree is minimal, because Sacks density puts a c.e. degree strictly between $0$ and any given nonzero c.e. degree. So minimality is a global ( $D$ ) phenomenon incompatible with the c.e. ( $R$ ) density — minimal degrees are never c.e., and c.e. degrees are never minimal. Rubric: full credit for the diamond construction from a minimal pair giving non-distributivity, and the density argument that no c.e. degree is minimal while Spector minimal degrees exist in $D$ .

Advanced results Master

The priority method moves from its founding application — Post's problem — to a structure theory of the c.e. degrees $R$ and a global theory of $D$ , organised by the level of injury the construction tolerates. Finite injury suffices for incomparability and splitting; the density and minimal-pair theorems require infinite injury controlled by a true path; the global structure is reached by forcing rather than enumeration.

Theorem 1 (Sacks splitting and density). Every nonzero c.e. degree $a$ splits: there are c.e. degrees $a_{0}, a_{1} <_{T} a$ with $a_{0} \lor a_{1} = a$ and $a_{0}, a_{1}$ incomparable (a finite-injury argument) ^{[Soare-RE Ch. VII]}. The Sacks density theorem: for c.e. degrees $a <_{T} b$ there is a c.e. degree $c$ with $a <_{T} c <_{T} b$ , by an infinite-injury ( $0^{''}$ -priority) construction in which the requirements are injured infinitely often but the true path through the tree of strategies meets each requirement along an outcome injured only finitely often. Density makes $R$ a dense partial order with no covering pairs, so $R$ is an upper semilattice that is dense, with $0$ and $0^{'}$ its endpoints, and no c.e. degree is minimal in it.

Theorem 2 (minimal pairs and non-distributivity). There are c.e. degrees $a, b > 0$ forming a minimal pair, $a \land b = 0$ (Lachlan, Yates), so $R$ has nontrivial infima at the bottom even though it is not a lattice ^{[Soare-RE Ch. IX]}. Combined with splitting, minimal pairs make $R$ non-distributive and force the failure of the diamond lattice as an initial segment in a controlled way; every finite lattice embeds into $R$ (Lachlan-Soare), and the question of which lattices embed as initial segments drives the deepest combinatorics of the subject. The infinitary content is that infima must be preserved against infinitely many threatening reductions, the prototype $0^{''}$ -argument.

Theorem 3 (infinite injury and the Sacks jump theorem). The infinite-injury method systematises constructions where a requirement's restraint oscillates unboundedly but its $lim inf$ is finite along the true path; formalised as $0^{''}$ - and $0^{'''}$ -priority (the tree method, with strategies arranged on a tree of guessed outcomes and a true path selected by the actual behaviour) ^{[Soare-RE Ch. XI-XII]}. The Sacks jump theorem: a degree $c$ is the jump of a c.e. degree $a$ (with $a \leq_{T} 0^{'}$ ) iff $c$ is c.e. in and above $0^{'}$ ; in particular there are low c.e. degrees ( $a^{'} = 0^{'}$ ) and high c.e. degrees ( $a^{'} = 0^{''}$ ) strictly between $0$ and $0^{'}$ , so the jump does not separate the c.e. degrees by Turing degree. The low/high hierarchy stratifies $R$ by how much information the jump extracts, refining the picture of 42.04.04.

Theorem 4 (the global structure of $D$ : minimal degrees and joins). Beyond the c.e. degrees, Spector minimal degrees exist: a degree $m > 0$ with no degree strictly between $0$ and $m$ , built by forcing with perfect (computable) binary trees, each requirement either thinning the tree to force $Φ_{e}^{G}$ partial or computable, or passing to a splitting subtree to force $Φ_{e}^{G} \equiv_{T} G$ ^{[Lerman Ch. VII-VIII]}. The Posner-Robinson join theorem: for every noncomputable $A$ there is $G$ with $A \oplus G \equiv_{T} G^{'} \equiv_{T} \emptyset^{'} \oplus G$ , so any noncomputable degree can be cupped to the jump by a single degree — a cornerstone of definability arguments. These forcing constructions sit at the $0$ -degree end of the global theory and are not c.e.-realisable: minimality is incompatible with c.e.-ness by Sacks density.

Theorem 5 (definability and the decidability of fragments). The c.e. degrees $R$ and the global degrees $D$ are rich enough to interpret arithmetic: the first-order theory of $D$ is recursively isomorphic to true second-order arithmetic (Simpson), and the theory of $R$ is undecidable ^{[Lerman Ch. IX]}. At low quantifier complexity the picture is tractable: the $Σ_{1}$ theory of $R$ (existential statements about finite configurations of c.e. degrees) is decidable, reducing to finite-lattice embeddability; the $Σ_{2}$ theory of $R$ is also decidable, but the $Σ_{3}$ theory is undecidable. The jump is first-order definable in $D$ (Cooper, Shore), and the major open problem is whether $D$ has nontrivial automorphisms — whether the degrees are a rigid structure — with partial rigidity results coding arithmetic into the order.

Synthesis. The priority method is computability theory's foundational reason the interval $(0, 0^{'})$ is densely populated rather than empty: where the global structure of 42.04.04 came from the jump and from forcing, the local structure of the c.e. degrees comes from building sets in stages to meet infinitely many competing requirements, and this is exactly the relativised diagonal of 42.04.04 turned into a scheduling problem solved by priority. The finite-injury lemma — each requirement injured by only finitely many higher ones, hence eventually permanently met — is the central insight, and it generalises Post's failed thinness programme of 42.04.03 (where simplicity bounded $\leq_{m}$ but not $\leq_{T}$ ) into direct control of Turing degree: the Friedberg-Muchnik sets are intermediate, and Sacks splitting and density extend the same skeleton to make $R$ a dense, non-distributive upper semilattice into which every finite lattice embeds.

Putting these together, infinite injury and the tree method run the construction against requirements injured infinitely often, controlled by a true path, which is dual to the finite case: there the schedule terminated, here it converges along one branch. The bridge is the requirement-restraint-injury skeleton itself, which scales from $0^{'}$ to $0^{''}$ to $0^{'''}$ and underlies the Sacks jump theorem, the low/high hierarchy refining the jump of 42.04.04, and the arithmetical hierarchy 42.04.05 in which these c.e. sets sit at the $Σ_{1}$ base; what forcing with perfect trees does for minimal degrees in $D$ , the priority method does for the c.e. degrees in $R$ , and the definability theory that interprets arithmetic into both is the foundational reason the whole landscape is as intricate as arithmetic itself.

Full proof set Master

Proposition 1 (finite-injury lemma). In the Friedberg-Muchnik construction every requirement $R_{n}$ is injured finitely often and acts finitely often.

Proof. Induct on $n$ . Assume each $R_{m}$ , $m < n$ , acts finitely often; pick $s_{0}$ past the last action of every such $R_{m}$ . $R_{n}$ is injured only by a higher-priority requirement enumerating below its restraint, so $R_{n}$ suffers no injury after $s_{0}$ , giving $∣ I_{n} ∣ < \infty$ . After its final injury $R_{n}$ holds a permanent witness $x$ and acts at most once thereafter (a single enumeration of $x$ when the triggering computation appears, after which it is satisfied and dormant). Hence $R_{n}$ acts finitely often, closing the induction. $□$

Proposition 2 (Friedberg-Muchnik; each requirement is met). The construction satisfies every $R_{n}$ , so $A \neq \leq_{T} B$ and $B \neq \leq_{T} A$ .

Proof. By Proposition 1 fix $s_{0}$ after which no higher-priority requirement acts, so $R_{n} = R_{2 e}$ has a permanent witness $x$ and permanent restraint environment. If $Φ_{e}^{B} (x) ↓= 0$ : the convergent computation appears at some stage $> s_{0}$ with use $u$ ; $R_{n}$ enumerates $x$ into $A$ and freezes $B ↾ u$ , and since no higher requirement acts after $s_{0}$ the freeze holds, so by the use lemma $Φ_{e}^{B} (x) = 0 \neq = 1 = χ_{A} (x)$ . If $Φ_{e}^{B} (x)$ diverges or converges to a nonzero value: $x$ is never enumerated, so $χ_{A} (x) = 0 \neq = Φ_{e}^{B} (x)$ (the latter is not $0$ ). In all cases $Φ_{e}^{B} \neq = χ_{A}$ . Symmetrically the odd requirements give $Φ_{e}^{A} \neq = χ_{B}$ . Meeting all $R_{2 e}$ gives $A \neq \leq_{T} B$ ; all $R_{2 e + 1}$ give $B \neq \leq_{T} A$ . $□$

Proposition 3 (the constructed degrees are intermediate). $A, B$ are c.e., noncomputable, and $\leq_{T} \emptyset^{'}$ , with $0 <_{T} de g (A), de g (B) <_{T} 0^{'}$ and $de g (A), de g (B)$ incomparable.

Proof. $A, B$ are c.e. as effective stage unions. The only non-effective step is detecting $Φ_{e, s}^{B_{s}} (x) ↓$ , a $Σ_{1}$ question decidable by $\emptyset^{'}$ , so $A, B \leq_{T} \emptyset^{'}$ . Noncomputable: a computable set reduces to every set, so $A$ computable would give $A \leq_{T} B$ , contradicting Proposition 2; thus $de g (A) >_{T} 0$ . Strictly below $0^{'}$ : if $A \equiv_{T} \emptyset^{'}$ then since $B \leq_{T} \emptyset^{'} \equiv_{T} A$ we get $B \leq_{T} A$ , contradicting incomparability; so $de g (A) <_{T} 0^{'}$ . Incomparability is Proposition 2. The symmetric facts hold for $B$ . $□$

Proposition 4 (Sacks splitting, finite-injury form). Every noncomputable c.e. set $C$ splits into disjoint c.e. sets $A_{0} ⊔ A_{1} = C$ with $A_{0}, A_{1} <_{T} C$ and $de g (A_{0}), de g (A_{1})$ incomparable, $de g (A_{0}) \lor de g (A_{1}) = de g (C)$ .

Proof (skeleton). Enumerate $C = ⋃_{s} C_{s}$ and route each new element of $C$ into exactly one of $A_{0}, A_{1}$ . Requirements $S_{e}^{i} : Φ_{e}^{A_{1 - i}} \neq = χ_{A_{i}}$ (for $i = 0, 1$ ) ensure $A_{i} \neq \leq_{T} A_{1 - i}$ , and the routing preserves $A_{0} \oplus A_{1} \equiv_{T} C$ (so the join is $de g (C)$ ) while each $A_{i} <_{T} C$ since $C$ computes both halves but not conversely. Each $S_{e}^{i}$ owns a follower and acts by directing a $C$ -element to the opposite side to spoil a threatening reduction, imposing restraint of the standard use-preserving kind; injuries are caused only by higher-priority $S$ -requirements rerouting below the restraint, finitely often by the finite-injury lemma. So all $S_{e}^{i}$ are met, giving incomparable halves whose join is $de g (C)$ . $□$

Proposition 5 (minimal pair; computability of the common reduct). There are noncomputable c.e. $A, B$ such that $Φ_{i}^{A} = Φ_{j}^{B}$ total $\Rightarrow Φ_{i}^{A}$ computable; hence $de g (A) \land de g (B) = 0$ .

Proof (skeleton). Meet $P$ -requirements forcing $A, B$ noncomputable and $N_{i, j}$ : if $Φ_{i}^{A} = Φ_{j}^{B}$ is total it is computable. Strategy for $N_{i, j}$ : maintain restraint preserving, for each argument $x$ at which both sides have converged to a common value, at least one of the two computations; the two sides are injured by different $P$ -requirements, so they are never both disturbed below the use at the same stage. If $Φ_{i}^{A} = Φ_{j}^{B} = f$ is total, compute $f (x)$ by searching for the first stage with $Φ_{i, s}^{A_{s}} (x) ↓= Φ_{j, s}^{B_{s}} (x) ↓$ ; the preserved side guarantees this common value is final, so $f$ is computable. Therefore any $D \leq_{T} A$ and $D \leq_{T} B$ equals such an $f$ and is computable, so the infimum of the two degrees is $0$ . Finite injury (each $N_{i, j}$ injured finitely often by higher-priority requirements) makes all requirements met. $□$

Proposition 6 (Spector minimal degree, statement and forcing skeleton). There is a degree $m > 0$ with no degree strictly between $0$ and $m$ .

Proof (skeleton). Build $G$ as the unique path through a nested sequence of perfect computable binary trees $T_{0} \supseteq T_{1} \supseteq \dots$ . Requirement $M_{e}$ acts on $T_{e}$ to produce $T_{e + 1}$ : if no subtree of $T_{e}$ forces $Φ_{e}^{G}$ total, thin to a subtree on which $Φ_{e}^{G}$ is partial; if $Φ_{e}^{G}$ is forced total, either it is computable on a subtree (pass to it) or $T_{e}$ has an $e$ -splitting subtree, on which distinct branches give distinct $Φ_{e}$ -values, forcing $Φ_{e}^{G} \equiv_{T} G$ . The Spector splitting lemma guarantees one of these alternatives. The resulting $G$ has: every $Φ_{e}^{G}$ either partial, or computable, or computing $G$ ; so any $D \leq_{T} G$ is either computable or $\equiv_{T} G$ , i.e. $de g (G)$ is minimal. $□$

Proposition 7 (Posner-Robinson, statement and the cupping consequence). For every noncomputable $A$ there is $G$ with $A \oplus G \equiv_{T} G^{'} \equiv_{T} \emptyset^{'} \oplus G$ ; consequently $de g (A) \lor de g (G) = de g (G)^{'}$ and $A$ is cupped to the jump by a single degree.

Proof (skeleton). Force $G$ by finite conditions (Posner-Robinson forcing) so that $A$ becomes computable from $G^{'}$ relative to $G$ via a coding that uses $A$ to resolve the jump, while keeping $G$ generic enough that $G^{'} \equiv_{T} \emptyset^{'} \oplus G \oplus A$ and $A \leq_{T} G \oplus \emptyset^{'}$ collapses to $A \oplus G \equiv_{T} G^{'}$ . The cupping statement is the immediate reading: $de g (A) \lor de g (G) = de g (A \oplus G) = de g (G^{'}) = de g (G)^{'}$ , so adjoining $G$ raises $A$ exactly to the jump of $G$ . This is the join-theoretic engine behind definability results, since it expresses every noncomputable degree as a join-component of a jump. $□$

Connections Master

Turing reducibility, oracles, and the jump 42.04.04, the prerequisite, supplies everything the priority method operates on: the reducibility $\leq_{T}$ the requirements diagonalise against, the use lemma that makes restraint preserve computations, the jump and the bound $A, B \leq_{T} \emptyset^{'}$ , and the Kleene-Post finite-extension argument that is the non-effective ancestor of finite injury. That unit owns the jump and the global structure of $D$ by counting and forcing; this unit owns the effective (c.e.) constructions — incomparable c.e. degrees, splitting, density, minimal pairs — that populate the interval $(0, 0^{'})$ the jump bounds.
Computably enumerable sets, creative and simple 42.04.03 frames Post's problem and supplies its failed attempts: the simple and hypersimple sets that bound $\leq_{m}$ and $\leq_{tt}$ hardness without bounding Turing degree (Dekker), and the recognition that a structural thinness property cannot force intermediate degree. This unit resolves exactly that open question — the Friedberg-Muchnik construction builds the intermediate degrees Post's program could not reach — and the simple-set requirement schedule of that unit is the historical seed of the priority requirement list used here.
The arithmetical hierarchy 42.04.05 places the c.e. sets of this unit at the $Σ_{1}^{0}$ base and supplies the complexity calibration of the priority method: a finite-injury construction is a $0^{'}$ -argument, density and minimal pairs are $0^{''}$ -arguments, and the tree method climbs to $0^{'''}$ . The low/high hierarchy within $R$ (Theorem 3) measures degrees below $0^{'}$ by where their jump lands in the $0^{'}, 0^{''}$ scale of that hierarchy, so the syntactic ladder of 42.04.05 is the meter for the injury level a construction needs.
The halting problem and recursion theorem 42.04.02 is the source of the diagonal these requirements deploy: each $R_{2 e} : Φ_{e}^{B} \neq = χ_{A}$ is a diagonalisation against a single index, run simultaneously against all indices, and the recursion theorem underlies the self-referential follower assignments in the splitting and minimal-pair constructions. That unit owns the single diagonal and the completeness of $K = \emptyset^{'}$ ; this unit runs infinitely many diagonals at once under a priority schedule that keeps them from destroying one another.

Historical & philosophical context Master

Post's problem was posed in Emil Post's 1944 paper "Recursively enumerable sets of positive integers and their decision problems," which asked whether every undecidable c.e. set is Turing-equivalent to the halting problem, or whether a c.e. set of intermediate degree exists ^{[Soare Ch. 7]}. Post attacked it through structural thinness — simple, hypersimple, and hyperhypersimple sets — hoping a lattice-theoretic property of a c.e. set would force its Turing degree strictly between $0$ and $0^{'}$ ; the program, pursued through the 1940s and early 1950s, controlled the many-one and truth-table structure but, as James Dekker's deficiency-set construction made clear, left the Turing degree free. The problem was solved independently in 1956–1957 by Richard Friedberg in the United States and Albert Muchnik in the Soviet Union, who each invented the priority method: constructing two c.e. sets of incomparable Turing degree directly, by a finite-injury argument scheduling infinitely many diagonalisation requirements under a priority ranking.

The method became the central technique of classical computability theory. Gerald Sacks's work of the early 1960s — the splitting theorem (1963), the density theorem (1964), and the jump theorem — extended the priority method to infinite injury, with the density theorem's $0^{''}$ -argument introducing the tree-of-strategies analysis later systematised by Robert Soare and others into the $0^{'''}$ -priority method ^{[Soare-RE Ch. XII]}. Alistair Lachlan and Clifford Yates established minimal pairs and the failure of distributivity in the c.e. degrees, and Lachlan's work on the undecidability of the theory of $R$ and the embeddability of finite lattices charted the limits of the structure. In parallel, Clifford Spector's 1956 minimal-degree construction by perfect-tree forcing, and later the Posner-Robinson join theorem and the Simpson-Shore definability results coding arithmetic into the degrees, built the global theory of $D$ . The Friedberg-Muchnik theorem stands as the method's founding triumph and the resolution of the first major problem of the field.

Bibliography Master

@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{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{spector1956minimal,
  author  = {Spector, Clifford},
  title   = {On degrees of recursive unsolvability},
  journal = {Annals of Mathematics},
  volume  = {64},
  number  = {3},
  year    = {1956},
  pages   = {581--592}
}

@article{sacks1963splitting,
  author  = {Sacks, Gerald E.},
  title   = {On the degrees less than $\mathbf{0}'$},
  journal = {Annals of Mathematics},
  volume  = {77},
  number  = {2},
  year    = {1963},
  pages   = {211--231}
}

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

@article{lachlan1966lower,
  author  = {Lachlan, Alistair H.},
  title   = {Lower bounds for pairs of recursively enumerable degrees},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {16},
  number  = {1},
  year    = {1966},
  pages   = {537--569}
}

@article{yates1966minimalpair,
  author  = {Yates, C. E. M.},
  title   = {A minimal pair of recursively enumerable degrees},
  journal = {The Journal of Symbolic Logic},
  volume  = {31},
  number  = {2},
  year    = {1966},
  pages   = {159--168}
}

@article{posnerrobinson1981,
  author  = {Posner, David B. and Robinson, Robert W.},
  title   = {Degrees joining to $\mathbf{0}'$},
  journal = {The Journal of Symbolic Logic},
  volume  = {46},
  number  = {4},
  year    = {1981},
  pages   = {714--722}
}

@book{soare1987re,
  author    = {Soare, Robert I.},
  title     = {Recursively Enumerable Sets and Degrees},
  series    = {Perspectives in Mathematical Logic},
  publisher = {Springer},
  year      = {1987}
}

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

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

Prerequisites

42.04.04

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 6 (read the informal account of building a set in stages to meet a list of demands, where a later, more urgent demand may temporarily spoil what an earlier one arranged, but each demand is spoiled only finitely often and so is met in the end — the 'priority' picture stated before any formal construction); Cooper 2004 *Computability Theory* (Chapman & Hall/CRC) Ch. 10 for Post's problem and the finite-injury idea told plainly
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 6-7 (Post's problem and its failed attempts via simple/hypersimple sets; the Friedberg-Muchnik theorem that incomparable c.e. degrees exist, by the finite-injury priority method — requirements $R_e$/$N_e$, the priority ordering, restraint and injury, the finite-injury lemma; the structure of the c.e. degrees $\mathcal R$: Sacks splitting and density, minimal pairs, non-distributivity); Cooper 2004 *Computability Theory* (Chapman & Hall/CRC) Ch. 10-11 (the Friedberg-Muchnik construction in full, the Sacks density theorem)
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 6-12 and the historical notes (the finite-injury priority method and the solution to Post's problem; the c.e. degrees $\mathcal R$ as an upper semilattice with $\mathbf 0$ and $\mathbf 0'$ — the Sacks density and splitting theorems, minimal pairs, the failure of distributivity, the embedding of every finite lattice; infinite-injury and the $\mathbf 0'''$-priority / tree method, the Sacks jump theorem; the global structure $\mathcal D$ — Spector minimal degrees by forcing with perfect trees, the Posner-Robinson join theorem, automorphism and definability questions; the decidability of the $\Sigma_2$ theory of $\mathcal R$ and the undecidability of richer fragments); Soare 1987 *Recursively Enumerable Sets and Degrees* (Springer) Ch. VII-XII (the priority method systematised, finite and infinite injury, the lattice $\mathcal R$); Lerman 1983 *Degrees of Unsolvability* (Springer) Ch. VII-IX (minimal degrees, the global theory of $\mathcal D$)

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 6-7 develop POST'S PROBLEM — whether a c.e. set of intermediate Turing degree exists, $\mathbf 0 <_T A <_T \mathbf 0'$ — and its resolution. Post's own attempts via SIMPLE and HYPERSIMPLE sets fail (they bound $\le_m$ and $\le_{tt}$ hardness but leave Turing degree free, by Dekker), so the problem is solved by direct construction. The FRIEDBERG-MUCHNIK THEOREM: there are c.e. sets $A, B$ of incomparable Turing degree, hence intermediate degrees exist, built by the FINITE-INJURY PRIORITY METHOD. Requirements $R_{2e} : \Phi_e^B \ne \chi_A$ and $R_{2e+1} : \Phi_e^A \ne \chi_B$ are arranged in a PRIORITY ORDERING $R_0, R_1, R_2, \dots$; each $R_n$ picks a fresh WITNESS $x$ and, when a computation $\Phi_e^{B_s}(x)\!\downarrow = 0$ appears, ENUMERATES $x$ into $A$ to diagonalise, imposing RESTRAINT to preserve the use of that computation. A higher-priority requirement enumerating a number below the restraint of a lower-priority one INJURES it; the FINITE-INJURY LEMMA shows each $R_n$ is injured only finitely often (only by the finitely many higher-priority requirements, each acting at most once after the witness settles), so from some stage on it is never injured and is met. The STRUCTURE of the c.e. degrees $\mathcal R$: the SACKS DENSITY THEOREM (between any two c.e. degrees $\mathbf a <_T \mathbf b$ there is a c.e. $\mathbf c$ with $\mathbf a <_T \mathbf c <_T \mathbf b$); the SACKS SPLITTING THEOREM (every nonzero c.e. degree splits into two incomparable c.e. degrees joining to it); MINIMAL PAIRS (c.e. $\mathbf a, \mathbf b > \mathbf 0$ with $\mathbf a \wedge \mathbf b = \mathbf 0$), the NON-DISTRIBUTIVITY of $\mathcal R$, and the embedding of every finite lattice. INFINITE-INJURY ($\mathbf 0'''$ arguments, the tree method) and the SACKS JUMP THEOREM. The connection back to logic: $\Pi_1^0$ classes and reverse mathematics (Soare Ch. 6 notes).
Soare, R. I. — Recursively Enumerable Sets and Degrees · Springer, Perspectives in Mathematical Logic (1987). Ch. VII: the FINITE-INJURY priority method systematised — the Friedberg-Muchnik solution to Post's problem, the Sacks splitting theorem, the permitting method; the anatomy of a priority argument (requirement list, priority ranking, witnesses, restraint functions, the injury set $I_n = \{s : R_n$ injured at $s\}$ and the lemma that $|I_n| < \infty$, a finite-injury lemma proved by induction on priority). Ch. VIII: the INFINITE-INJURY method, the $\emptyset''$-priority arguments, the Sacks density theorem (a window argument with infinitely many injuries controlled by a true path), the thickness lemma. Ch. IX-X: minimal pairs (Lachlan, Yates), the non-diamond and the failure of distributivity in $\mathcal R$, the Lachlan-Soare embedding results for finite lattices. Ch. XI-XII: the $\emptyset'''$-priority / TREE METHOD with its $\mathcal O(\omega)$-branching trees of strategies and the true path, the Sacks jump inversion theorem for c.e. degrees ($\mathbf c$ c.e. in and above $\mathbf 0'$ is the jump of a c.e. degree), and the high/low hierarchy within $\mathcal R$. The book is the canonical reference for the technical core of the priority method.
Lerman, M. — Degrees of Unsolvability · Springer, Perspectives in Mathematical Logic (1983). Ch. VII-IX treat the global degree structure $\mathcal D$ as opposed to the local c.e. structure $\mathcal R$: SPECTOR MINIMAL DEGREES by forcing with PERFECT (computable) BINARY TREES — a minimal degree $\mathbf m > \mathbf 0$ with nothing strictly between, where each requirement either thins the tree to a subtree forcing $\Phi_e^G$ partial or computable, or splits it to force $\Phi_e^G \equiv_T G$; the exact-pair theorem and the structure of countable ideals; the POSNER-ROBINSON join theorem (for any $A >_T \emptyset$ noncomputable there is $G$ with $A \oplus G \equiv_T G' \equiv_T \emptyset' \oplus G$, so $A$ is 'cupped to' the jump by a single set, a cornerstone of definability arguments); the AUTOMORPHISM and DEFINABILITY questions for $\mathcal D$ — whether $\mathcal D$ is rigid, which relations (the jump, $\mathbf 0$, the c.e. degrees) are first-order definable, and the coding of arithmetic into $\mathcal D$ that makes its first-order theory recursively isomorphic to true second-order arithmetic. The boundary between the decidable $\Sigma_2$ fragment and the undecidable richer theories (Simpson, Lachlan).

Estimated time

beginner: 20m
intermediate: 55m
master: 105m