Recursion theory studies the mathematical limits of effective computation. It asks which problems can be solved by a uniform procedure, which sets of natural numbers can be enumerated or decided algorithmically, and how to compare problems by their relative computational difficulty. The course develops the central objects of the subject: computable functions, decidable and computably enumerable sets, reductions, and degree structures that measure noncomputability. The early chapters build the basic language of computation and diagonalization, then move from simple notions of decidability to reducibility and the first classification of unsolvable problems. From there, the course develops Turing reducibility and Turing degrees, the jump operator, and relativization, which provide a richer hierarchy of computational power. These tools lead naturally to the arithmetical hierarchy and to classical results such as Post’s problem, the construction of simple sets, and the [Friedberg-Muchnik theorem](/theorems/5435). Later chapters focus on the structure of the computably enumerable degrees and on priority arguments, especially finite injury methods, which are the main technique for building sets with carefully controlled degree-theoretic properties. The final chapters widen the perspective to degrees beyond the c.e. sets and to connections with reverse mathematics, showing how questions about computability interact with [proof theory](/page/Proof%20Theory) and the logical strength of mathematical principles. # Introduction Recursion theory studies the boundary between effective and non-effective mathematics. The course takes Turing reducibility and the structure of Turing degrees as its organising thread: instead of asking only whether a set can be computed, we compare sets by the information needed to compute them. This introductory chapter fixes the viewpoint, explains why undecidable sets become objects of study rather than endpoints, and previews the constructions that drive the subject. The prerequisites are first-order logic, basic set theory, countability, and comfort with diagonal arguments. Elementary model theory helps in later examples, and the later chapters use standard graduate-level language from degree theory, priority arguments, fragments of arithmetic, and reverse mathematics. The main technical language is built from programs, sets of natural numbers, enumerations, and reductions, with the advanced material introduced as an extension of those tools. Throughout the course, computable is treated as a mathematical property of functions and sets after a coding convention has been fixed. ## The Central Problem of Effective Mathematics What does it mean for a mathematical object to contain exactly the information needed to solve another problem? Classical computability begins with procedures, but recursion theory quickly turns procedures into a comparative theory of information. A set $A \subset \mathbb N$ may be undecidable, yet it can still serve as an oracle for deciding other sets; the main question is how such powers compare. A decision problem is represented by a subset of $\mathbb N$ after a coding of finite mathematical objects by natural numbers. This reduction to sets of numbers is not meant to erase mathematical structure. It gives a common language in which proofs about programs, formulas, graphs, groups, and models can be expressed using the same computational notions. [definition: Decision Problem] A decision problem is a subset $A \subset \mathbb N$, where $n \in A$ means that the instance coded by $n$ has answer yes. [/definition] Once problems are represented as sets, the next issue is whether membership can be answered uniformly for every input. This motivates the first class of sets in the course: those whose yes/no question is settled by a total effective procedure. [definition: Computable Set] A set $A \subset \mathbb N$ is computable if its characteristic function $\mathbb{1}_A: \mathbb N \to \{0,1\}$ is a total computable function. [/definition] This definition makes totality part of decidability: the procedure must halt on every input. Many natural mathematical searches halt exactly when a witness exists, so we need a weaker notion that records effective positive evidence without requiring a negative answer in finite time. [definition: Computably Enumerable Set] A set $A \subset \mathbb N$ is computably enumerable if there is a partial computable function $\varphi: \mathbb N \rightharpoonup \mathbb N$ such that \begin{align*} A = \operatorname{Range}(\varphi). \end{align*} [/definition] The range formulation matches the idea of listing all positive instances, but it also explains why computable enumerability is weaker than computability. An enumeration may eventually display every member of $A$ while giving no signal that a number will never appear. Later we will also use equivalent formulations by semidecision procedures and by existential quantification over computable predicates, each expressing the same asymmetry between finding witnesses and ruling them out. [example: Searching For A Witness] Let $(\alpha_i)_{i \in \mathbb N}$ be a computable enumeration of the non-logical axioms of the fixed recursively axiomatised theory $T$. At stage $s$, inspect every finite sequence of formulas whose code is at most $s$, and accept such a sequence as a $T$-proof if each line is either a logical axiom, one of $\alpha_0,\dots,\alpha_s$, or follows from earlier lines by one of the fixed formal inference rules. These are finite checks, so stage $s$ is effective; whenever a sequence is accepted, enumerate the code of its last formula into $A$. If a formula $\theta$ has a $T$-proof, that proof uses only finitely many non-logical axioms, for instance among $\alpha_0,\dots,\alpha_r$, and has some finite code $q$. At every stage $s \ge \max(r,q)$, the inspection includes that proof and verifies each of its lines, so the code of $\theta$ is eventually listed. Conversely, every listed code is the last line of a verified finite proof, so it belongs to $A$. Thus the procedure enumerates exactly the provable formulas. The asymmetry is that failure to see a proof by stage $s$ only says that no proof has appeared among the finitely many candidates checked so far; it does not rule out a longer proof appearing at a later stage. [/example] This example marks a theme of the course: syntactic search procedures are often computably enumerable, while exact decision procedures require additional structure. The next concept explains how one undecidable problem can still be no harder than another. [definition: Turing Reducibility] For sets $A,B \subset \mathbb N$, write $A \le_T B$ if there is an oracle Turing machine which, using membership queries to $B$, computes the characteristic function $\mathbb{1}_A$. [/definition] Turing reducibility is reflexive and transitive, so it compares decision problems up to oracle computation. It is not antisymmetric on actual subsets of $\mathbb N$: two differently coded sets can compute each other even though they are not equal. The obstruction is representational rather than computational: equality of sets is too strict for comparing oracle power. To turn this preorder into objects that can be ordered without duplicate presentations, we first need a precise relation saying that two presentations carry exactly the same computational information. [definition: Turing Equivalent Sets] Sets $A,B \subset \mathbb N$ are Turing equivalent, written $A \equiv_T B$, if $A \le_T B$ and $B \le_T A$. [/definition] Turing equivalence removes coding accidents: two sets may look different while allowing exactly the same computations. If we kept naming individual representatives, every comparison would still depend on a coding choice. The solution is to make the shared computational content itself into the object of study, so that the degree structure orders equivalence classes rather than particular subsets of $\mathbb N$. [definition: Turing Degree] A Turing degree is an equivalence class of subsets of $\mathbb N$ under Turing equivalence. [/definition] A Turing degree records computational power rather than the presentation of a particular set. Two different-looking sets may have the same degree if each computes the other, so degree theory asks which computations are possible from the information in the set, not which coding happened to be chosen. The following example shows the simplest kind of coding change: moving the same membership information into a computable slice of $\mathbb N$. [example: Coding Does Not Change Degree] Let $A \subset \mathbb N$, and let $\langle \cdot,\cdot\rangle:\mathbb N^2 \to \mathbb N$ be a computable pairing function with computable projections $\pi_0,\pi_1:\mathbb N \to \mathbb N$, so that \begin{align*} \pi_0(\langle x,y\rangle)&=x,\\ \pi_1(\langle x,y\rangle)&=y \end{align*} for all $x,y \in \mathbb N$. Define \begin{align*} B=\{\langle n,0\rangle:n\in A\}. \end{align*} We show that $A \equiv_T B$ by giving reductions in both directions. First, $B \le_T A$. On input $m$, compute \begin{align*} x&=\pi_0(m),\\ y&=\pi_1(m). \end{align*} If $y\ne 0$, then $m\notin B$, because every element of $B$ has second coordinate $0$. If $y=0$, ask the oracle for $A$ whether $x\in A$. In that case, \begin{align*} m\in B &\Longleftrightarrow m=\langle n,0\rangle \text{ for some } n\in A\\ &\Longleftrightarrow \pi_0(m)\in A \text{ and } \pi_1(m)=0\\ &\Longleftrightarrow x\in A. \end{align*} Thus the oracle procedure decides membership in $B$ using $A$. Conversely, $A \le_T B$. On input $n$, compute $\langle n,0\rangle$ and ask the oracle for $B$ whether $\langle n,0\rangle\in B$. By the definition of $B$, \begin{align*} n\in A &\Longleftrightarrow \langle n,0\rangle \in \{\langle k,0\rangle:k\in A\}\\ &\Longleftrightarrow \langle n,0\rangle \in B. \end{align*} So $A \le_T B$ and $B \le_T A$, hence $A \equiv_T B$. The set $B$ only moves the same membership information into the computable slice with second coordinate $0$, so the coding change does not change the Turing degree. [/example] This invariance lets us move between codes, sets, and indices without changing the underlying degree. It also explains why the course can use whichever effective coding is convenient, provided the coding and decoding maps are computable. ## Why the Halting Problem Is the First Benchmark Which undecidable problem should serve as the basic unit of non-computable information? [The halting problem](/theorems/1823) supplies the first canonical answer because it captures successful computation itself. It is computably enumerable, since halting can be witnessed by a finite computation history, but it cannot be computable because any proposed decider can be diagonalised against. [definition: The Halting Set] Fix an acceptable enumeration $(\varphi_e)_{e \in \mathbb N}$ of the partial computable functions $\varphi_e: \mathbb N \rightharpoonup \mathbb N$. The halting set is \begin{align*} K = \{e \in \mathbb N : \varphi_e(e) \downarrow\}. \end{align*} [/definition] The diagonal input $e$ is not a technical accident: it is what lets a program use information about its own index. There are two competing facts to separate: halting has finite positive evidence, but any total algorithm claiming to decide all diagonal halting instances can be turned against its own index. This creates the first test for any proposed boundary between effective enumeration and effective decision. If positive halting evidence were enough to decide nonhalting uniformly, then computably enumerable information would collapse to computable information; the diagonal argument shows exactly where that collapse fails. The formal result below isolates that boundary in the smallest possible example: a set that can be listed by waiting for successful computations, but cannot be decided by a uniform yes-or-no procedure. This is the model case for later reductions, where new undecidable problems are compared to $K$ rather than diagonalised from scratch. [quotetheorem:5397] [citeproof:5397] The diagonal input is essential to the limitation. The set $\{e \in \mathbb N : \varphi_e(0) \downarrow\}$ is still undecidable, but its proof of hardness uses a computable translation from arbitrary inputs into programs with fixed input $0$; without some uniform way to feed a program information about its own code, the direct contradiction above has no target. A bounded version, such as the set of pairs $(e,s)$ for which $\varphi_e(e)$ halts within $s$ steps, is computable because the time bound turns the search into a finite check. Thus the theorem is not saying that every halting-shaped question is undecidable; it identifies unbounded self-application as the first source of noncomputable computably enumerable information. [example: Why Dovetailing Matters] Suppose we try to enumerate \begin{align*} K=\{e\in\mathbb N:\varphi_e(e)\downarrow\} \end{align*} by running $\varphi_0(0)$ until it halts, then $\varphi_1(1)$ until it halts, and so on. If $\varphi_0(0)$ diverges, then the procedure never reaches $\varphi_1(1)$, even if $\varphi_1(1)$ halts after one step; therefore this sequential search need not enumerate all of $K$. Dovetailing avoids this blockage. At stage $s$, simulate each computation \begin{align*} \varphi_0(0),\varphi_1(1),\dots,\varphi_s(s) \end{align*} for exactly $s$ steps, and list $e$ if the simulation shows that $\varphi_e(e)$ has halted. If $e\in K$, then $\varphi_e(e)$ halts after some finite number $t$ of steps. At every stage \begin{align*} s\ge \max(e,t), \end{align*} the computation $\varphi_e(e)$ is among the first $s$ computations and is simulated for at least $t$ steps, so the halting is detected and $e$ is listed. Conversely, if $e$ is listed at stage $s$, the stage-$s$ simulation has exhibited a finite halting computation of $\varphi_e(e)$, so $e\in K$. Thus dovetailing enumerates exactly the halting set, while the naive one-at-a-time search can be stopped forever by the first divergent computation. [/example] The halting set also motivates the idea of relative computability. A machine with oracle $K$ can answer many questions about ordinary computations that no ordinary machine can answer; the course asks what lies below, above, and incomparable with this power. ## Reducibility and Degrees as a Geometry Once undecidable sets are allowed as oracles, what kind of mathematical structure do they form? The Turing degrees form a partially ordered structure under reducibility. Computable sets all collapse to the least degree, while $K$ gives the degree usually denoted $\mathbf{0}'$. [definition: Least Degree] The least Turing degree, denoted $\mathbf{0}$, is the degree containing all computable subsets of $\mathbb N$. [/definition] This notation treats computable information as zero additional oracle power, giving the degree structure a base point. Once computable sets have been identified with $\mathbf{0}$, the next question is how to generate stronger degrees in a systematic way. To move upward from a degree in a uniform way, we ask the halting problem again, but now for computations that are allowed to query the original oracle. [definition: Turing Jump] For a set $A \subset \mathbb N$, the Turing jump of $A$ is \begin{align*} A' = \{e \in \mathbb N : \varphi_e^A(e) \downarrow\}, \end{align*} where $(\varphi_e^A)_{e \in \mathbb N}$ is an acceptable enumeration of the partial $A$-computable functions $\varphi_e^A: \mathbb N \rightharpoonup \mathbb N$. [/definition] The jump packages the halting problem relative to $A$. It is always computably enumerable relative to $A$, and it is never computable from $A$. [remark: Jump Strictness Preview] For every oracle $A$, the jump $A'$ computes $A$ but is not computable from $A$. Thus the jump is a genuine increase in Turing degree, not just a change of notation. [/remark] The jump is the main vertical operation on degrees, but the theorem is more precise than the slogan that "$A'$ is harder than $A$." The reduction $A \le_T A'$ depends on the chosen acceptable oracle enumeration being rich enough to contain, uniformly in $n$, a program that asks whether $n \in A$ and then halts exactly in the positive case. The strictness direction depends on using the same oracle $A$ in both the alleged decider and the diagonal construction; if the decider were allowed the stronger oracle $A'$, the conclusion would fail because $A'$ computes itself. The theorem also does not say that every degree above $A$ is a jump, or that the degrees form a linear tower \begin{align*} \mathbf{0} <_T \mathbf{0}' <_T \mathbf{0}'' <_T \cdots . \end{align*} That tower is only one visible spine inside a much wider partial order. For example, later priority constructions produce computably enumerable degrees strictly between $\mathbf{0}$ and $\mathbf{0}'$, so the jump theorem cannot by itself classify the degrees below $\mathbf{0}'$. [example: The First Two Benchmarks] The degree $\mathbf{0}$ consists of the computable sets. For example, evenness is decided by computing the remainder of $n$ modulo $2$; membership in a fixed finite set $F=\{a_0,\dots,a_{k-1}\}$ is decided by checking the finite list \begin{align*} n=a_0,\quad n=a_1,\quad \dots,\quad n=a_{k-1}; \end{align*} and primality is decided by testing the finitely many divisors $d$ with $2\le d\le n-1$. These procedures halt for every input, so all three examples lie in $\mathbf{0}$. Let \begin{align*} H_0=\{e\in\mathbb N:\varphi_e(0)\downarrow\}. \end{align*} We compute its degree by comparing it with \begin{align*} K=\{e\in\mathbb N:\varphi_e(e)\downarrow\}. \end{align*} Given $e$, effectively produce an index $p(e)$ for the program which ignores its input and simulates $\varphi_e(e)$. Then \begin{align*} e\in K &\Longleftrightarrow \varphi_e(e)\downarrow\\ &\Longleftrightarrow \varphi_{p(e)}(0)\downarrow\\ &\Longleftrightarrow p(e)\in H_0. \end{align*} Thus $K\le_T H_0$. Conversely, given $e$, effectively produce an index $q(e)$ for the program which ignores its input and simulates $\varphi_e(0)$. Then \begin{align*} e\in H_0 &\Longleftrightarrow \varphi_e(0)\downarrow\\ &\Longleftrightarrow \varphi_{q(e)}(q(e))\downarrow\\ &\Longleftrightarrow q(e)\in K. \end{align*} Thus $H_0\le_T K$, so $H_0\equiv_T K$. Therefore $K$, $H_0$, and every set Turing equivalent to the ordinary halting problem all have degree $\mathbf{0}'$. [/example] This geometry leads to the central historical question. Emil Post asked whether every noncomputable computably enumerable set must already have the full degree of the halting problem, or whether there are intermediate computably enumerable degrees. [remark: Friedberg-Muchnik Preview] The Friedberg-Muchnik theorem later answers Post's question by constructing a computably enumerable set whose degree lies strictly between the computable degree and the halting-problem degree. [/remark] This preview is not an immediate tool, and its hypotheses mark the boundary of the result. The set $A$ is required to be computably enumerable, so it is built by positive enumeration rather than by an arbitrary oracle definition. Without that restriction, standard basis theorems already produce noncomputable sets below $\mathbf{0}'$: for example, the [low basis theorem](/theorems/5436) gives a noncomputable path $L$ through a suitable infinite computable binary tree with $L' \equiv_T \mathbf{0}'$, and therefore $L <_T \mathbf{0}'$ while $L$ is not computable. Such an $L$ is not obtained by simply enumerating positive information into a c.e. set. Post's question was difficult because the construction must keep the set c.e. while also preventing it from becoming complete. The strict inequalities are also part of the content, not decoration. A computable c.e. set would satisfy $A \equiv_T \varnothing$, so it would not answer Post's question; the halting set $K$ is c.e. but satisfies $K \equiv_T \mathbf{0}'$, so it is the opposite boundary case. The priority proof has to avoid both failures at once: the positive requirements diagonalise against every total computable characteristic-function candidate for $A$, while the negative requirements block every proposed reduction $K \le_T A$. This is why priority arguments are central to the course: they are a method for building sets whose computational power is controlled in incompatible directions. ## What the Course Will Build How do the early definitions lead to the later theory of degrees, jumps, and applications? The course develops in layers. First it fixes robust models of computation and proves the basic machinery: universal machines, acceptable numberings, Gödel coding, the $s$-$m$-$n$ theorem, and normal forms. Then it uses these tools to analyse decidability, computable enumerability, and diagonalisation. [explanation: From Programs To Indices] A recurring move is to replace an effective procedure by an index $e \in \mathbb N$ for a partial computable function $\varphi_e$. This lets questions about programs become subsets of $\mathbb N$, such as $K$, totality sets, index sets of semantic properties, and sets defined by oracle computations. The price is that indices are non-unique: a single function has many programs. The benefit is that uniformity becomes visible, since constructions can transform indices effectively. [/explanation] The $s$-$m$-$n$ theorem is the formal expression of parameter substitution. It says that fixing some inputs to a program can be done effectively at the level of indices, and it is the engine behind many reductions. Although the halting set was introduced using a unary enumeration $(\varphi_e)_{e \in \mathbb N}$, we use the fixed computable pairing and tupling functions to identify programs on $\mathbb N^{m+n}$ with unary programs on codes of tuples. Thus expressions such as $\varphi_e(a,x)$ and $\varphi_{s_{m,n}(e,a)}(x)$ are shorthand for the corresponding unary computations after coding and decoding tuples. [quotetheorem:5398] [citeproof:5398] The theorem is not merely a convenience for writing shorter programs. Its force is uniformity: the same total computable function $s_{m,n}$ transforms all indices and all parameter tuples. If each fixed pair $(e,a)$ only came with the assertion that some specialised index existed, reductions could not compute the target index from the source instance, and the construction would be unusable in many-one reductions, Rice-style arguments, and completeness proofs. For a non-acceptable numbering, or for a presentation of programs where source transformations are not effective, the existence of a specialised program need not provide a computable way to find its index. A concrete failure illustrates the point. Given $e$ and $a$, there is always some program whose behaviour on $x$ matches $\varphi_e(a,x)$, but choosing such a program by an arbitrary non-effective rule may encode outside information into the chosen index. A reduction from $K$ to another index set cannot query that outside information; it must output its target index by a computable map. The $s$-$m$-$n$ theorem supplies exactly that missing map, and its hypotheses therefore depend on an acceptable numbering where program text can be effectively modified. After the basic machinery, the course studies reductions and completeness. [Rice's theorem](/theorems/1835) shows that substantive semantic properties of partial computable functions are undecidable, while many-one and Turing reductions distinguish different strengths of undecidability. [example: A Typical Index-Set Question] Let \begin{align*} \operatorname{TOT}=\{e\in\mathbb N:\varphi_e \text{ is total}\}. \end{align*} This is a semantic index set: membership depends on the partial function computed by program $e$, not on any visible syntactic feature of the program text. We show first why $\operatorname{TOT}$ is not computable. Given $e$, effectively produce an index $p(e)$ for the one-input program \begin{align*} \text{on input }x:\quad \text{simulate }\varphi_e(e);\ \text{if that simulation halts, output }0. \end{align*} For every $x\in\mathbb N$, the behavior of this program is \begin{align*} \varphi_{p(e)}(x)\downarrow &\Longleftrightarrow \varphi_e(e)\downarrow. \end{align*} Hence \begin{align*} e\in K &\Longleftrightarrow \varphi_e(e)\downarrow\\ &\Longleftrightarrow \text{for every }x\in\mathbb N,\ \varphi_{p(e)}(x)\downarrow\\ &\Longleftrightarrow p(e)\in \operatorname{TOT}. \end{align*} So a decider for $\operatorname{TOT}$ would decide $K$ by computing $p(e)$ and asking whether $p(e)\in\operatorname{TOT}$, contradicting the noncomputability of the halting set proved above. Therefore $\operatorname{TOT}$ is not computable. Its quantifier form also shows why it sits beyond a single halting question: \begin{align*} e\in\operatorname{TOT} &\Longleftrightarrow \forall x\in\mathbb N\ \varphi_e(x)\downarrow\\ &\Longleftrightarrow \forall x\in\mathbb N\ \exists t\in\mathbb N\ [\varphi_e(x)\text{ halts within }t\text{ steps}]. \end{align*} The bracketed relation is computable by simulating $\varphi_e(x)$ for exactly $t$ steps, but the outer universal quantifier ranges over all inputs. Thus $\operatorname{TOT}$ asks about the whole computed function, not one finite computation history, which is why later reductions place it higher than the halting set in the arithmetical hierarchy. [/example] This example shifts the focus from a single halting computation to properties of entire partial functions. Such properties usually require quantifying over all inputs, so they naturally sit above the first halting problem in complexity. The middle of the course turns to relative computability and the jump, where the notation $A'$, $\mathbf{0}'$, $\mathbf{0}''$, and higher jumps organises the arithmetical hierarchy and connects definability by quantifiers with oracle computation. [explanation: Quantifiers And Oracles] Existential search over a computable relation produces computably enumerable sets. Alternating quantifiers produce higher arithmetical complexity. Oracle jumps give a computational way to measure this increase: asking a halting question relative to $A$ corresponds to adding one layer of effective search over computations using $A$. [/explanation] The later lectures introduce priority constructions, simple and creative sets, Post's problem, and the fine structure of the c.e. degrees. These topics turn recursion theory from a list of undecidability results into a construction theory. [remark: Terminology] The subject is often called computability theory in modern usage. The phrase recursion theory remains standard in many logic courses, especially when emphasising partial recursive functions, the arithmetical hierarchy, and degree-theoretic structure. [/remark] The final part connects degree theory with reverse mathematics. Instead of asking whether a theorem is true, reverse mathematics asks which set-existence axioms are needed to prove it over a weak base system. Computability enters because models built from Turing ideals can separate principles by controlling which sets exist. ## Recurring Methods Which proof methods should a reader expect to master? The course repeatedly uses a small set of techniques in increasingly delicate forms. This section names them at the start so that later chapters can point back to the same strategic patterns. [definition: Dovetailing] Dovetailing is the method of simulating countably many computations by stages, giving the first $s$ computations $s$ steps of simulation at stage $s$. [/definition] Dovetailing converts countably many finite discoveries into an effective enumeration. Its limitation is equally important: it detects computations that eventually halt, not computations that never halt, and this limitation motivates the diagonal method used to prove that no uniform decider can fill the gap. [definition: Diagonalisation] Diagonalisation is the method of constructing an object whose behaviour at index $e$ disagrees with the behaviour predicted by the $e$th candidate procedure. [/definition] Diagonal arguments prove impossibility results, but they also guide constructions. When many diagonal goals must be met in a single computably enumerable set, we need a language for tracking the individual obligations and their conflicts. [definition: Priority Requirement] A priority requirement is a condition imposed during a construction of a computably enumerable set, ordered together with other requirements so that conflicts are resolved by priority rank. [/definition] Priority arguments are needed when requirements compete. The proof must show not only that the construction acts effectively, but also that the conflict pattern settles enough for every requirement to be met. [example: Shape Of A Requirement] To prove that a constructed c.e. set $A$ is not computable, it is enough to make $A$ disagree with every total computable $\{0,1\}$-valued function. For each $e$, impose the requirement \begin{align*} R_e:\quad \text{if }\varphi_e\text{ is total and }\operatorname{Range}(\varphi_e)\subseteq \{0,1\},\text{ then }\varphi_e\ne \mathbb{1}_A. \end{align*} Indeed, if $A$ were computable, then its characteristic function $\mathbb{1}_A$ would be total computable and $\{0,1\}$-valued, so $\mathbb{1}_A=\varphi_e$ for some index $e$ in the fixed enumeration. Requirement $R_e$ would then give $\varphi_e\ne \mathbb{1}_A$, a contradiction. A requirement $R_e$ is met by choosing a witness $n$ and forcing \begin{align*} \varphi_e(n)\ne \mathbb{1}_A(n). \end{align*} Since \begin{align*} \mathbb{1}_A(n)= \begin{cases} 1,& n\in A,\\ 0,& n\notin A, \end{cases} \end{align*} there are two possible ways to create the disagreement: \begin{align*} \varphi_e(n)=0 \text{ and } n\in A &\Longrightarrow \mathbb{1}_A(n)=1 \Longrightarrow \varphi_e(n)\ne \mathbb{1}_A(n),\\ \varphi_e(n)=1 \text{ and } n\notin A &\Longrightarrow \mathbb{1}_A(n)=0 \Longrightarrow \varphi_e(n)\ne \mathbb{1}_A(n). \end{align*} The first kind of action is permanent once $n$ is enumerated into $A$. The second kind requires restraint: if the construction promises to keep $n$ out of $A$, then later lower-priority actions must not enumerate $n$ into $A$, because doing so would change $\mathbb{1}_A(n)$ from $0$ to $1$ and could destroy the disagreement. Thus a finite-injury construction chooses witnesses and manages restraints so that each successful disagreement eventually remains true. [/example] The example is schematic, but it captures the logic of finite injury. Individual degrees track the power of one oracle, but many applications need to describe an entire universe of sets closed under the computations already available inside it. The obstruction is that arbitrary collections of sets need not be stable under reducibility or under combining two available oracles, so we isolate the collections that are closed under both operations. [definition: Turing Ideal] A Turing ideal is a collection $\mathcal I \subset \mathcal P(\mathbb N)$ such that whenever $B \in \mathcal I$ and $A \le_T B$, then $A \in \mathcal I$, and whenever $A,B \in \mathcal I$, then $A \oplus B \in \mathcal I$, where \begin{align*} \oplus &: \mathcal P(\mathbb N) \times \mathcal P(\mathbb N) \to \mathcal P(\mathbb N),\\ A \oplus B &= \{2n : n \in A\} \cup \{2n+1 : n \in B\}. \end{align*} [/definition] Turing ideals appear when recursion theory meets subsystems of second-order arithmetic. They collect the sets available inside an $\omega$-model and therefore translate computability closure properties into model-theoretic ones. [example: Computable Sets Form A Turing Ideal] Let $\mathcal I$ be the class of computable subsets of $\mathbb N$. We verify the two closure conditions in the definition of a Turing ideal. First suppose $B\in\mathcal I$ and $A\le_T B$. Since $B$ is computable, there is a total computable function $\mathbb{1}_B:\mathbb N\to\{0,1\}$ deciding membership in $B$. Since $A\le_T B$, there is an oracle machine $\Phi^B$ such that, for every $n\in\mathbb N$, \begin{align*} \Phi^B(n)=\mathbb{1}_A(n). \end{align*} Define an ordinary computation on input $n$ by running the same oracle program for $\Phi^B(n)$, but whenever the program asks whether $q\in B$, compute $\mathbb{1}_B(q)$ and return that value as the oracle answer. Each oracle query is answered after finitely many steps because $\mathbb{1}_B$ is total computable. The oracle computation halts for every input because it computes the total characteristic function $\mathbb{1}_A$, so the substituted ordinary computation halts for every input and outputs $\mathbb{1}_A(n)$. Hence $\mathbb{1}_A$ is total computable, and therefore $A\in\mathcal I$. Now suppose $A,B\in\mathcal I$. Let $a$ and $b$ be total computable characteristic functions for $A$ and $B$, respectively: \begin{align*} a(n)&=\mathbb{1}_A(n),\\ b(n)&=\mathbb{1}_B(n). \end{align*} To decide $A\oplus B$, take an input $m$. If $m$ is even, compute $n=m/2$. Then \begin{align*} m\in A\oplus B &\Longleftrightarrow m\in \{2k:k\in A\}\\ &\Longleftrightarrow m=2k \text{ for some } k\in A\\ &\Longleftrightarrow n\in A, \end{align*} so the correct output is $a(n)$. If $m$ is odd, compute $n=(m-1)/2$. Then \begin{align*} m\in A\oplus B &\Longleftrightarrow m\in \{2k+1:k\in B\}\\ &\Longleftrightarrow m=2k+1 \text{ for some } k\in B\\ &\Longleftrightarrow n\in B, \end{align*} so the correct output is $b(n)$. Parity, division by $2$ in the even case, and the map $m\mapsto (m-1)/2$ in the odd case are computable operations on natural numbers, and $a$ and $b$ are total computable. Thus $A\oplus B$ has a total computable characteristic function, so $A\oplus B\in\mathcal I$. Therefore the computable subsets of $\mathbb N$ form a Turing ideal. [/example] This last example indicates why degree theory is not isolated from logic. The same reducibility relation that orders decision problems also describes closure conditions for models, which is why the course ends by relating recursion theory to reverse mathematics. The closing perspective on degree theory shows that computability is already tied to logical structure, not just to isolated decision problems. Chapter 1 begins by fixing the notion of effective procedure in concrete terms, so that the abstract reducibility ideas from the introduction can be developed on a precise computational foundation. # 1. Computable Functions and Effective Procedures This opening chapter fixes the meaning of effective procedure for the rest of the course. We assume only the usual background in functions on $\mathbb N$, elementary set notation, and finite strings; no prior exposure to logic or automata theory is needed. We begin with concrete machine models, extract the class of partial computable functions, and then replace machines by indices so that programs themselves become mathematical objects. The chapter ends with the universal machine and the $s$-$m$-$n$ theorem, which are the basic tools for Chapter 2's diagonal arguments, Chapter 3's reductions, and Chapter 4's study of Turing degrees. ## Machines and Partial Computable Functions The first problem is to make the informal phrase "there is an algorithm" precise enough that it can support proofs. A computation may fail to halt, so the correct initial object is not a total function but a partial function whose value is defined exactly when the procedure eventually stops with an output. [definition: Partial Function] Let $A$ and $B$ be sets. A partial function from $A$ to $B$ is a function $f: D \to B$ for some subset $D \subset A$. The domain of convergence is denoted $\operatorname{dom}(f)=D$. [/definition] We write $f(a)\downarrow$ when $a \in \operatorname{dom}(f)$ and $f(a)\uparrow$ otherwise. With partiality in place, the next task is to specify which partial functions arise from a finite mechanical procedure, and Turing machines give the reference formalism for that specification. [definition: Turing Computable Partial Function] A partial function $f: \mathbb N^k \rightharpoonup \mathbb N$ is Turing computable if there is a Turing machine $M$ such that, on input $(x_1,\dots,x_k) \in \mathbb N^k$, the machine halts with output $f(x_1,\dots,x_k)$ exactly when $f(x_1,\dots,x_k)\downarrow$, and otherwise never halts. [/definition] This definition separates the external function from the internal run of the machine. A total computable function is a partial computable function whose domain of convergence is all of $\mathbb N^k$. [example: Successor Function] The successor function $S:\mathbb N\to\mathbb N$ defined by $S(n)=n+1$ is Turing computable. In unary notation, represent $n$ by the block $1^n$ of $n$ marks. A Turing machine starts at the left end of the block, repeatedly moves one square to the right while it sees a mark, and stops at the first blank square. At that square it writes one mark and halts, so the tape changes from \begin{align*} 1^n\blank \end{align*} to \begin{align*} 1^n1=1^{n+1}. \end{align*} Thus the output block has exactly one more mark than the input block, so it represents $n+1$. In binary notation, the same function is computed by the finite carry procedure. Starting at the rightmost digit, the machine changes each trailing $1$ to $0$ while carrying $1$ leftward; when it first sees a $0$, it changes that $0$ to $1$ and halts. For an input whose binary expansion is the all-one word $11\cdots 1$ of length $r$, the machine changes all $r$ digits to $0$ and writes a new leading $1$, producing $100\cdots 0$. Algebraically, \begin{align*} 11\cdots 1_2&=2^r-1,\\ (2^r-1)+1&=2^r,\\ 100\cdots 0_2&=2^r. \end{align*} If the rightmost non-trailing digit is $0$, write the input as $u0\underbrace{11\cdots 1}_{r\text{ ones}}$ for some binary prefix $u$. The value of the suffix is \begin{align*} 0\underbrace{11\cdots 1}_{r\text{ ones}}{}_2 &=2^r-1, \end{align*} and after adding $1$ it becomes \begin{align*} (2^r-1)+1&=2^r =1\underbrace{00\cdots 0}_{r\text{ zeros}}{}_2. \end{align*} So the output is $u1\underbrace{00\cdots 0}_{r\text{ zeros}}$, which represents exactly one more than the input. The unary and binary machines use different tape-level routines, but both compute the same mathematical function $n\mapsto n+1$. [/example] The example shows a direct machine construction, but a theory built from bespoke machines would be cumbersome. The next question is whether this class depends on the chosen formalism. If two models of computation produced different classes of functions, every later theorem would have to specify which model it means, and diagonal arguments could become artifacts of a chosen syntax. The course uses Turing machines as the reference model, but register machines, lambda-definable functions, and partial recursive functions all produce the same class. The equivalence theorem below removes that robustness obstruction: it says that the finitary models used in ordinary computability theory define one machine-independent notion of partial computable function. [remark: Quoted result: Equivalence of Standard Models of Computation] For partial functions $f: \mathbb N^k \rightharpoonup \mathbb N$, the following conditions are equivalent: 1. $f$ is Turing computable. 2. $f$ is computable by a finite-register machine whose instructions are increment, decrement-with-branch, copy, and halt instructions over registers storing natural numbers. 3. $f$ is lambda-definable in the standard untyped lambda calculus after representing natural numbers by Church numerals. 4. $f$ is partial recursive. [/remark] The theorem allows the rest of the course to speak about partial computable functions without repeatedly naming the machine model. Its standardness hypotheses matter: the simulations rely on finite descriptions, discrete configurations, and effectively checkable transition rules. If we allowed an arbitrary external oracle as a "machine instruction", or permitted a real number with non-computable binary expansion to be built into the model, the resulting procedures could decide sets that no Turing machine decides. The theorem therefore identifies robust finitary models of computation, not every imaginable physical or infinitary process. It also creates the need for a syntax-free way to build computable functions inside proofs, since later arguments will combine, iterate, and search through functions without drawing a new machine each time. [definition: Partial Recursive Function] The class of partial recursive functions is the least class of partial functions $\mathbb N^k \rightharpoonup \mathbb N$, for all $k \ge 1$, containing the zero, successor, and projection functions and closed under composition, primitive recursion, and unbounded minimisation. [/definition] Unbounded minimisation is the source of partiality: a search may never find a witness. This operation is also the bridge from bounded finite computation to open-ended computation. [example: Least Zero Search] Let $g:\mathbb N^2\to\mathbb N$ be total computable, and define \begin{align*} f(x)=\mu y\,[g(x,y)=0], \end{align*} meaning that $f(x)$ is the least $y$ with $g(x,y)=0$, if such a $y$ exists, and is undefined otherwise. We show that $f$ is partial computable by describing a machine for it. On input $x$, the machine keeps a counter $y$, initially $0$. At stage $y$, it computes the total value $g(x,y)$. If $g(x,y)=0$, it outputs $y$ and halts. If $g(x,y)\ne 0$, it replaces $y$ by $y+1$ and repeats. Thus the successive tests are exactly \begin{align*} g(x,0),\quad g(x,1),\quad g(x,2),\quad \dots . \end{align*} If there is a least $y_0$ such that $g(x,y_0)=0$, then for every $z<y_0$ we have $g(x,z)\ne 0$, so the machine rejects stages $0,1,\dots,y_0-1$, reaches stage $y_0$, sees $g(x,y_0)=0$, outputs $y_0$, and halts. Hence in this case \begin{align*} f(x)=y_0. \end{align*} If no $y$ satisfies $g(x,y)=0$, then every stage has $g(x,y)\ne 0$, so the counter is increased forever and the machine never reaches a halting instruction. Therefore the machine halts exactly on the inputs where the least zero exists, and on those inputs it outputs that least zero. [/example] ## Church-Turing Thesis and Coding Programs Once several precise models agree, the remaining question is philosophical rather than formal: why identify this common class with the informal notion of effective calculability? The Church-Turing thesis answers this as a methodological principle, not as a theorem inside mathematics. [remark: Church-Turing Thesis] The Church-Turing thesis says that every effectively calculable partial function on the natural numbers is computable by a Turing machine. It is not a theorem because "effectively calculable" is an informal pre-mathematical notion, while "Turing computable" is a formal definition. [/remark] The thesis is used in two directions. It licenses machine-independent language in proofs, and it warns us that a proposed stronger model of algorithmic calculation should be checked against the same informal constraints of finite description, discrete steps, and mechanical execution. To reason about all programs at once, programs must be coded by natural numbers. This requires a reliable way to encode finite tuples and finite strings. [definition: Pairing Function] A pairing function is a total computable bijection $\langle \cdot, \cdot \rangle: \mathbb N^2 \to \mathbb N$ whose coordinate projection functions are total computable. [/definition] Pairing functions turn multi-input computation into one-input computation and let finite syntax be stored arithmetically. The exact formula is not canonical; what matters is computable coding and computable decoding. [example: Cantor Pairing Function] Define \begin{align*} T_s=\frac{s(s+1)}{2} \end{align*} and set \begin{align*} \langle x,y\rangle=T_{x+y}+y =\frac{(x+y)(x+y+1)}{2}+y. \end{align*} We show that this gives a computable bijection $\mathbb N^2\to\mathbb N$ with computable coordinate projections. If $s=x+y$, then $0\le y\le s$, so \begin{align*} T_s &\le T_s+y\\ &\le T_s+s\\ &=\frac{s(s+1)}{2}+s\\ &=\frac{s(s+1)+2s}{2}\\ &=\frac{s^2+3s}{2}\\ &=\frac{(s+1)(s+2)}{2}-1\\ &=T_{s+1}-1. \end{align*} Thus every pair with $x+y=s$ is sent into the interval \begin{align*} T_s\le n<T_{s+1}. \end{align*} Within that interval the value is $T_s+y$, and as $y$ runs through $0,1,\dots,s$, the outputs are exactly \begin{align*} T_s,\ T_s+1,\ \dots,\ T_s+s=T_{s+1}-1. \end{align*} Now let $n\in\mathbb N$. To decode $n$, search through $s=0,1,\dots,n$ until finding the unique $s$ such that \begin{align*} T_s\le n<T_{s+1}. \end{align*} Such an $s$ exists because $T_0=0\le n$ and \begin{align*} T_{n+1} =\frac{(n+1)(n+2)}{2} >n. \end{align*} It is unique because the intervals $[T_s,T_{s+1})$ are consecutive: $T_{s+1}$ is the right endpoint of the $s$th interval and the left endpoint of the next one. Once this $s$ is found, define \begin{align*} y&=n-T_s,\\ x&=s-y. \end{align*} The inequalities $T_s\le n<T_{s+1}$ give \begin{align*} 0\le y &=n-T_s\\ &<T_{s+1}-T_s\\ &=\frac{(s+1)(s+2)}{2}-\frac{s(s+1)}{2}\\ &=\frac{(s+1)((s+2)-s)}{2}\\ &=s+1, \end{align*} so $0\le y\le s$ and hence $x=s-y\in\mathbb N$. Finally, \begin{align*} \langle x,y\rangle &=T_{x+y}+y\\ &=T_{(s-y)+y}+y\\ &=T_s+y\\ &=T_s+(n-T_s)\\ &=n. \end{align*} Therefore every $n$ has exactly one decoded pair $(x,y)$, and encoding that pair returns $n$. The encoding is computable because it uses addition, multiplication, division by $2$ of the product of consecutive integers, and addition of $y$. The projections are computable because the decoder performs the bounded search $s=0,\dots,n$, then computes $y=n-T_s$ and $x=s-y$. Thus the formula is a total computable bijection with total computable coordinate projections. [/example] The pairing example handles tuples of numbers; the next coding problem is program syntax itself. We need a Gödel coding so that statements about well-formed instructions, input arity, and program simulation become computable predicates on natural numbers. [definition: Effective Gödel Coding of Programs] An effective Gödel coding of programs is an injective map from finite program descriptions into $\mathbb N$ such that the syntactic relations needed to recognise well-formed programs, instructions, variables, input arities, initial configurations, halting configurations, and single-step transitions are computable from the code. [/definition] The coding is not part of the mathematical content of computability; it is bookkeeping that lets syntax enter arithmetic. Starting from such a concrete coding of machines, the associated enumeration of partial functions has extra effective structure: programs can be recognised by arity, simulated step by step, and modified by a mechanical transformation of their texts. The next definition abstracts exactly that structure. It is stronger than being a surjective list of all partial computable functions, because an arbitrary list may contain every function while giving no computable way to interpret an index as executable syntax. [definition: Acceptable Numbering] An acceptable numbering of the unary partial computable functions is a sequence $(\varphi_e)_{e \in \mathbb N}$ such that every unary partial computable function occurs as some $\varphi_e$, there is a partial computable universal evaluator $U_1: \mathbb N^2 \rightharpoonup \mathbb N$ satisfying $U_1(e,x) \simeq \varphi_e(x)$ for all $e,x \in \mathbb N$, and the numbering satisfies the parameter property expressed by total computable functions $s_{m,n}: \mathbb N^{m+1} \to \mathbb N$ for all $m,n \ge 1$. [/definition] For each arity $k \ge 1$, we fix an associated acceptable numbering $(\varphi_{e,k})_{e \in \mathbb N}$ of the $k$-ary partial computable functions $\mathbb N^k \rightharpoonup \mathbb N$. The unary notation $\varphi_e$ means $\varphi_{e,1}$. The acceptability conditions prevent pathological enumerations that list the right functions but destroy the effective structure of programs. In an acceptable numbering, an index behaves like a genuine program code rather than a mere name. For numberings obtained from an effective Gödel coding of Turing machines, acceptability is a theorem about the coding; once the course has abstracted to acceptable numberings, universality and parameterisation become the structural properties that are carried forward. ## Universal Computation and Parameters The next problem is to turn the informal statement "run program $e$ on input $x$" into a single computable operation. Universality says that there is one machine capable of simulating all machines once it is given the simulated machine's code. [quotetheorem:5399] [citeproof:5399] Universality is the formal basis for diagonalisation: the input can include the code of the very program being analysed. The theorem uses three concrete hypotheses supplied by the Gödel coding: program syntax is effectively recognisable, the arity of a program can be computed from its code, and each coded transition can be simulated by a computable operation on coded configurations. It does not say that every listing of partial computable functions has a computable evaluator; an arbitrary permutation of the indices can hide non-computable information in the numbering and destroy effective simulation. The validity check in the proof is also essential, because a universal machine must respond uniformly to both genuine program codes and malformed codes rather than relying on informal syntax outside arithmetic. Without effective coding, the expression "run program $e$" would be a meta-level instruction rather than a partial computable function. Before diagonal arguments appear, we need a second structural result saying that parameters can be compiled into indices. [quotetheorem:5398] [citeproof:5398] The theorem is often read as a formal currying principle for programs. It does not merely assert that a specialised procedure exists; it says that an index for that procedure can be obtained effectively from the original index and the parameter values. This effectiveness is stronger than extensional closure under substitution: knowing that each fixed $a$ gives some computable unary function $x \mapsto \varphi_{e,2}(a,x)$ would not tell us how to find its program. For example, if a numbering were scrambled by a non-computable permutation, the specialised function would still occur somewhere in the list, but there need not be a computable way to locate an index for it. The $s$-$m$-$n$ theorem rules out that defect for acceptable numberings, and this is why it supports later self-reference arguments rather than only ordinary function composition. The self-reference principle used later is the recursion theorem. In an acceptable numbering, every total computable index-transformer has a fixed point up to program equivalence: if $f:\mathbb N\to\mathbb N$ is total computable, then there is an index $e$ such that \begin{align*} \varphi_e \simeq \varphi_{f(e)}. \end{align*} The parameterized form says more generally that if a computable construction takes a parameter $a$ and a prospective self-index, then one can choose an index $e(a)$ effectively in $a$ so that the resulting program has access to its own chosen index. This is the formal tool behind productive-set and fixed-point arguments below; it is not a new machine model, but a consequence of universality together with the $s$-$m$-$n$ theorem. [example: Fixing One Parameter] Suppose $e$ is an index for the binary partial computable function $(a,x)\mapsto \varphi_{e,2}(a,x)$, and fix $a\in\mathbb N$. Applying the *[S-M-N Theorem](/theorems/5398)* with $m=1$ and $n=1$ gives a total computable function $s_{1,1}$ such that, for every $x\in\mathbb N$, \begin{align*} \varphi_{s_{1,1}(e,a),1}(x) &\simeq \varphi_{e,2}(a,x). \end{align*} Thus the single number $s_{1,1}(e,a)$ is an index for the unary partial function obtained by holding the first input fixed at $a$. Operationally, the specialised program with index $s_{1,1}(e,a)$ behaves as follows on input $x$: it writes the stored parameter $a$ into the first input position, writes the actual input $x$ into the second input position, and then runs the program coded by $e$ on the pair $(a,x)$. Therefore, if \begin{align*} \varphi_{e,2}(a,x)\downarrow = y, \end{align*} then the specialised program follows the same simulated run and halts with \begin{align*} \varphi_{s_{1,1}(e,a),1}(x)=y. \end{align*} If instead \begin{align*} \varphi_{e,2}(a,x)\uparrow, \end{align*} then after writing $a$ and $x$ the specialised program enters the same non-halting computation, so \begin{align*} \varphi_{s_{1,1}(e,a),1}(x)\uparrow. \end{align*} The point is not only that the specialised unary function exists, but that its index is obtained effectively from the original index $e$ and the fixed parameter $a$. [/example] The example illustrates program specialisation, while later enumerability arguments require a different view of computation: a halting computation should be recognisable from a finite certificate. This motivates Kleene normal form, which separates bounded verification of a computation history from the unbounded search for such a history. [quotetheorem:5400] [citeproof:5400] Kleene normal form packages computation into two parts: primitive recursive verification and unbounded search. The theorem does not make halting decidable, because it gives a bounded check for a proposed history $t$, not a computable bound on how far to search for such a history. A concrete obstruction is a non-halting program: every finite candidate history can be rejected by $T_k$, but no finite rejection proves that all later candidates fail. Thus the theorem explains why successful computations have finite certificates while unsuccessful searches may not. This distinction reappears in the study of computably enumerable sets, where membership is witnessed by a finite successful computation but absence may have no finite certificate. [remark: Indices Are Not Unique] A partial computable function has infinitely many indices in any standard programming formalism: add unused states, insert redundant computations before the real work, or choose a different but equivalent program structure. Recursion theory studies both extensional objects, such as the function $\varphi_e$, and intensional data, such as the particular index $e$. [/remark] This chapter leaves us with countable effective lists $(\varphi_{e,k})_{e \in \mathbb N}$ of all $k$-ary partial computable functions, universal evaluators for those lists, and an effective method for specialising programs by fixing parameters. These tools are enough to begin the central arguments of the course: recognising sets by halting computations, proving that some computations cannot be decided uniformly, and using diagonalisation to create functions and sets outside any proposed computable boundary. With effective procedures in hand, the course can now focus on sets of natural numbers and the difference between deciding membership and merely recognizing it. The next chapter uses this distinction to study decidability, enumerability, and diagonal arguments as the first tools for proving that some problems lie beyond any uniform algorithm. # 2. Decidability, Enumerability, and Diagonalization This chapter turns the effective procedures from the first chapter into a theory of sets of natural numbers. The guiding question is how much information is obtained when a procedure can eventually confirm membership, but may never confirm non-membership. This distinction between deciding and recognizing is the first source of incomputability, and diagonalization supplies the basic method for proving that certain effective-looking tasks cannot be computable. ## Decidable and Computably Enumerable Sets When a set $A \subseteq \mathbb N$ represents a decision problem, the strongest effective requirement is that there is an algorithm which always halts and gives the correct yes-or-no answer. Many natural procedures are weaker: they halt when the answer is yes, but may run forever when the answer is no. The first definitions separate these two behaviours. [definition: Indicator Function] Let $A \subseteq \mathbb N$. The indicator function of $A$ is the total function $\mathbb{1}_A: \mathbb N \to \{0,1\}$ given by \begin{align*} \mathbb{1}_A(n) = \begin{cases} 1, & n \in A,\\ 0, & n \notin A. \end{cases} \end{align*} [/definition] The indicator function packages a set as a total computational problem: on input $n$, output the truth value of $n \in A$. This gives the right language for decision problems where both positive and negative answers must be produced. The next definition names exactly those sets whose indicator functions can be computed. [definition: Computable Set] A set $A \subseteq \mathbb N$ is computable, or decidable, if its indicator function $\mathbb{1}_A: \mathbb N \to \{0,1\}$ is computable. [/definition] A computable set is one for which membership and non-membership are both effectively settled. The problem is that many procedures encountered in practice have only a positive stopping condition: they can verify a witness when it appears, but they have no finite signal that no witness exists. This raises the question of how to name sets whose members can be effectively listed or recognized even when non-members are not decidable. [definition: Computably Enumerable Set] A set $A \subseteq \mathbb N$ is computably enumerable, abbreviated c.e., if there is a partial computable function $\varphi: \mathbb N \rightharpoonup \mathbb N$ such that \begin{align*} A = \operatorname{Range}(\varphi). \end{align*} [/definition] This definition says that the elements of $A$ can be printed, perhaps with repetitions and with gaps in the computation. For proofs it is often more convenient to recognize membership than to list outputs, or to express membership by a finite computable witness. The following theorem records these interchangeable forms, so later arguments can choose whichever representation fits the construction. [quotetheorem:5401] [citeproof:5401] The equivalence also does not turn c.e. information into decidable information, because the existential witness relation only certifies membership when a witness is found. If no such $s$ has appeared by a finite stage, that finite failure gives no certificate that no witness exists. For instance, the later halting set $K$ has finite witnesses for membership but no computable supply of finite witnesses for non-membership. To obtain a decision procedure one needs a second effective source of negative information, which motivates the complement condition in the next theorem. Using the dovetailing method introduced in Chapter 0 and formalised in Chapter 1, the next example makes the enumeration viewpoint concrete. [example: Range of a Partial Computable Function] Let $\varphi: \mathbb N \rightharpoonup \mathbb N$ be partial computable. We enumerate $\operatorname{Range}(\varphi)$ by dovetailing its computations: at stage $s$, run the first $s$ steps of each computation \begin{align*} \varphi(0),\varphi(1),\dots,\varphi(s), \end{align*} and print every value whose computation is seen to halt at that stage. If $y \in \operatorname{Range}(\varphi)$, then there is some $e \in \mathbb N$ such that $\varphi(e)=y$. Since $\varphi(e)$ is defined, its computation halts after some finite number $t$ of steps. Choose a stage $s$ with \begin{align*} s \ge e \qquad\text{and}\qquad s \ge t. \end{align*} At stage $s$, the computation $\varphi(e)$ is among the computations being simulated, because $e \le s$, and it has been run for at least $t$ steps, so its halt with output $y$ is detected and $y$ is printed. Conversely, suppose a number $y$ is printed at some stage $s$. Then the procedure printed $y$ only because, for some input $e \le s$, the finite simulation of $\varphi(e)$ halted with output $y$. Therefore $\varphi(e)=y$, so \begin{align*} y \in \operatorname{Range}(\varphi). \end{align*} Thus every value in the range is eventually printed, and every printed value belongs to the range; repetitions may occur, but they do not change the enumerated set. [/example] The example shows why c.e. information is positive information: seeing a value is conclusive, while not having seen it yet proves nothing. To compare recognition with decision, we must also ask whether the negative instances can be recognized by the same kind of finite evidence. The next definition names this complementary semidecision property. [definition: Co-Computably Enumerable Set] A set $A \subseteq \mathbb N$ is co-computably enumerable, abbreviated co-c.e., if $\mathbb N \setminus A$ is c.e. [/definition] A co-c.e. set has effective evidence for non-membership in its complement, but that alone still does not decide membership in the original set. The decisive situation is when both sides have semidecision procedures. The following theorem is the first structural bridge between recognizing and deciding. [quotetheorem:5402] [citeproof:5402] This theorem is the formal version of the slogan that a decision procedure is a pair of semidecision procedures, one for yes and one for no. Both hypotheses in the reverse direction are necessary: a recognizer for $A$ alone gives no reliable stopping point when $n \notin A$, and a recognizer for the complement alone gives no reliable stopping point when $n \in A$. The halting set $K$ later supplies the standard counterexample, since $K$ is c.e. but not computable, so its c.e.-ness by itself cannot be upgraded into a decision procedure. The theorem also gives a standard way to prove noncomputability: show that a set is c.e., then show its complement is not c.e., or use diagonalization to rule out a total decider. ## The Halting Problem and Diagonalization The universal machine from the previous chapter lets us ask whether a program halts on its own index. This is the first canonical undecidable set, and it captures the failure of a uniform algorithm for predicting arbitrary computations. The diagonal argument shows that any proposed halting decider can be forced to disagree with itself. [definition: Halting Set] Fix an acceptable enumeration $(\varphi_e)_{e \in \mathbb N}$ of the partial computable functions $\mathbb N \rightharpoonup \mathbb N$. The halting set is \begin{align*} K = \{e \in \mathbb N : \varphi_e(e)\downarrow\}. \end{align*} [/definition] Here $\varphi_e(e)\downarrow$ means that the computation halts, without specifying its output. Before proving that $K$ cannot be decided, we separate the positive part of the problem: actual halting is witnessed by a finite computation. The next theorem records that this finite witness makes $K$ c.e. The theorem below uses the standard notation \begin{align*} \mathbb K_0&=\{(e,x)\in\mathbb N^2:\varphi_e(x)\downarrow\},\\ \mathbb K&=\{e\in\mathbb N:\varphi_e(e)\downarrow\}. \end{align*} Thus the diagonal halting set already denoted by $K$ in these notes is the same set as $\mathbb K$. [quotetheorem:1822] [citeproof:1822] Recognizability of $K$ is not the same as decidability. The theorem uses the finite nature of halting computations: a completed computation is a certificate that can be checked by universal simulation. Both pieces are necessary. If we replace the certificate "the simulation has halted by stage $s$" with "the simulation has not halted by stage $s$," the proposed negative certificate fails: for every fixed stage $s$ there are programs that wait $s+1$ steps and then halt, so finite waiting never certifies non-halting. The universal simulation hypothesis is also essential. The proof assumes an acceptable enumeration in which there is an effective machine that, given $(e,x)$, simulates $\varphi_e(x)$. Without that effectivity, an arbitrary listing of partial functions could hide non-c.e. information in its indices. For example, if $B \subseteq \mathbb N$ is not c.e. and a non-effective list assigns $\psi_e$ to be the constant zero function when $e \in B$ and the nowhere-defined function when $e \notin B$, then the corresponding self-halting set is exactly $B$. Such a list is not an acceptable computable numbering, and this is why the theorem is about the standard effective enumeration of programs rather than an arbitrary catalogue of partial functions. Thus the result proves only positive enumerability of $K$, and the missing negative information is exactly what the next diagonal argument rules out uniformly. [quotetheorem:5403] [citeproof:5403] This is the prototype of diagonalization in recursion theory. The proof depends on totality of the assumed decider: the construction of $g(e)$ must receive a definite answer before choosing whether to halt or diverge. A mere recognizer for $K$ would not suffice, because waiting for the recognizer to fail to halt would not be an effective instruction. This is not a cosmetic restriction: the previous theorem gives exactly such a recognizer for $K$, and no contradiction follows from it because the recognizer supplies only the positive branch of the case distinction. The acceptable-numbering hypothesis is also needed. The constructed partial computable function $g$ must appear somewhere as $\varphi_d$ so that the proof can ask about its behaviour on its own index. If a list omits the functions produced by the construction, diagonalization only builds a function outside that list. For instance, a list containing only total constant functions has a decidable self-halting set, but it is not a numbering of all partial computable functions. The theorem therefore rules out a total computable halting decider for a universal effective list of programs; it does not say that every restricted programming language has an undecidable halting problem. This same pattern reappears whenever a proposed uniform solver can be fed its own description or used to construct a program whose behaviour opposes the solver's prediction. [example: A c.e. Set Which is Not co-c.e.] By *The Halting Set is Computably Enumerable*, the halting set $K$ is c.e. We show that $K$ is not co-c.e. Suppose, toward a contradiction, that $K$ were co-c.e. By the definition of co-c.e., this means that \begin{align*} \mathbb N \setminus K \end{align*} is c.e. Hence both $K$ and $\mathbb N \setminus K$ are c.e. Applying *Decidable iff c.e. and co-c.e.* with $A=K$, it follows that $K$ is computable. This contradicts *The Halting Set is Not Computable*. Therefore $K$ is not co-c.e. Thus $K$ is c.e. but not co-c.e.; equivalently, halting has finite positive evidence, while non-halting has no computably enumerable supply of finite certificates. [/example] The example gives the first genuine separation between c.e. and computable sets. The next problem is broader: many undecidable questions are not literally asking whether a program halts on its own code, but whether the function computed by a program has some semantic property. To state this general principle, we first isolate properties that depend only on the computed partial function and not on the chosen index. [definition: Index Set] A set $A \subseteq \mathbb N$ is an index set if, whenever $\varphi_e = \varphi_f$ as partial functions, one has \begin{align*} e \in A \iff f \in A. \end{align*} [/definition] Index sets ignore the syntactic form of a program and depend only on the partial computable function it computes. The problem is whether any nonconstant semantic program property can be decided from an index. Rice's theorem answers this question in the negative and turns the halting problem into a general undecidability principle. Rice's theorem says that if $\mathcal C$ is a nonempty proper class of partial computable functions and membership in $\mathcal C$ depends only on the partial function computed, then the index set \begin{align*} A_{\mathcal C}=\{e\in\mathbb N:\varphi_e\in\mathcal C\} \end{align*} is not computable. The theorem is powerful because it converts many undecidability arguments into a check that the property depends only on computed behaviour and is neither always true nor always false. Both restrictions matter. If $\mathcal C$ is empty or contains every partial computable function, then $A_{\mathcal C}$ is respectively $\varnothing$ or $\mathbb N$, and those sets are computable. If a property is not extensional, such as whether a program has fewer than one hundred symbols, Rice's theorem does not apply because two different programs can compute the same partial function while having different syntactic forms. The next examples show how totality and infinitude fit the theorem's semantic, nonconstant pattern, and later reductions use this viewpoint to separate properties that are undecidable from properties that are merely hard to enumerate. [example: Noncomputability of TOT] Let \begin{align*} \operatorname{TOT}=\{e \in \mathbb N : \varphi_e \text{ is total}\}. \end{align*} We verify that this is a nontrivial semantic property of the computed partial function, so *Rice's Theorem* applies. First, $\operatorname{TOT}$ is an index set. If $\varphi_e=\varphi_f$ as partial functions, then they have the same domain. Hence \begin{align*} e \in \operatorname{TOT} &\iff \varphi_e \text{ is total} \\ &\iff \operatorname{dom}(\varphi_e)=\mathbb N \\ &\iff \operatorname{dom}(\varphi_f)=\mathbb N \\ &\iff \varphi_f \text{ is total} \\ &\iff f \in \operatorname{TOT}. \end{align*} Thus membership in $\operatorname{TOT}$ depends only on the partial function computed, not on the particular index. The property is not empty: if $\varphi_c(n)=0$ for every $n \in \mathbb N$, then $\operatorname{dom}(\varphi_c)=\mathbb N$, so $c \in \operatorname{TOT}$. The property is not universal: if $\varphi_d$ is the nowhere-defined partial function, then \begin{align*} \operatorname{dom}(\varphi_d)=\varnothing \ne \mathbb N, \end{align*} so $d \notin \operatorname{TOT}$. Therefore $\operatorname{TOT}$ is a nonempty, nonuniversal index set, and *Rice's Theorem* implies that $\operatorname{TOT}$ is not computable. This shows that there is no algorithm which, given an arbitrary program index, always halts and correctly decides whether that program halts on every input. [/example] Totality asks whether the domain is all of $\mathbb N$. A different semantic property asks whether the domain is infinite, and it is also neither always true nor always false. [example: Noncomputability of INF] Let \begin{align*} \operatorname{INF}=\{e \in \mathbb N : \operatorname{dom}(\varphi_e) \text{ is infinite}\}. \end{align*} We verify that this is a nontrivial semantic property of the partial function computed by an index. If $\varphi_e=\varphi_f$ as partial functions, then their domains are equal: \begin{align*} \operatorname{dom}(\varphi_e)=\operatorname{dom}(\varphi_f). \end{align*} Therefore \begin{align*} e \in \operatorname{INF} &\iff \operatorname{dom}(\varphi_e) \text{ is infinite} \\ &\iff \operatorname{dom}(\varphi_f) \text{ is infinite} \\ &\iff f \in \operatorname{INF}. \end{align*} So membership in $\operatorname{INF}$ depends only on the computed partial function, not on the chosen program index. The property is nonempty: let $c$ be an index for the identity function $\varphi_c(n)=n$. This function is defined for every $n \in \mathbb N$, so \begin{align*} \operatorname{dom}(\varphi_c)=\mathbb N. \end{align*} Since $\mathbb N$ is infinite, $c \in \operatorname{INF}$. The property is not universal: let $d$ be an index for the nowhere-defined partial function. Then \begin{align*} \operatorname{dom}(\varphi_d)=\varnothing, \end{align*} and $\varnothing$ is finite, so $d \notin \operatorname{INF}$. Thus $\operatorname{INF}$ is a nonempty, nonuniversal index set, and *Rice's Theorem* implies that $\operatorname{INF}$ is not computable. This shows that no algorithm can always decide, from a program index, whether that program halts on infinitely many inputs. [/example] Rice's theorem is not saying that every question about programs is undecidable. Syntactic properties such as the number of symbols in a program may be computable because they are not invariant under equality of partial functions. The theorem applies to extensional properties of computed functions. ## Enumeration Operators and Dovetailing The preceding arguments repeatedly used the same operational idea: simulate many computations in stages and record every finite success. This is the basis for enumeration operators and for the practical distinction between recognizing and deciding. The central question is which transformations preserve positive information when only enumerations, not decision procedures, are available. [definition: Enumeration Procedure] An enumeration procedure for a set $A \subseteq \mathbb N$ is an effective process which prints elements of $A$, possibly with repetitions and in no prescribed order, such that every element of $A$ is eventually printed. [/definition] This definition matches c.e. sets: the printed stream can be coded as the range of a partial computable function, and a partial computable range can be printed by running many computations in stages. The absence of order and the permission for repetition are essential conveniences; forcing a clean increasing list would accidentally build in decidability for infinite sets. We therefore need a named scheduling method that guarantees every finite computation eventually receives attention. [definition: Dovetailing] Dovetailing is the method of organizing a countable family of computations $(C_i)_{i \in \mathbb N}$ into stages so that, for every pair $(i,t)$, the first $t$ steps of computation $C_i$ are eventually performed. [/definition] Dovetailing prevents a single divergent computation from blocking all later searches. It is the mechanism behind universal enumeration, the domain characterization of c.e. sets, and the proof that two opposing recognizers yield a decider. The next example shows the method in the basic case of enumerating the domain of one partial computable function. [example: Recognizing a Domain by Dovetailing] Suppose $A=\operatorname{dom}(\varphi_e)$. Define an enumeration procedure by stages as follows: at stage $s$, simulate the computations \begin{align*} \varphi_e(0),\varphi_e(1),\dots,\varphi_e(s) \end{align*} for $s$ steps each, and print exactly those inputs $m \le s$ whose computation is seen to halt at stage $s$ and has not already been printed at an earlier stage. We show that the set printed by this procedure is exactly $A$. First let $n \in A$. By the definition of domain, \begin{align*} n \in \operatorname{dom}(\varphi_e) \end{align*} means that $\varphi_e(n)$ is defined, so the computation $\varphi_e(n)$ halts after some finite number $t$ of steps. Choose a stage $s$ such that \begin{align*} s \ge n \qquad\text{and}\qquad s \ge t. \end{align*} At stage $s$, the computation $\varphi_e(n)$ is included in the list being simulated because $n \le s$, and it is run for at least $t$ steps because $t \le s$. Therefore the halt of $\varphi_e(n)$ is detected by stage $s$, and the procedure prints $n$. Conversely, suppose $n$ is printed at some stage $s$. Then the procedure printed $n$ only because $n \le s$ and the finite simulation of $\varphi_e(n)$ halted within the $s$ simulated steps. Hence the actual computation $\varphi_e(n)$ halts, so \begin{align*} n \in \operatorname{dom}(\varphi_e)=A. \end{align*} Thus every element of $A$ is eventually printed, and every printed number belongs to $A$; the staged procedure is an enumeration of the domain. [/example] This example shows that c.e. procedures operate by accumulating finite positive facts. The next abstraction asks what operations can be performed when the input set itself is supplied only by such a stream of positive facts. Enumeration operators are designed to use finite positive certificates and no negative information. [definition: Enumeration Operator] An enumeration operator specified by a c.e. set $W \subseteq \mathbb N \times \mathcal P_{\mathrm{fin}}(\mathbb N)$ is the map \begin{align*} \Phi_W: \mathcal P(\mathbb N) &\to \mathcal P(\mathbb N),\\ A &\mapsto \{n \in \mathbb N : \exists F \subseteq A\text{ finite with }(n,F)\in W\}. \end{align*} [/definition] The finite set $F$ is a finite positive certificate: once all elements of $F$ have appeared in an enumeration of $A$, the operator is allowed to enumerate $n$. No negative information about $A$ can be used, because failure to appear at a finite stage never proves absence. The next theorem verifies that these positive transformations preserve c.e.-ness. [quotetheorem:5404] [citeproof:5404] This theorem formalizes why c.e. information is stable under effective positive transformations. The finiteness hypothesis in the certificate is essential: an operator that required checking an infinite subset of $A$ could not be triggered by any finite stage of an enumeration. The c.e. input hypothesis is also necessary. Take the effective instruction set \begin{align*} W=\{(n,\{n\}) : n \in \mathbb N\}. \end{align*} Then $\Phi_W(A)=A$. If the theorem allowed arbitrary, non-c.e. inputs $A$, it would falsely imply that every subset of $\mathbb N$ is c.e. The c.e. hypothesis on $W$ is part of the effectivity condition as well, since the instructions themselves must be discoverable by a computable search. If this is dropped, a non-c.e. set $B$ can be built directly into the instructions by taking \begin{align*} W_B=\{(n,\varnothing) : n \in B\}. \end{align*} For every input $A$, this gives $\Phi_{W_B}(A)=B$, so even the computable input $A=\varnothing$ would be sent to a non-c.e. output. The limitation is equally important: deciding a set requires reliable negative information, which enumeration alone does not provide. Thus enumeration operators behave like continuous maps for positive information, preserving finite evidence while remaining unable to detect permanent absence. [explanation: Recognizing Versus Deciding] A recognizer for $A$ gives a semidecision procedure: if $n \in A$, the computation eventually halts and confirms membership; if $n \notin A$, the computation may run forever. A decider for $A$ is a total procedure that halts on every input and returns the correct truth value. The gap between these two notions is measured by the complement: recognizing $A$ does not provide a recognizer for $\mathbb N \setminus A$, and without that second recognizer there is no effective moment at which waiting can be interpreted as evidence of non-membership. The halting set $K$ is the standard example. Simulation recognizes halting computations, but an unfinished simulation at stage $s$ gives only partial information; it may halt later. Diagonalization proves that no uniform computable method can turn this kind of waiting into a correct negative answer for all programs. [/explanation] A final practical principle follows. Whenever an argument only needs to find finite witnesses, c.e. methods and dovetailing are often enough. Whenever an argument must certify that no witness exists, computability or co-c.e. information is needed, and diagonalization often shows that such information cannot be obtained uniformly. After separating decidability from computable enumerability, the natural next question is how finely undecidable sets can be compared. Chapter 3 answers this by introducing reducibilities that measure how one problem can code another, setting up the comparison framework needed before Turing degrees are defined. # 3. Reducibilities Before Turing Degrees Chapter 2 separated decidability from computable enumerability by diagonal arguments, especially through the halting set $K$. This chapter asks how refined such separations are: if one undecidable set is available as an oracle or as a target of a coding, which other undecidable sets can be solved from it? The prerequisites are the basic theory of partial computable functions, c.e. sets, oracle Turing machines, the s-m-n theorem, and the recursion theorem. Before passing to Turing degrees, we compare several reducibilities that measure different amounts of uniform information transfer. The guiding theme is that a reducibility is not just a technical convenience; it determines which sets count as having the same computational content. ## Coding Decision Problems into One Another Suppose $A,B \subseteq \mathbb N$ are decision problems. The basic question is whether membership in $A$ can be transformed, by a computable preprocessing of inputs, into membership in $B$. This is the many-one viewpoint: a single question about $B$ must answer the original question about $A$. [definition: Many-One Reducibility] Let $A,B \subseteq \mathbb N$. We say that $A$ is many-one reducible to $B$, written $A \le_m B$, if there is a total computable function $f: \mathbb N \to \mathbb N$ such that for every $x \in \mathbb N$, \begin{align*} x \in A \iff f(x) \in B. \end{align*} [/definition] A many-one reduction turns a decision procedure for $B$ into a decision procedure for $A$ by computing $f(x)$ and then asking the single membership question for $B$. The next example shows why this definition is useful: many natural undecidable problems can be encoded by constructing a new program whose halting behaviour records the answer. [example: Acceptance Reduces to Halting] Let $A_{\mathrm{acc}}=\{\langle e,x\rangle:\varphi_e(x)\downarrow \text{ and } \varphi_e(x)=1\}$, and let $K=\{\langle p,y\rangle:\varphi_p(y)\downarrow\}$ be the halting problem in paired form. We compute a many-one reduction by turning the question whether $\varphi_e(x)$ halts with value $1$ into one halting question about a new program. For fixed $e,x$, define a partial computable program $P_{e,x}$ by the following procedure on input $y$: simulate $\varphi_e(x)$; if that simulation halts with value $1$, halt; if it halts with any other value, run forever. Thus, for every $y$, \begin{align*} P_{e,x}(y)\downarrow &\iff \varphi_e(x)\downarrow \text{ and } \varphi_e(x)=1. \end{align*} The construction of $P_{e,x}$ is uniform in the parameters $e$ and $x$, so by the *s-m-n theorem* there is a total computable function $h$ such that $h(\langle e,x\rangle)$ is an index for $P_{e,x}$. Define \begin{align*} f(\langle e,x\rangle)=\langle h(\langle e,x\rangle),0\rangle. \end{align*} Since $h$ is total computable and the pairing function is computable, $f$ is total computable. For every input $\langle e,x\rangle$, \begin{align*} \langle e,x\rangle \in A_{\mathrm{acc}} &\iff \varphi_e(x)\downarrow \text{ and } \varphi_e(x)=1\\ &\iff P_{e,x}(0)\downarrow\\ &\iff \varphi_{h(\langle e,x\rangle)}(0)\downarrow\\ &\iff \langle h(\langle e,x\rangle),0\rangle \in K\\ &\iff f(\langle e,x\rangle)\in K. \end{align*} Therefore $f$ witnesses $A_{\mathrm{acc}}\le_m K$: one computable preprocessing step converts acceptance with output $1$ into a single halting query. [/example] The example illustrates the standard pattern for many-one reductions in recursion theory: build, uniformly from the original instance, a program whose halting behaviour records the answer. The next definition asks for a finer reduction in which the preprocessing map also preserves distinctness of inputs, so that the coding does not merge separate instances. [definition: One-One Reducibility] Let $A,B \subseteq \mathbb N$. We say that $A$ is one-one reducible to $B$, written $A \le_1 B$, if there is a total computable injective function $f: \mathbb N \to \mathbb N$ such that for every $x \in \mathbb N$, \begin{align*} x \in A \iff f(x) \in B. \end{align*} [/definition] One-one reducibility is useful when the construction must preserve enough information about the original instance to be inverted on its range or to support effective isomorphism arguments. Since it has the same membership condition as many-one reducibility plus injectivity, the next theorem records its position in the hierarchy. [quotetheorem:5405] [citeproof:5405] The theorem uses only the computable membership-preserving part of a one-one reduction; injectivity is stronger than the conclusion requires. For example, if $A=\mathbb N$ and $B=\{0\}$, the constant map $x\mapsto 0$ witnesses $A \le_m B$, while no injective map can send every input into the one-element set $B$. Thus this result is not a hypothesis-necessity statement about injectivity. It records a containment of notions: [every one-one reduction is a many-one reduction](/theorems/5405), but some many-one reductions lose information by merging inputs. The other hypotheses still matter: the witness must be total, computable, and membership-preserving, because dropping any of these conditions no longer gives an algorithmic reduction of decision problems. This implication is the first step in the hierarchy of reducibilities, and the next step is to allow finitely many predetermined queries to the target set. [definition: Truth-Table Reducibility] Let $A,B \subseteq \mathbb N$. We say that $A$ is truth-table reducible to $B$, written $A \le_{tt} B$, if there are total computable functions $q:\mathbb N \to \mathbb N^{<\mathbb N}$ and $t:\mathbb N \to \mathbb N$ such that $q(x)=(q_1(x),\dots,q_{k(x)}(x))$ is a finite list of queries and $t(x)$ codes a Boolean function $\theta_x:\{0,1\}^{k(x)} \to \{0,1\}$ satisfying \begin{align*} \mathbb{1}_A(x)=\theta_x(\mathbb{1}_B(q_1(x)),\dots,\mathbb{1}_B(q_{k(x)}(x))). \end{align*} [/definition] Truth-table reducibility allows more information from $B$ than a many-one reduction, but it still requires all queries to be chosen before any answers are seen. The next theorem places the three pre-Turing reducibilities inside Turing reducibility, identifying exactly which inclusions will be used later when degrees are compared. [definition: Turing Reducibility] Let $A,B \subseteq \mathbb N$. We say that $A$ is Turing reducible to $B$, written $A \le_T B$, if there is an oracle Turing machine $M$ such that the oracle computation with oracle $B$ halts on every input and satisfies \begin{align*} \Phi_M^B(x)=\mathbb{1}_A(x) \end{align*} for every $x \in \mathbb N$. [/definition] Turing reducibility allows the computation to ask membership questions about $B$ while it runs, and later queries may depend on earlier oracle answers. The earlier reducibilities impose extra restrictions on the witness: injectivity, a single computable query, or a fixed finite nonadaptive list of queries. Before comparing the resulting degree notions, we need to know that each restricted witness can be interpreted as an oracle computation without changing the membership decision it makes. [quotetheorem:5406] [citeproof:5406] Each implication forgets part of the witness, and the forgotten structure cannot usually be recovered. The implication $A\le_1 B\implies A\le_m B$ is not reversible: $\mathbb N\le_m\{0\}$ by the constant map $x\mapsto 0$, but $\mathbb N\not\le_1\{0\}$ because an injective witness would have to put infinitely many inputs into a one-element target. The implication $A\le_m B\implies A\le_{tt}B$ is not reversible either: $\mathbb N\setminus K\le_{tt}K$ by making the single query $x$ and negating the answer, while $\mathbb N\setminus K\not\le_m K$, since a many-one reduction to the c.e. set $K$ would make $\mathbb N\setminus K$ c.e. Finally, the implication $A\le_{tt}B\implies A\le_TB$ is not reversible in general; the distinction is that a Turing reduction may choose later oracle questions after seeing earlier answers, whereas a truth-table reduction must commit to a finite query list before receiving any answers. The theorem's role is therefore to locate the reducibilities inside oracle computability, not to collapse their equivalence relations. ## Complete Computably Enumerable Sets Among c.e. sets, the halting problem should be the universal example: every c.e. question can be converted into a halting question. To state such universality, undecidability alone is too weak; a set might be undecidable without uniformly coding every c.e. problem. We therefore need a definition that demands a single computable translation from each c.e. set into the proposed universal c.e. set. [definition: Many-One Complete Computably Enumerable Set] A c.e. set $C \subseteq \mathbb N$ is many-one complete for the c.e. sets if for every c.e. set $A \subseteq \mathbb N$, $A \le_m C$. [/definition] Completeness says that $C$ is not merely undecidable; it contains a uniform coded copy of every c.e. decision problem. The halting problem has this property because a c.e. set is exactly a set accepted by some partial computable function, and the next theorem turns that acceptance into a diagonal halting instance. [quotetheorem:5407] [citeproof:5407] The c.e. hypothesis is essential: if $A$ were arbitrary, then a many-one reduction $A \le_m K$ would make $A$ c.e. by enumerating the preimage of the c.e. set $K$ under the computable reduction. The theorem also does not say that every complete c.e. set is literally the same set as $K$, only that every c.e. set has a single computable coding into $K$. This proof is the template behind many completeness arguments: freeze the original instance into a program, then ask a universal halting question about that program. The next section asks for an intrinsic diagonal property that recognises the same complete c.e. behaviour without mentioning reductions from all c.e. sets. [example: Totality as a Stronger Oracle Candidate] Let $\operatorname{TOT}=\{e : \varphi_e \text{ is total}\}$. For each index $e$, \begin{align*} e\in \operatorname{TOT} &\iff \text{for every } x\in \mathbb N,\ \varphi_e(x)\downarrow\\ &\iff \forall x\,\exists s\,[\text{the computation } \varphi_e(x) \text{ halts by stage } s]. \end{align*} Thus totality has the shape of a $\Pi^0_2$ condition. The hierarchy chapter will later make this classification sharp and show that totality is not computable from $K$. At this point in the course, we only record the easier direction: an oracle for totality can decide the ordinary halting set. We now show the other direction, $K\le_T \operatorname{TOT}$. Given $e$, construct uniformly an index $p_e$ for the following program on input $y$: simulate $\varphi_e(e)$; if that simulation halts, output $0$. The input $y$ is not used except as the input on which this program is being run. Therefore, for every $y$, \begin{align*} \varphi_{p_e}(y)\downarrow &\iff \varphi_e(e)\downarrow. \end{align*} Taking the universal quantifier over $y$ gives \begin{align*} p_e\in \operatorname{TOT} &\iff \forall y\,\varphi_{p_e}(y)\downarrow\\ &\iff \forall y\,\varphi_e(e)\downarrow\\ &\iff \varphi_e(e)\downarrow\\ &\iff e\in K. \end{align*} The map $e\mapsto p_e$ is total computable by the s-m-n theorem, so an oracle for $\operatorname{TOT}$ decides $K$ by computing $p_e$ and asking whether $p_e\in\operatorname{TOT}$. Hence $K\le_T\operatorname{TOT}$. Later, after the arithmetical hierarchy has been developed, this same example becomes the standard comparison showing that deciding every individual halting question is weaker than deciding whether one program halts on all inputs. [/example] The example warns against treating all oracle access as equivalent to a single coding. Many-one reducibility is designed for uniform c.e. recognition, while totality problems involve a global condition over infinitely many computations. ## Creative and Productive Sets Completeness can also be characterised by a more intrinsic diagonal property. Instead of saying that every c.e. set reduces to $C$, we ask whether the complement of $C$ can effectively escape every c.e. subset proposed inside it. Fix, once and for all, an effective enumeration $(W_e)_{e\in\mathbb N}$ of the computably enumerable subsets of $\mathbb N$, where $W_e$ is the set enumerated by program $e$ in the chosen acceptable numbering. This convention lets a single index $e$ name both an enumeration procedure and the c.e. set it produces. [definition: Productive Set] A set $P \subseteq \mathbb N$ is productive if there is a partial computable function $p:\mathbb N \rightharpoonup \mathbb N$ such that whenever $W_e \subseteq P$, the value $p(e)$ is defined and satisfies \begin{align*} p(e) \in P \setminus W_e. \end{align*} [/definition] The function $p$ is a uniform diagonal witness: given an attempted c.e. listing inside $P$, it produces an element of $P$ omitted by that listing. This motivates the next definition, which applies productivity to the complement of a c.e. set so that the set itself behaves like a complete positive information problem. [definition: Creative Set] A c.e. set $C \subseteq \mathbb N$ is creative if $\mathbb N \setminus C$ is productive. [/definition] Creative sets formalise the mechanism behind diagonal incompleteness. Their complements cannot be exhausted by any c.e. approximation, and the next example shows that the halting set has exactly this kind of effective escape property. [example: The Complement of K is Productive] Let $K=\{n:\varphi_n(n)\downarrow\}$, and let $W_e$ be the c.e. set enumerated by program $e$. Given $e$, use the *parameterized recursion theorem* to obtain an index $n=p(e)$ for the program which, on input $y$, enumerates $W_e$ and halts exactly if the number $n$ is eventually enumerated into $W_e$. The map $e\mapsto p(e)$ is total computable, and the defining property of the index $n=p(e)$ gives \begin{align*} \varphi_n(y)\downarrow &\iff n \text{ is eventually enumerated into } W_e\\ &\iff n\in W_e \end{align*} for every input $y$. In particular, taking $y=n$, \begin{align*} n\in K &\iff \varphi_n(n)\downarrow\\ &\iff n\in W_e. \end{align*} Now assume $W_e\subseteq \mathbb N\setminus K$. If $n\in W_e$, then the displayed equivalence gives $n\in K$, contradicting $W_e\subseteq \mathbb N\setminus K$. Hence $n\notin W_e$. Using the same equivalence again, $n\notin W_e$ implies $n\notin K$. Therefore \begin{align*} n\in \mathbb N\setminus K \quad\text{and}\quad n\notin W_e, \end{align*} so \begin{align*} p(e)=n\in (\mathbb N\setminus K)\setminus W_e. \end{align*} Thus $p$ is a productive function for $\mathbb N\setminus K$: every c.e. subset of the complement of $K$ effectively misses a computable diagonal element. [/example] This is the same diagonal idea as the noncomputability of $K$, but now expressed uniformly in the index $e$. At this point there are two different descriptions of maximal c.e. complexity: an external one, where every c.e. set many-one reduces to $C$, and an internal one, where the complement of $C$ effectively escapes every c.e. subset of it. The issue is whether these are genuinely the same notion or merely parallel diagonal phenomena. [quotetheorem:5408] [citeproof:5408] The c.e. hypothesis on $C$ is necessary because creativity is a property of positive information together with a productive complement; an arbitrary productive complement without a c.e. positive side need not represent a c.e.-complete decision problem. A concrete boundary case is $\mathbb N\setminus \operatorname{TOT}$: its complement $\operatorname{TOT}$ is a standard productive set, but $\mathbb N\setminus \operatorname{TOT}$ is not c.e., so it cannot be creative or many-one complete for the c.e. sets in the sense above. The theorem also does not say that productivity alone gives a many-one complete set, since the set whose complement is productive must itself be c.e. Myhill's theorem explains why creative sets are the right intrinsic version of c.e. completeness, and it prepares the later use of the recursion theorem as a uniform self-reference principle in degree-theoretic arguments. ## Rice-Shapiro and Extensional Properties Rice's theorem from the previous chapter says that every proper extensional property of partial computable functions is undecidable. For c.e. index sets, the sharper question is which extensional properties are themselves c.e.; Rice-Shapiro gives the finite-positive-information answer. [definition: Extensional Index Set] A set $I \subseteq \mathbb N$ is extensional if for all $e,d \in \mathbb N$, \begin{align*} \varphi_e = \varphi_d \implies (e \in I \iff d \in I). \end{align*} [/definition] An extensional index set depends only on the partial function computed, not on the syntactic program chosen. A c.e. enumeration can only act after seeing finite positive evidence from a computation; it cannot wait for an entire infinite graph of a partial function to be revealed. We therefore need notation for the finite pieces of a computation table that can serve as observable witnesses. [definition: Finite Subfunction] Let $\theta$ be a finite partial function $\theta: \mathbb N \rightharpoonup \mathbb N$ and let $\psi$ be a partial function $\psi: \mathbb N \rightharpoonup \mathbb N$. We write $\theta \subseteq \psi$ if $\operatorname{dom}(\theta) \subseteq \operatorname{dom}(\psi)$ and $\theta(x)=\psi(x)$ for every $x \in \operatorname{dom}(\theta)$. [/definition] Finite subfunctions represent finite positive observations about a computation table. The obstruction for c.e. extensional properties is that enumeration is irreversible: once an index is listed, the finite evidence seen so far must already force membership for every extension computing the same kind of partial function. The characterization asks exactly when membership can always be justified by such an enumerable finite trace. [remark: Quoted result: Rice-Shapiro Theorem] Let $\mathcal A$ be an extensional class of partial computable functions, and let \begin{align*} I_{\mathcal A}=\{e : \varphi_e \in \mathcal A\}. \end{align*} Then $I_{\mathcal A}$ is c.e. iff there is a c.e. set $S$ of finite partial functions such that, for every partial computable function $\psi$, \begin{align*} \psi \in \mathcal A \iff \text{there exists } \theta \in S \text{ with } \theta \subseteq \psi. \end{align*} Equivalently, membership in $\mathcal A$ is forced by some enumerable finite positive trace and is closed upward under extension among partial computable functions. [/remark] The extensionality hypothesis is essential: without it, an index set may depend on the code number rather than on the computed partial function, and finite computation traces cannot detect such syntactic information. The upward finite-trace condition is also essential; totality fails it because every finite trace of a total function is compatible with a partial computable extension that later diverges. In this chapter Rice-Shapiro is used as a structural test for c.e. index sets rather than as another reducibility theorem: it identifies the positive finite evidence that an enumeration can eventually see. Conceptually, it says that c.e. semantic properties are open in the topology generated by finite computation traces, which connects computability theory with the general idea that observable finite data generate an effective topology. [example: Totality Has No Finite Positive Witness] Consider $\operatorname{TOT}=\{e:\varphi_e \text{ is total}\}$. Let $\theta:\mathbb N\rightharpoonup\mathbb N$ be any finite partial function contained in a total computable function $g$, so \begin{align*} \operatorname{dom}(\theta)\subseteq \mathbb N \quad\text{is finite, and}\quad g(x)=\theta(x)\text{ for every }x\in\operatorname{dom}(\theta). \end{align*} Define a partial computable function $\psi_\theta$ by the finite lookup rule \begin{align*} \psi_\theta(x)= \begin{cases} \theta(x), & x\in\operatorname{dom}(\theta),\\ \uparrow, & x\notin\operatorname{dom}(\theta). \end{cases} \end{align*} This is partial computable because $\operatorname{dom}(\theta)$ is finite: a program can compare $x$ with each element of $\operatorname{dom}(\theta)$, output the corresponding value if a match is found, and otherwise enter an infinite loop. For every $x\in\operatorname{dom}(\theta)$, \begin{align*} \psi_\theta(x)=\theta(x), \end{align*} so $\theta\subseteq \psi_\theta$. Since $\operatorname{dom}(\theta)$ is finite and $\mathbb N$ is infinite, choose $z\notin\operatorname{dom}(\theta)$. Then \begin{align*} \psi_\theta(z)\uparrow, \end{align*} so $\psi_\theta$ is not total. Thus the same finite trace $\theta$ is compatible both with the total computable function $g$ and with the non-total partial computable function $\psi_\theta$. No finite positive observation can force totality, so by the *Rice-Shapiro Theorem*, the index set $\operatorname{TOT}$ is not c.e. [/example] This example connects Rice-Shapiro back to reducibility. The halting set $K$ is c.e. because halting has a finite positive witness: a completed computation. Totality is different because every finite trace is compatible with both total and non-total behaviour. ## Uniform and Nonuniform Reductions A final issue must be settled before Turing degrees are introduced. When we say that a problem reduces to another, do we require a single computable method that transforms all instances, or do we merely assert that each instance has some helpful witness? Degree theory uses uniform reductions because degrees are meant to measure algorithms, not scattered existential coincidences. [definition: Uniform Reduction] Fix a reducibility notion $r\in\{m,1,tt,T\}$. A reduction from $A \subseteq \mathbb N$ to $B \subseteq \mathbb N$ is uniform of type $r$ if there is a single effective witness for all inputs: for $r=m$ or $r=1$, a total computable map $f:\mathbb N\to\mathbb N$; for $r=tt$, total computable functions coding a finite query list and a Boolean truth table; and for $r=T$, one oracle Turing machine $M$ such that the oracle functional $\Phi_M^B:\mathbb N\to\{0,1\}$ is total and satisfies $\Phi_M^B(x)=\mathbb{1}_A(x)$ for every $x\in\mathbb N$. [/definition] The witness must decide $x\in A$ from the corresponding allowed information about $B$ for every $x\in\mathbb N$. Uniformity is already built into $\le_m$, $\le_1$, $\le_{tt}$, and $\le_T$: each is witnessed by one computable function or one oracle machine. A nonuniform comparison may give separate witnesses for separate inputs or finite subproblems without producing an effective global method, as the next example demonstrates. [example: Pointwise Witnesses Do Not Give a Reduction] Choose fixed numbers $b_1\in B$ and $b_0\notin B$, which exist because $B$ is nonempty and proper. For each $x\in\mathbb N$, the set-theoretic choice rule \begin{align*} g(x)= \begin{cases} b_1, & x\in A,\\ b_0, & x\notin A \end{cases} \end{align*} satisfies the membership equivalence \begin{align*} x\in A &\iff g(x)=b_1\\ &\iff g(x)\in B, \end{align*} because $b_1\in B$ and $b_0\notin B$. This does not by itself witness $A\le_m B$, since many-one reducibility requires the witnessing map to be total computable. For a concrete failure, take $A=K$ and $B=\{0\}$, with $b_1=0$ and $b_0=1$. If the rule above were computable, then on input $x$ we could compute $g(x)$ and decide \begin{align*} x\in K &\iff g(x)\in \{0\}\\ &\iff g(x)=0, \end{align*} which would make $K$ decidable. Since $K$ is undecidable, this pointwise choice rule cannot be computable. Thus separate witnesses for separate inputs record membership facts, but they do not provide a uniform algorithmic reduction. [/example] This distinction prevents degree structures from collapsing into set-theoretic cardinal comparisons. To use reducibility as an ordering relation, however, one more obstruction remains: solving $A$ by coding into $B$ and solving $B$ by coding into $C$ should give a uniform way to solve $A$ by coding into $C$. This requires the witnessing maps themselves to compose effectively, not just the underlying membership facts to line up. [quotetheorem:5409] [citeproof:5409] The computability of both witnesses is essential. For the first witness, let $A=K$, $B=\{0\}$, and $C=\{0\}$; the set-theoretic map sending $x$ to $0$ exactly when $x\in K$ gives a noncomputable membership-preserving map from $A$ to $B$, and the identity map reduces $B$ to $C$, but $K\not\le_m\{0\}$ because a computable reduction to a computable singleton would decide $K$. For the second witness, take $A=B=K$ and $C=\{0\}$; the identity witnesses $A\le_mB$, and a set-theoretic characteristic map reduces $B$ to $C$, but again $A\not\le_mC$. Thus transitivity depends not only on the membership equivalences but on the effective construction of both maps. The theorem also does not say that unrelated reducibilities compose in the same way without checking their witnesses; for example, composing an adaptive oracle computation with a single-query coding requires explicitly substituting the coding into each oracle query. Transitivity is what lets us form degree structures by identifying sets that reduce to one another. But the degrees obtained depend on the allowed reductions: many-one degrees, truth-table degrees, and Turing degrees retain different information about how a problem may use another. [remark: Why the Chosen Reducibility Matters] Many-one equivalence preserves single-query coding strength, truth-table equivalence preserves bounded nonadaptive finite-query strength, and Turing equivalence permits adaptive oracle computation. A set may be complete under Turing reducibility without being complete under many-one reducibility for the same class of problems. Thus the phrase "the degree of a set" is incomplete until the reducibility has been fixed. [/remark] The next chapter begins the study of Turing degrees proper. The present chapter supplies the comparison scale: one-one and many-one reductions capture direct coding, truth-table reductions capture finite nonadaptive oracle use, and Turing reductions capture general algorithmic access to an oracle. The reducibilities of the previous chapter provide the language for comparing computational strength, but Turing reducibility is the full notion needed to talk about oracles and degree structure. Chapter 4 turns that comparison scale into a theory of relative computation and the equivalence classes that organize noncomputable sets. # 4. Turing Reducibility and Degrees This chapter moves from individual computable and computably enumerable sets to computation relative to extra information. The guiding question is how much computational power is contained in a set of natural numbers when it is made available as an oracle. This leads to Turing reducibility, the equivalence classes called Turing degrees, and the first view of the global geometry of noncomputability. ## Computing Relative To An Oracle A computable procedure may fail to decide a set because it lacks some noncomputable information. To separate the finite mechanical part of a computation from the information it is allowed to consult, we introduce machines that can ask membership questions about a fixed set. [definition: Oracle Turing Machine] An oracle Turing machine is a Turing machine equipped with a special query mechanism. For each set $B \subseteq \mathbb N$, the machine with oracle $B$ may ask whether a queried number $n$ belongs to $B$ and receives the correct yes-or-no answer in one step. [/definition] The oracle is treated as an external information source, not as a program that the machine has to compute. Once this model is available, the natural comparison question is whether one set of information is enough to decide another set. [definition: Turing Reducibility] Let $A, B \subseteq \mathbb N$. We write $A \le_T B$ if there is an oracle Turing machine which, with oracle $B$, computes the characteristic function of $A$. [/definition] Thus $A \le_T B$ means that membership in $A$ can be decided using finitely many adaptive questions about membership in $B$. As Chapter 3 already showed for many-one reducibility, the next problem is whether these broader oracle comparisons can be chained without changing their meaning, since degree theory will use reducibility as its basic ordering relation. [quotetheorem:5410] [citeproof:5410] The finiteness of each oracle computation is the hypothesis that makes the transitivity simulation legitimate: without termination of the computation answering a simulated $B$-query, the outer machine could get stuck before returning an answer about $A$. The theorem does not say that $A \le_T B$ and $B \le_T A$ force $A=B$ as sets; it only says that reducibility comparisons compose. For example, if $E=\{2n:n\in A\}$ is the even coding of $A$, then $A \le_T E$ by querying $2n$, and $E \le_T A$ by dividing even inputs by $2$ and rejecting odd inputs. This concrete coding failure is why the next step is to identify sets with the same relative computational power. [definition: Turing Equivalence] Let $A, B \subseteq \mathbb N$. We write $A \equiv_T B$ if $A \le_T B$ and $B \le_T A$. [/definition] Turing equivalence removes coding differences while preserving what can be computed from a set. The remaining problem is that any particular representative may contain irrelevant coding choices, such as using only even numbers to store the same information. Degree theory avoids this dependence by treating the whole equivalence class as the unit of computational content. [definition: Turing Degree] Let $\mathcal D_T$ denote the class of Turing degrees. The Turing degree map is \begin{align*} \deg_T : \mathcal P(\mathbb N) \to \mathcal D_T, \end{align*} defined for $A \subseteq \mathbb N$ by \begin{align*} \deg_T(A) = \{B \subseteq \mathbb N : B \equiv_T A\}. \end{align*} [/definition] A degree is an equivalence class of sets, not a preferred representative. Sometimes we also need to keep a fixed problem $A$ and look upward at all oracles strong enough to solve it; this leads to the language of cones. [definition: Turing Cone] Let $A \subseteq \mathbb N$. The cone above $A$ is the class \begin{align*} \{B \subseteq \mathbb N : A \le_T B\}. \end{align*} [/definition] Cones record all oracles with at least a prescribed amount of information. They will later help formulate statements that hold above every degree, rather than only near the computable sets. [example: A One-Query Reduction To The Halting Set] Fix an effective enumeration $(\varphi_e)_{e\in\mathbb N}$ of the partial computable functions, and let \begin{align*} K=\{e\in\mathbb N:\varphi_e(e)\downarrow\}. \end{align*} Suppose $f:\mathbb N\to\mathbb N$ is computable and \begin{align*} A=\{n\in\mathbb N:\varphi_{f(n)}(f(n))\downarrow\}. \end{align*} We show that $A\le_T K$ by giving a $K$-oracle decision procedure for membership in $A$. On input $n$, first compute the natural number $m=f(n)$; this halts because $f$ is computable. Then ask the oracle whether $m\in K$. By the definition of $K$, \begin{align*} m\in K &\Longleftrightarrow \varphi_m(m)\downarrow. \end{align*} Since $m=f(n)$, this is \begin{align*} \varphi_m(m)\downarrow &\Longleftrightarrow \varphi_{f(n)}(f(n))\downarrow. \end{align*} By the definition of $A$, \begin{align*} \varphi_{f(n)}(f(n))\downarrow &\Longleftrightarrow n\in A. \end{align*} Combining the three equivalences gives \begin{align*} m\in K &\Longleftrightarrow n\in A. \end{align*} Therefore the oracle answer to the single question “$f(n)\in K$?” is exactly the correct answer to “$n\in A$?”, so $A\le_T K$. The pattern is to computably transform the input $n$ into an index $f(n)$ whose self-halting behavior encodes the original membership question. [/example] ## The Partially Ordered Degrees Reducibility gives a preorder on sets, but the structural object of degree theory is the quotient order on equivalence classes. The problem in this section is to identify the bottom of that order and the first important noncomputable benchmark. [definition: Order On Turing Degrees] For Turing degrees $a = \deg_T(A)$ and $b = \deg_T(B)$, define \begin{align*} a \le b \quad \text{if and only if} \quad A \le_T B. \end{align*} [/definition] This definition uses representatives, so the first issue is whether changing representatives changes the answer. The theorem below resolves that issue and shows that antisymmetry appears exactly because mutual reducibility has already been quotiented out. [quotetheorem:5411] [citeproof:5411] The quotient by $\equiv_T$ is essential here: on actual sets, the even coding $E=\{2n:n\in A\}$ can satisfy $A \equiv_T E$ while $A\ne E$. Thus antisymmetry would fail if we tried to order raw subsets of $\mathbb N$ by mutual reducibility. The theorem does not identify what the degrees look like internally; it only guarantees that comparisons between them form a genuine partial order. Now that the order is defined, its least element should represent no oracle power beyond ordinary computability. This gives a name to the degree of all computable sets. [definition: Computable Degree] The computable degree is \begin{align*} 0 = \deg_T(\varnothing). \end{align*} [/definition] The empty oracle carries no positive membership information, so computations relative to it should be the same as ordinary computations. This needs verification because an oracle machine is syntactically allowed to ask questions even when the oracle is empty; those answers are all predetermined, and hence should be removable from the computation. The result identifies exactly which sets fall into the bottom degree. [quotetheorem:5412] [citeproof:5412] The empty-oracle hypothesis is doing real work: if the oracle is allowed to be a noncomputable set $B$, then $B \le_T B$ even when $B$ is not computable. The theorem therefore does not say that every set reducible to some oracle is computable; it says exactly that reducibility to no positive information is ordinary decidability. This identifies the bottom of the degree structure. The next reference point is the degree of the halting problem, since it measures the power needed to decide convergence of ordinary computations. [definition: Halting Degree] Let $K = \{e \in \mathbb N : \varphi_e(e)\downarrow\}$. The halting degree is \begin{align*} 0' = \deg_T(K). \end{align*} [/definition] The notation $0'$ anticipates the jump operator studied later. The important question here is whether passing from the empty oracle to the halting set gives a genuinely stronger source of information or merely a different representative of the computable degree. If $K$ were computable, then its degree would still be $0$, so the degree notation would add no new point to the order. The obstruction is the same diagonal nondecidability that made $K$ the benchmark in the first place. [quotetheorem:5413] [citeproof:5413] The noncomputability of $K$ is the decisive input: if the chosen representative for $0'$ were computable, its degree would collapse back to $0$. The theorem does not say that $0'$ is the least nonzero degree, and in fact that question leads toward Post's problem. What it does provide is the first fixed noncomputable benchmark above the computable degree. The halting set is also computably enumerable, so its degree belongs to an important subclass of degrees. The next definition isolates degrees that have some enumerable representative, because many naturally presented noncomputable sets arise by enumeration rather than arbitrary oracle coding. [definition: Computably Enumerable Degree] A Turing degree $a$ is computably enumerable, or c.e., if $a = \deg_T(A)$ for some computably enumerable set $A \subseteq \mathbb N$. [/definition] A c.e. degree need not consist entirely of c.e. sets; the definition asks only for one c.e. representative. This distinction matters because Turing equivalence allows substantial recoding. [example: The Halting Degree Is C.E.] Enumerate $K$ as follows. At stage $s$, for each $e \le s$, simulate the computation $\varphi_e(e)$ for exactly $s$ steps, and enumerate $e$ if this simulation has halted and $e$ has not already been enumerated. This enumeration lists exactly the elements of $K$. If $e$ is enumerated at some stage $s$, then the stage-$s$ simulation has witnessed that $\varphi_e(e)$ halts within $s$ steps, so \begin{align*} e \in K. \end{align*} Conversely, if $e \in K$, then by definition \begin{align*} \varphi_e(e)\downarrow. \end{align*} So there is some number $t$ such that $\varphi_e(e)$ halts within $t$ computation steps. At stage \begin{align*} s=\max(e,t), \end{align*} we have both $e \le s$ and $t \le s$, so the stage-$s$ search includes the computation $\varphi_e(e)$ and runs it long enough to see that it halts. Hence $e$ is enumerated at stage $s$ unless it was already enumerated earlier. Thus $K$ is computably enumerable. Since \begin{align*} 0'=\deg_T(K), \end{align*} the degree $0'$ has a computably enumerable representative, namely $K$, and is therefore a c.e. degree. It is not the computable degree: if $0'=0$, then $\deg_T(K)=0$, so by *Characterisation Of The Computable Degree* the set $K$ would be computable, contradicting the noncomputability of the halting set. [/example] ## Joins And Least Upper Bounds The degree order is not expected to be linear, so we need an operation which combines two sources of oracle information. The obstruction is concrete: an oracle for $A$ may decide no useful questions about $B$, and an oracle for $B$ may decide no useful questions about $A$, but an upper bound should provide both kinds of answers. The join $A \oplus B$ interleaves two sets into one oracle in a way that preserves access to both components. [definition: Join Of Sets] The join operation is the map \begin{align*} \oplus : \mathcal P(\mathbb N) \times \mathcal P(\mathbb N) \to \mathcal P(\mathbb N), \end{align*} defined by \begin{align*} (A,B) \mapsto A \oplus B = \{2n : n \in A\} \cup \{2n+1 : n \in B\}. \end{align*} [/definition] The even numbers carry the information of $A$, and the odd numbers carry the information of $B$. The first check is that this coding has not hidden either component: both can be recovered by computable decoding of parity. [example: Reducing Each Component To The Join] Fix $A,B\subseteq \mathbb N$. We show that each component is computable from the joined oracle \begin{align*} A\oplus B=\{2k:k\in A\}\cup\{2k+1:k\in B\}. \end{align*} To decide whether $n\in A$ using oracle $A\oplus B$, compute $2n$ and ask the oracle whether $2n\in A\oplus B$. By the definition of the join, \begin{align*} 2n\in A\oplus B &\Longleftrightarrow 2n\in \{2k:k\in A\}\cup\{2k+1:k\in B\}\\ &\Longleftrightarrow \bigl(2n\in \{2k:k\in A\}\bigr)\ \text{or}\ \bigl(2n\in \{2k+1:k\in B\}\bigr). \end{align*} The second disjunct is false, because an even number cannot equal an odd number. For the first disjunct, \begin{align*} 2n\in \{2k:k\in A\} &\Longleftrightarrow \text{there is }k\in A\text{ such that }2n=2k\\ &\Longleftrightarrow \text{there is }k\in A\text{ such that }n=k\\ &\Longleftrightarrow n\in A. \end{align*} Hence \begin{align*} 2n\in A\oplus B \Longleftrightarrow n\in A, \end{align*} so this one-query oracle procedure computes $A$ from $A\oplus B$. Similarly, to decide whether $n\in B$, compute $2n+1$ and ask whether $2n+1\in A\oplus B$. Again from the definition of the join, \begin{align*} 2n+1\in A\oplus B &\Longleftrightarrow \bigl(2n+1\in \{2k:k\in A\}\bigr)\ \text{or}\ \bigl(2n+1\in \{2k+1:k\in B\}\bigr). \end{align*} The first disjunct is false, because an odd number cannot equal an even number. For the second disjunct, \begin{align*} 2n+1\in \{2k+1:k\in B\} &\Longleftrightarrow \text{there is }k\in B\text{ such that }2n+1=2k+1\\ &\Longleftrightarrow \text{there is }k\in B\text{ such that }n=k\\ &\Longleftrightarrow n\in B. \end{align*} Therefore \begin{align*} 2n+1\in A\oplus B \Longleftrightarrow n\in B. \end{align*} Thus $A\le_T A\oplus B$ and $B\le_T A\oplus B$: the even part of the join recovers $A$, and the odd part recovers $B$. [/example] This example shows that the join is an upper bound. The stronger question is whether it is the least such upper bound, meaning that any oracle capable of computing both $A$ and $B$ can compute the combined oracle. [quotetheorem:5414] [citeproof:5414] The assumptions $A \le_T C$ and $B \le_T C$ are both necessary for this particular conclusion: if $C$ computes only $A$, then on odd inputs the proposed decision procedure for $A\oplus B$ would still need information about $B$. The theorem does not say that $A\oplus B$ is the only set representing the least upper bound; any Turing-equivalent coding of the two components represents the same degree. What matters is that parity coding gives a canonical representative whose two halves can be decoded uniformly. The preceding theorem gives the pairwise least upper bounds. The next result combines it with the existence of the computable degree to package the first algebraic description of the whole degree structure. [quotetheorem:5415] [citeproof:5415] Well-definedness is the subtle point: without quotienting by Turing equivalence, changing $A$ to a different coding could change the literal set $A\oplus B$. The theorem does not assert the existence of greatest lower bounds, so it gives an upper semilattice rather than a lattice. This distinction will matter when comparing the degree order with more familiar algebraic orders. The operation $\vee$ behaves like a join in order theory, not like addition of sets. A useful special case is joining with a computable set, where no new degree-theoretic information is added. [example: Joining With A Computable Set] Let $C \subseteq \mathbb N$ be computable, and fix a computable decision procedure for $C$. We show that for every $A \subseteq \mathbb N$, \begin{align*} A \oplus C \equiv_T A. \end{align*} First, $A \le_T A \oplus C$. On input $n$, compute $2n$ and ask the oracle whether $2n \in A \oplus C$. By the definition of the join, \begin{align*} 2n \in A \oplus C &\Longleftrightarrow 2n \in \{2k:k\in A\}\cup \{2k+1:k\in C\}\\ &\Longleftrightarrow \bigl(2n\in \{2k:k\in A\}\bigr)\ \text{or}\ \bigl(2n\in \{2k+1:k\in C\}\bigr). \end{align*} The second disjunct is false, since $2n=2k+1$ would make an even number equal to an odd number. For the first disjunct, \begin{align*} 2n\in \{2k:k\in A\} &\Longleftrightarrow \text{there is }k\in A\text{ such that }2n=2k\\ &\Longleftrightarrow \text{there is }k\in A\text{ such that }n=k\\ &\Longleftrightarrow n\in A. \end{align*} Hence \begin{align*} 2n\in A\oplus C \Longleftrightarrow n\in A, \end{align*} so the even query computes $A$ from $A\oplus C$. Conversely, $A\oplus C \le_T A$. On input $m$, compute whether $m$ is even or odd. If $m=2n$, ask the oracle whether $n\in A$. Then \begin{align*} m\in A\oplus C &\Longleftrightarrow 2n\in A\oplus C\\ &\Longleftrightarrow n\in A, \end{align*} by the computation above. If $m=2n+1$, run the computable decision procedure for $C$ on input $n$. In this case, \begin{align*} m\in A\oplus C &\Longleftrightarrow 2n+1\in \{2k:k\in A\}\cup \{2k+1:k\in C\}\\ &\Longleftrightarrow \bigl(2n+1\in \{2k:k\in A\}\bigr)\ \text{or}\ \bigl(2n+1\in \{2k+1:k\in C\}\bigr). \end{align*} The first disjunct is false, since an odd number cannot equal an even number. For the second disjunct, \begin{align*} 2n+1\in \{2k+1:k\in C\} &\Longleftrightarrow \text{there is }k\in C\text{ such that }2n+1=2k+1\\ &\Longleftrightarrow \text{there is }k\in C\text{ such that }n=k\\ &\Longleftrightarrow n\in C. \end{align*} Thus odd inputs are decided without using the oracle for $A$, because $C$ is computable. We have both $A\le_T A\oplus C$ and $A\oplus C\le_T A$, so $A\oplus C\equiv_T A$ and therefore \begin{align*} \deg_T(A\oplus C)=\deg_T(A). \end{align*} Joining with a computable set adds no new oracle information; it only adds a decidable odd component. [/example] ## Incomparability And The Shape Of The Degree Structure A partial order may contain pairs with neither element below the other. In Turing degree theory, incomparability is a central phenomenon because it shows that computational power is not arranged in a single ladder. [definition: Incomparable Turing Degrees] Two Turing degrees $a$ and $b$ are incomparable if neither $a \le b$ nor $b \le a$ holds. [/definition] Incomparability says that each oracle contains information the other cannot uniformly recover. Their join exists, and the next observation records why it must lie strictly above both degrees. [remark: Join Of Incomparable Degrees] If $a$ and $b$ are incomparable, then $a < a \vee b$ and $b < a \vee b$. The strictness follows because equality $a \vee b = a$ would imply $b \le a$, and equality $a \vee b = b$ would imply $a \le b$. [/remark] This remark explains how the semilattice operation interacts with non-linearity. The remaining structural question is how much non-linearity the degree order contains. A standard orientation theorem says that every countable partial order embeds into the partially ordered set of Turing degrees. This result is stated here as orientation rather than proved in this chapter. Its proof uses priority-style constructions and coding methods developed later in the course. [explanation: Consequences For The Course] The upper semilattice theorem gives a stable algebraic operation, while the embedding theorem signals that no simple linear hierarchy can describe relative computability. The remaining chapters refine this picture. The jump operator produces systematic increases in computational power, Post's problem asks how c.e. degrees sit between $0$ and $0'$, and priority arguments provide the construction methods needed to build degrees with prescribed non-comparability properties. [/explanation] Once Turing degrees are available, the next step is to understand how computational strength changes under a canonical operation. Chapter 5 introduces the jump as the basic measure of a higher halting problem relative to an oracle, and uses it to sharpen the structure uncovered by degree theory. # 5. The Jump Operator and Relativization Chapters 2 through 4 built the distinction between decidable and computably enumerable sets, compared reducibilities, and then organized noncomputability by Turing reducibility. This chapter introduces the operation that measures the next uniform halting problem above a given oracle. The Turing jump turns a set $A$ into a stronger set $A'$ and gives a precise way to iterate the passage from computability to relative computable enumerability. The main questions are: how much stronger is $A'$ than $A$, how does the jump interact with Turing reducibility, and how far do earlier theorems survive when all machines are allowed an oracle? The answers are the beginning of degree theory above the computable sets: $A <_T A'$, the jump is monotone, diagonalization relativizes, and the iterated jumps $0^{(n)}$ provide the arithmetical hierarchy's basic landmarks. ## The Halting Problem Relative to an Oracle The ordinary halting problem asks whether program $e$ halts on input $e$. Once oracle computation has been introduced, the same question can be asked relative to any fixed set $A \subseteq \mathbb N$: if machines may query $A$, which of those oracle computations halt? [definition: Oracle Computation] Let $A \subseteq \mathbb N$. A partial function $\varphi_e^A: \mathbb N \rightharpoonup \mathbb N$ is the partial function computed by the $e$-th Turing machine when that machine is allowed oracle queries of the form "$n \in A$?" during its computation. [/definition] This notation makes the dependence on the oracle explicit. Different choices of $A$ may change whether the same program halts, because the program's future computation can depend on oracle answers received earlier. [example: An Oracle-Dependent Computation] Let $e$ be an index for the oracle program which, on input $0$, first asks the oracle query "$0 \in A$?" If the oracle answers yes, the program halts; if the oracle answers no, the program enters an infinite loop. Therefore \begin{align*} 0 \in A &\implies \text{the oracle answer to "$0 \in A$?" is yes}\\ &\implies \varphi_e^A(0)\downarrow, \end{align*} while \begin{align*} 0 \notin A &\implies \text{the oracle answer to "$0 \in A$?" is no}\\ &\implies \varphi_e^A(0)\uparrow. \end{align*} Hence $\varphi_e^A(0)$ is defined exactly when $0 \in A$. The same program index $e$ can therefore halt relative to one oracle and fail to halt relative to another, depending only on the answer to a single oracle query. [/example] The example shows that relative halting is already sensitive to the oracle at the level of a single query. To compare oracles by their halting power, we need a single set that collects the diagonal halting questions for all $A$-oracle programs at once. [definition: Turing Jump] The Turing jump is the map \begin{align*} J: \mathcal P(\mathbb N) &\to \mathcal P(\mathbb N),\\ A &\mapsto A' = K^A := \{e \in \mathbb N : \varphi_e^A(e) \downarrow\}. \end{align*} [/definition] Some authors distinguish $K^A$ from $A'$ by using different acceptable numberings or by coding pairs $\langle e,x\rangle$ rather than diagonal inputs. These versions are Turing equivalent, so the degree of the jump is independent of the harmless coding choice. The next definition names the class of sets whose membership can be recognized, rather than decided, when the same oracle $A$ is available. [definition: Relative Computable Enumerability] Let $A,B \subseteq \mathbb N$. The set $B$ is computably enumerable relative to $A$, written $B$ is c.e. in $A$, if there is an oracle Turing machine with oracle $A$ whose domain is exactly $B$. [/definition] Relative computable enumerability is the correct language for universal halting questions: the jump is the universal c.e.-in-$A$ set. To decide whether a relative enumeration eventually lists a number, it is enough to ask a suitable question of $A'$. [remark: Universal Property of the Jump] If $B$ is computably enumerable in $A$, then $B$ is reducible to $A'$. The later relativized completeness theorem gives the sharper many-one version. [/remark] This theorem is the practical reason for introducing the jump: $A'$ decides all existential halting questions over $A$-computations. The hypothesis that $B$ is c.e. in $A$ is essential; arbitrary sets need not be reducible to $A'$, since there are only countably many reductions but uncountably many subsets of $\mathbb N$. The theorem also does not say that $B$ is decidable by $A$ itself, and this gap is exactly what the jump measures. The next example records the most common use case, where an existential search becomes decidable once the jump is available. [example: Deciding Relative Sigma-One Questions] Fix $A \subseteq \mathbb N$ and suppose $R(x,y)$ is decidable relative to $A$. Thus there is an $A$-oracle decision procedure which, on input $(x,y)$, halts with answer yes exactly when $R(x,y)$ holds and halts with answer no exactly when $R(x,y)$ fails. For \begin{align*} B=\{x\in \mathbb N:\exists y\,R(x,y)\}, \end{align*} we show that $B$ is c.e. in $A$. On input $x$, run the following $A$-oracle program: \begin{align*} &\text{for }y=0,1,2,\dots,\\ &\quad \text{run the }A\text{-oracle decision procedure for }R(x,y),\\ &\quad \text{halt as soon as the answer is yes.} \end{align*} If $x\in B$, then there is some $y_0$ such that $R(x,y_0)$ holds. The search reaches $y_0$ after checking $0,1,\dots,y_0-1$, and the decision procedure answers yes on $(x,y_0)$, so the search halts. If the search halts on input $x$, it halts only after receiving a yes answer for some pair $(x,y)$, so $R(x,y)$ holds and therefore $x\in B$. Hence \begin{align*} x\in B &\iff \text{the above }A\text{-oracle search halts on input }x. \end{align*} So $B$ is c.e. in $A$. By the *Universal Property of the Jump*, every set c.e. in $A$ is Turing reducible to $A'$, and therefore \begin{align*} B \le_T A'. \end{align*} Thus $A'$ decides existential, or $\Sigma^0_1$, questions relative to $A$ by converting the search for a witness into a single relative halting question. [/example] ## The Jump Is Above the Oracle The first structural question is whether $A'$ really contains the information of $A$, or whether it only solves unrelated halting questions. The answer is that $A$ is uniformly reducible to $A'$. [quotetheorem:5416] [citeproof:5416] This reduction is uniform in $A$: the same computable transformation $n \mapsto p(n)$ works for every oracle. The result says that jumping never loses the original information, but it should not be read as saying that $A'$ is merely $A$ with extra notation. The boundary case $A=\varnothing$ already gives the ordinary halting problem, so even the computable oracle has a noncomputable jump. This is why the following strictness theorem is needed: being able to recover $A$ from $A'$ does not settle whether $A'$ can be recovered from $A$. [example: Recovering an Oracle Bit] Let $A \subseteq \mathbb N$ and fix $n \in \mathbb N$. Define an oracle program $p(n)$ as follows: on any input, it asks the single oracle query "$n \in A$?"; if the answer is yes, it halts, and if the answer is no, it runs forever. By the definition of the jump, \begin{align*} p(n) \in A' &\iff \varphi_{p(n)}^A(p(n))\downarrow\\ &\iff \text{the oracle answer to "$n \in A$?" is yes}\\ &\iff n \in A. \end{align*} Similarly, \begin{align*} p(n) \notin A' &\iff \varphi_{p(n)}^A(p(n))\uparrow\\ &\iff \text{the oracle answer to "$n \in A$?" is no}\\ &\iff n \notin A. \end{align*} Thus an oracle for $A'$ decides whether $n \in A$ by making the single query "$p(n) \in A'$?" The reduction $A \le_T A'$ is therefore not just abstract: each bit of $A$ is recovered from one corresponding halting question in $A'$. [/example] Being above $A$ is not the same as being computable from $A$. The diagonal argument for the ordinary halting problem survives with the oracle $A$ present throughout. [quotetheorem:5417] [citeproof:5417] The conclusion is the relativized form of the noncomputability of the halting problem. It also explains why the jump gives a genuine operation on Turing degrees rather than a cosmetic recoding of $A$. The theorem depends on giving the diagonal program access to exactly the same oracle as the alleged decision procedure; without that shared oracle, the contradiction would compare different computational worlds. It does not imply that $A'$ is incomparable with all other sets above $A$, only that $A$ itself cannot decide its own halting problem. This distinction becomes important when comparing different oracles by monotonicity. [example: The Relative Halting Set Is Not Relative Decidable] Fix $A \subseteq \mathbb N$. To see that $K^A=A'$ is c.e. in $A$, run the following $A$-oracle enumeration procedure: for stages $s=0,1,2,\dots$, simulate the first $s+1$ diagonal computations \begin{align*} \varphi_0^A(0),\ \varphi_1^A(1),\ \dots,\ \varphi_s^A(s) \end{align*} for $s$ steps each, and list every $e\le s$ whose simulation has halted by then. If $e\in K^A$, then $\varphi_e^A(e)\downarrow$, so there is some finite number of steps $t$ at which this computation halts. At stage $s=\max(e,t)$, the enumeration simulates $\varphi_e^A(e)$ for at least $t$ steps, sees it halt, and lists $e$. Conversely, if the procedure lists $e$, it does so only after observing that the simulation of $\varphi_e^A(e)$ has halted, so $\varphi_e^A(e)\downarrow$ and hence $e\in K^A$. Therefore the enumeration lists exactly the elements of $K^A$. The strictness theorem for the jump gives \begin{align*} A' \nleq_T A. \end{align*} Since $K^A=A'$, this says that no $A$-oracle decision procedure can decide membership in $K^A$. Thus $K^A$ can be recognized relative to $A$ by waiting for diagonal computations to halt, but it cannot be decided relative to $A$; relative recognition and relative decision are still different notions. [/example] ## Monotonicity and Degree Invariance The next question is how the jump behaves under reducibility. A naive worry is that jumping might depend so delicately on the oracle answers that a reduction $A \le_T B$ would not give enough uniform control over whole $A$-oracle computations. The point of monotonicity is that a single chosen reduction from $A$ to $B$ can be built into every simulated oracle query, turning $A$-oracle programs into $B$-oracle programs effectively. [quotetheorem:5418] [citeproof:5418] Monotonicity requires an actual reduction $A \le_T B$; mere inclusion $A \subseteq B$ is irrelevant unless it yields such a decision procedure. For instance, $\varnothing' \subseteq \mathbb N$, but $\varnothing' \nleq_T \mathbb N$ because $\mathbb N$ is computable. Inclusion alone therefore cannot answer the negative membership queries needed when an oracle program asks whether $n \in A$. The theorem also does not reflect order: from $A' \le_T B'$ one cannot in general recover $A \le_T B$. A standard example is a noncomputable low set $L$, for which $L' \equiv_T \varnothing'$ while $L \nleq_T \varnothing$. Thus the jump may erase distinctions already present below the jump level. Its role is forward control of halting problems, and this is exactly what is needed to pass the jump from sets to degrees. The previous theorem compares particular representatives $A$ and $B$. Since degree theory identifies mutually reducible sets, the next issue is whether the jump is compatible with passing from sets to Turing degrees. [quotetheorem:5419] [citeproof:5419] This theorem justifies writing $\mathbf a'$ for the jump of a Turing degree $\mathbf a$. The theorem depends on having reductions in both directions; a one-sided reduction gives only the one-sided monotonicity statement. For example, $\varnothing \le_T \varnothing'$, so monotonicity gives $\varnothing' \le_T \varnothing''$, but strictness gives $\varnothing'' \nleq_T \varnothing'$. The missing reverse reduction below the jump is exactly what prevents equivalence above the jump. The theorem also does not say that equivalent sets have the same literal jump set, since different representatives and numberings may produce different subsets of $\mathbb N$ in the same degree. Degree invariance is essential in the later study of the partial order of degrees because it makes the jump an order-preserving operation on degrees. [remark: Monotone Does Not Mean Reflecting] The implication $A \le_T B \implies A' \le_T B'$ need not be reversible. Jump inversion theorems describe which degrees can appear as jumps, but the jump can collapse distinctions: distinct degrees may have the same jump degree. [/remark] ## Relativization of Earlier Theorems Many arguments from the first chapters did not depend on the absence of an oracle. They used only effective manipulation of program indices, universal simulation, dovetailing, and diagonalization; each of these has a relative version obtained by allowing all machines to share the same oracle $A$. [definition: Relativization] A theorem or construction relativizes if, for every oracle $A \subseteq \mathbb N$, the same statement remains true after replacing computable functions, c.e. sets, and Turing machines by $A$-computable functions, c.e.-in-$A$ sets, and $A$-oracle machines. [/definition] Relativization is a method, not an automatic truth guarantee for every theorem in computability theory. The first test case is the completeness of the halting problem, because its proof uses only universal simulation, dovetailing, and the $s$-$m$-$n$ theorem, all of which have oracle forms. [quotetheorem:5420] [citeproof:5420] This completeness theorem is stronger than the earlier Turing-reduction universal property because the reduction is many-one: each input is converted into one halting question. The c.e.-in-$A$ hypothesis is again the exact boundary; a set decidable from $A'$ need not itself be c.e. in $A$. The result is the relative form of the ordinary completeness of $K$, and it prepares the general lesson that many classical computability arguments survive unchanged once every machine is given the same oracle. The next example shows how a familiar theorem changes only by adding the oracle as a background parameter. [example: Relative Decidability from Two Enumerations] Let $B \subseteq \mathbb N$. Suppose first that $B$ and $\mathbb N \setminus B$ are both c.e. in $A$. Choose $A$-oracle enumeration procedures $E_0$ and $E_1$ such that $E_0$ lists exactly the elements of $B$ and $E_1$ lists exactly the elements of $\mathbb N \setminus B$. To decide whether $x \in B$ using oracle $A$, run the two enumerations in parallel by stages: at stage $s$, run $E_0$ for $s$ steps and run $E_1$ for $s$ steps, keeping track of all numbers listed so far. If $x$ has appeared in the output of $E_0$, answer yes; if $x$ has appeared in the output of $E_1$, answer no. This decision procedure halts on every input $x$. Indeed, since \begin{align*} x \in B \cup (\mathbb N \setminus B) = \mathbb N, \end{align*} the number $x$ belongs to at least one of the two sets, so it is eventually listed by at least one of $E_0$ or $E_1$. It cannot be listed by both, because \begin{align*} B \cap (\mathbb N \setminus B)=\varnothing. \end{align*} Thus exactly one of the two possible answers is eventually produced, and it is correct. Hence $B \le_T A$. Conversely, suppose $B \le_T A$. Then there is an $A$-oracle decision procedure $D$ such that, for every $x$, \begin{align*} x \in B &\iff D^A(x)\text{ halts with answer yes},\\ x \notin B &\iff D^A(x)\text{ halts with answer no}. \end{align*} To enumerate $B$ relative to $A$, run $D^A(0),D^A(1),D^A(2),\dots$ in dovetailing fashion and list $x$ exactly when $D^A(x)$ returns yes. This lists precisely the elements of $B$. To enumerate $\mathbb N \setminus B$ relative to $A$, use the same dovetailing procedure and list $x$ exactly when $D^A(x)$ returns no. This lists precisely the elements outside $B$. Therefore $B$ is decidable relative to $A$ exactly when both $B$ and its complement are c.e. relative to $A$. [/example] The example illustrates a positive relativized theorem: two relative enumerations combine into a relative decision procedure. To control negative results as well, we need the matching relativized form of diagonalization, where the diagonal machine and the alleged decision procedure use the same oracle. [quotetheorem:5421] [citeproof:5421] This principle is the common template behind $K \nleq_T 0$, $K^A \nleq_T A$, and the strictness of every finite jump level. Its hypothesis is deliberately universal in $e$; partial information about many computations does not trigger the diagonal contradiction. The principle also shows a limitation of relativization as a method: it preserves arguments whose computational content is purely syntactic, but it does not by itself solve questions requiring new constructions of oracles. Those new constructions are the reason jump inversion later leads naturally into priority methods. ## Iterated Jumps and the Arithmetical Hierarchy After one jump, the same construction can be repeated. This produces a hierarchy of increasingly strong halting problems, beginning with the computable degree and climbing through finite iterations. [definition: Iterated Finite Jumps] Let $J: \mathcal P(\mathbb N) \to \mathcal P(\mathbb N)$ be the Turing jump map. Define representatives $(\varnothing^{(n)})_{n \in \mathbb N \cup \{0\}}$ by \begin{align*} \varnothing^{(0)} &= \varnothing,\\ \varnothing^{(n+1)} &= J(\varnothing^{(n)}). \end{align*} The degree $0^{(n)}$ is the Turing degree of the representative $\varnothing^{(n)}$. [/definition] The notation $0'$ is the ordinary halting problem degree, $0''$ is the halting problem relative to any representative of $0'$, and so on; degree invariance makes this independent of the representative chosen. Without fixing representatives first, expressions such as membership in $0^{(n)}$ would be meaningless, because degrees are equivalence classes rather than sets of numbers. The strictness theorem iterates to give a genuine ascending chain. [quotetheorem:5422] [citeproof:5422] Finite jumps give the computational content of finite blocks of first-order number quantifiers. The strictness result also marks a boundary: no fixed finite jump can decide all finite arithmetical levels, because the next jump is always strictly stronger. At this point in the course, we only need the guiding principle that the representative $\varnothing^{(n)}$ decides complete questions at the $n$-th arithmetical level. [definition: Omega Jump Notation] The omega jump representative is the set \begin{align*} \varnothing^{(\omega)} = \{\langle n,x\rangle : x \in \varnothing^{(n)}\}. \end{align*} The degree $0^{(\omega)}$ is the Turing degree of $\varnothing^{(\omega)}$. [/definition] This set is not a finite jump. It is a bookkeeping device for access to all finite jump representatives at once, and it appears when arguments need uniform control over the whole arithmetical hierarchy. The pairing function in the definition matters only up to computable coding, so changing the standard code gives an equivalent degree. The construction also shows why uniformity is a separate issue from finite strength: knowing each finite level individually is weaker than having one oracle that organizes all levels coherently. [example: Using a Finite Jump to Decide Bounded Alternations] Suppose $R(x,y,z)$ is computable, and let \begin{align*} B=\{x\in \mathbb N:\exists y\,\forall z\,R(x,y,z)\}. \end{align*} For fixed $x$ and $y$, define \begin{align*} C_{x,y}=\{z\in \mathbb N:\neg R(x,y,z)\}. \end{align*} Since $R$ is computable, there is a computable decision procedure for $R(x,y,z)$; running that procedure and reversing the yes/no answer decides membership in $C_{x,y}$. Hence the question \begin{align*} C_{x,y}\neq \varnothing &\iff \exists z\,\neg R(x,y,z) \end{align*} is c.e.: search through $z=0,1,2,\dots$, halt exactly when the decision procedure finds a $z$ with $\neg R(x,y,z)$. Therefore $\varnothing'$ can decide whether this search halts, by the *Universal Property of the Jump* with $A=\varnothing$. Thus $\varnothing'$ decides the equivalent universal statement \begin{align*} \forall z\,R(x,y,z) &\iff \neg\exists z\,\neg R(x,y,z)\\ &\iff C_{x,y}=\varnothing. \end{align*} Now use $\varnothing'$ as an oracle to search for the outer witness $y$. On input $x$, run through $y=0,1,2,\dots$; for each $y$, ask the $\varnothing'$-decision procedure whether $\forall z\,R(x,y,z)$ holds, and halt as soon as the answer is yes. This $\varnothing'$-oracle search halts exactly when \begin{align*} \exists y\,\forall z\,R(x,y,z) \end{align*} holds, so $B$ is c.e. in $\varnothing'$. Applying the *Universal Property of the Jump* again, now with $A=\varnothing'$, gives \begin{align*} B\le_T(\varnothing')'=\varnothing''. \end{align*} Thus one jump decides the inner universal block by checking for a counterexample, and the next jump decides the outer existential search. [/example] ## Jump Inversion Theorems The jump raises every degree, but the inverse problem asks which degrees are themselves jumps. This is subtler than monotonicity: we are not trying to compute $A'$ from $A$, but to find an $A$ whose jump has a prescribed degree. [remark: Deferred jump inversion] The basic jump inversion theorem says that every degree $\mathbf b\ge \mathbf 0'$ is the jump of some degree: there is a set $A$ with $A'\equiv_T B$ whenever $B$ has degree $\mathbf b$. This is a structural theorem about all Turing degrees, not only about c.e. degrees. The condition $\mathbf b\ge \mathbf 0'$ is necessary because every jump lies above $\mathbf 0'$, and the theorem says that this necessary condition is also sufficient. Its construction belongs with priority methods rather than with the elementary properties of the jump. [/remark] The basic theorem gives existence of a preimage under the jump. A sharper version asks for control over the computational strength of that preimage. The basic theorem gives inversion above $0'$, but it does not record how complicated the preimage $A$ must be. The classical Friedberg version adds the sharper degree-theoretic conclusion that the preimage can be chosen below the given degree, which is the form needed in many later applications. [remark: Friedberg jump inversion] The Friedberg strengthening chooses the preimage without exceeding the target: for every $B\ge_T\varnothing'$ there is an $A\le_T B$ with $A'\equiv_T B$. The added bound $A\le_T B$ is the useful refinement, because it says that inverting the jump does not require more computational strength than the degree being inverted. The proof is deferred to the priority-method part of the theory. [/remark] Jump inversion says that being above $0'$ is the only degree-theoretic obstruction to being a jump. Friedberg's refinement says more: the set whose jump is $B$ can be constructed without exceeding the computational strength of $B$ itself. These results make the jump operator a central tool for understanding the global shape of the Turing degrees. The jump operator shows how to climb from one level of noncomputability to the next, but it also invites a finer stratification of definability. Chapter 6 develops that stratification through the arithmetical hierarchy, using the relativized machinery from the earlier chapters to classify index sets by logical complexity. # 6. The Arithmetical Hierarchy Chapters 1 through 5 developed partial computable functions, computably enumerable sets, many-one and Turing reducibility, and the Turing jump as concrete tools for measuring noncomputability. Those ideas are the prerequisites for this chapter: we will use effective enumerations of partial computable functions, finite-stage simulations, and the relativised halting problem throughout. We now introduce the arithmetical hierarchy, which measures the logical complexity of sets of natural numbers by the number and pattern of number quantifiers needed to define them. The central theme is that computability-theoretic operations, especially the Turing jump, exactly match first-order definability over arithmetic. This hierarchy is also a model for several other stratifications of definability. In descriptive set theory, Borel and analytic hierarchies classify sets by the kinds of quantifiers permitted over spaces; in computational complexity, polynomial-time hierarchies classify decision problems by alternating bounded searches. The arithmetical hierarchy is the recursion-theoretic version: the quantified objects are natural numbers, the matrix is computable, and alternation measures the depth of unbounded effective search. ## Definability by Arithmetic Formulas The first problem is to turn informal statements such as “program $e$ halts on input $x$” or “program $e$ halts on every input” into a uniform complexity scale. These statements are not decidable in general, but they often have a decidable core hidden behind blocks of quantifiers over $\mathbb N$. The arithmetical hierarchy records the shape of those quantifier blocks. [definition: Computable Predicate] A predicate $R(x_1, \dots, x_k)$ on $\mathbb N^k$ is computable if its characteristic function $\mathbb{1}_R: \mathbb N^k \to \{0,1\}$ is total computable. [/definition] Computable predicates are the decidable base layer: they are the parts of a definition that can be checked by a finite algorithm. To measure noncomputable sets, we need a language that permits quantification over possible witnesses, stages, and inputs while keeping the atomic information effective. This leads to arithmetical formulas. [definition: Arithmetical Formula] An arithmetical formula is a first-order formula in the language of arithmetic, with variables ranging over $\mathbb N$, whose non-logical symbols are interpreted by computable relations and computable functions on $\mathbb N$. [/definition] A raw arithmetical formula is not yet a useful complexity measure. The same condition can be written with extra bounded searches, repeated dummy variables, or negated subformulas, and these cosmetic changes should not create a different level of noncomputability. What matters is the unavoidable alternation of unbounded searches: a finite search can be folded into the decidable part, but an unbounded existential or universal demand changes the kind of evidence needed. For the hierarchy, formulas are sorted by their quantifier alternations after they have been placed into prenex form. Bounded quantifiers do not count, since a bounded search over a computable predicate remains computable. The next definition isolates the three families that will organize the rest of the chapter. [definition: Sigma Pi and Delta Classes] Let $n \ge 1$. A set $A \subset \mathbb N$ is in $\Sigma^0_n$ if there is a computable predicate $R$ such that \begin{align*} x \in A \iff \exists y_1 \forall y_2 \exists y_3 \cdots Q y_n\, R(x,y_1,\dots,y_n), \end{align*} where the quantifier block has $n$ alternating unbounded quantifiers and begins with $\exists$. A set $A$ is in $\Pi^0_n$ if there is such a definition with $n$ alternating unbounded quantifiers beginning with $\forall$. A set $A$ is in $\Delta^0_n$ if $A \in \Sigma^0_n$ and $A \in \Pi^0_n$. [/definition] Thus $\Sigma^0_1$ sets are defined by existential search through a computable relation, while $\Pi^0_1$ sets are defined by universal avoidance of a computable failure condition. The class $\Delta^0_1$ is the computable sets. [example: The Halting Set Is Sigma One] Let \begin{align*} K=\{e\in \mathbb N:\varphi_e(e)\downarrow\}. \end{align*} Fix the computable bounded-stage predicate $T:\mathbb N^3\to\{0,1\}$, where $T(e,x,s)=1$ means that the computation of program $e$ on input $x$ has halted by stage $s$. For each $e$, \begin{align*} e\in K &\iff \varphi_e(e)\downarrow\\ &\iff \text{there is a finite stage }s\text{ by which the computation }\varphi_e(e)\text{ has halted}\\ &\iff \exists s\, T(e,e,s)=1. \end{align*} Since $T$ is computable, the final line has the form required for a $\Sigma^0_1$ definition: one unbounded existential quantifier followed by a computable predicate. Hence $K\in \Sigma^0_1$, and the witness $s$ is exactly the finite evidence that the computation has halted. [/example] The previous example is the template for the first level: membership is verified by finding a finite witness, usually a stage of a computation or enumeration. Since c.e. sets were defined earlier by effective enumeration rather than by formulas, we need to check that the new syntactic class gives exactly the old computability-theoretic class. In the following theorem, $\mathbb W$ denotes the natural-number universe used for coding finite tuples, so $\mathbb W^k$ is the $k$-fold product of coded natural-number inputs. [quotetheorem:1824] [citeproof:1824] This theorem identifies the first existential level with a class already studied earlier in the course, but it does not say that every arithmetical set is c.e. Both hypotheses are doing work. The matrix must be computable: if arbitrary predicates were allowed, then any set $B \subset \mathbb N$ would satisfy \begin{align*} x \in B \iff \exists y\, (y=1 \land x \in B), \end{align*} which would make the statement false. The single leading existential search is also essential: the complement of the halting set is given by $\forall s\, \neg T(e,e,s)$, so it is $\Pi^0_1$, but it is not c.e. Thus changing $\exists s$ to $\forall s$ genuinely changes the computational content. Dually, $\Pi^0_1$ consists of complements of c.e. sets, because a universal statement over a computable predicate is the negation of an existential computable failure. This distinction is the first sign that later alternations must be tracked rather than compressed away. ## Normal Forms and Closure Properties The next question is whether the definition of $\Sigma^0_n$ depends on the exact syntactic presentation of the formula. Without a normal form theorem, the same set could appear to move levels merely because we wrote $R(x,f(y))$ instead of introducing a variable for the value of $f(y)$, or because we inserted a bounded search over a finite interval. In practice, arithmetical definitions arise with many bounded quantifiers, repeated variables, conjunctions, disjunctions, and computable side conditions. Normal forms show that all of this can be reorganised into a standard alternating quantifier block over a single computable predicate. [quotetheorem:4653] [citeproof:4653] Normal form justifies thinking of the hierarchy as a hierarchy of alternating search procedures, but it has precise limitations. Bounded quantifiers can be absorbed because a condition such as $\exists y \le b\, R(x,y)$ is checked by a finite search once $x$ and $b$ are fixed. An unbounded quantifier cannot be absorbed into the computable matrix in the same way: if $\forall s\, \neg T(e,e,s)$ could be replaced uniformly by a computable predicate with no unbounded quantifier, then $\mathbb N \setminus K$ would be computable, contradicting the unsolvability of the halting problem. Prenex conversion also gives an upper bound rather than a minimal classification. Moving quantifiers outward may introduce extra apparent alternations, especially when Boolean combinations of formulas at different levels are normalised, so a displayed prefix does not by itself prove that the set is outside lower levels. Lower bounds require separate arguments such as many-one completeness, diagonalisation, or [Post's Theorem](/theorems/5425). Once formulas have a standard shape, negation becomes a precise operation on the leading quantifier pattern. This makes complements the next structural property to record. Negating a normal-form $\Sigma^0_n$ definition changes the outer existential block into a universal block, and after pushing the negation through the computable matrix one obtains a $\Pi^0_n$ definition. Conversely, negating a $\Pi^0_n$ definition gives a $\Sigma^0_n$ definition. This duality explains the notation: $\Sigma$ classes are existential at the outside, while $\Pi$ classes are universal at the outside. The duality does not say that a $\Sigma^0_n$ set usually has its complement again in $\Sigma^0_n$. At level $1$, $K \in \Sigma^0_1$, but $\mathbb N \setminus K \notin \Sigma^0_1$; otherwise $K$ and its complement would both be c.e., making $K$ computable. The intersection $\Delta^0_n$ consists of sets that admit both forms, so they can be approached from both positive and negative information at that level. To use the hierarchy in calculations, we also need to know that combining finitely many conditions does not change the level. [quotetheorem:5423] [citeproof:5423] The closure properties are useful when classifying examples, because they allow complex index sets to be built from simpler halting and non-halting conditions without leaving the expected level. The word finite is essential. For example, let $K_s$ be the finite set of indices observed to enter $K$ by stage $s$. Each set $\mathbb N \setminus K_s$ is computable, but \begin{align*} \bigcap_{s=1}^{\infty} (\mathbb N \setminus K_s) = \mathbb N \setminus K, \end{align*} which is not $\Sigma^0_1$. Infinite intersections can therefore add a hidden universal quantifier over stages. Infinite unions can add a hidden existential quantifier in the same way: an infinite union of computable finite-stage approximations may produce a c.e. set such as $K$, even though no finite union carries that extra search. The limitation is also visible for complements: $\Sigma^0_n$ is not generally closed under complement, and neither is $\Pi^0_n$. For instance, $K \in \Sigma^0_1$ but $\mathbb N \setminus K \notin \Sigma^0_1$; complement closure would collapse the first level and erase the distinction between positive finite evidence and permanent non-halting. This is why $\Delta^0_n$ is defined as the overlap of the two dual descriptions rather than as either side alone. [remark: Inclusion Between Adjacent Levels] For every $n \ge 1$, \begin{align*} \Sigma^0_n \cup \Pi^0_n \subset \Delta^0_{n+1}. \end{align*} The standard padding argument adds a vacuous quantifier block at the correct end of the prefix and then pairs adjacent same-type quantifiers if they arise. Thus a $\Sigma^0_n$ definition may be placed in $\Sigma^0_{n+1}$, while its complement has a $\Pi^0_n$ definition and hence may be placed in $\Pi^0_{n+1}$. The same reasoning with the roles reversed handles $\Pi^0_n$ sets, so each lower-level set has both a $\Sigma^0_{n+1}$ and a $\Pi^0_{n+1}$ definition. [/remark] This inclusion says that higher levels can simulate lower levels. The main content of the hierarchy is that the inclusions do not collapse. ## Standard Index Sets in the Hierarchy The next classification obstacle is that many natural recursion-theoretic properties are not about a single computation. They ask whether an entire partial computable function has a global feature: a finite domain, an infinite domain, eventual coverage of almost all inputs, totality, or equality with another partial function. Such properties force us to decide which quantifiers come from inputs, which come from stages, and which come from witnesses of convergence. Index sets are the standard testing ground because they expose these quantifiers in their most concrete form. [definition: Domains of Partial Computable Functions] For an index $e \in \mathbb N$, write \begin{align*} W_e = \{x \in \mathbb N : \varphi_e(x)\downarrow\}. \end{align*} [/definition] The set $W_e$ is c.e. uniformly in $e$. Properties of $W_e$ often require quantifying over elements, missing elements, or bounds on future enumeration. When finite stages are needed, write $\varphi_{e,s}(x)\downarrow$ to mean that the computation of program $e$ on input $x$ has halted by stage $s$, and write $\varphi_{e,s}(x)=y$ to mean that this bounded computation halts with value $y$. These are computable bounded-stage relations; they are stage-indexed versions of the partial function $\varphi_e$, not new partial computable functions. [example: Finite Domain] Let \begin{align*} \operatorname{FIN}=\{e:W_e\text{ is finite}\}. \end{align*} We show that membership in $\operatorname{FIN}$ is expressible with one existential bound followed by a universal computable check. Since $W_e=\{x:\varphi_e(x)\downarrow\}$, the set $W_e$ is finite exactly when there is a number $b$ such that no element larger than $b$ ever enters $W_e$. Therefore \begin{align*} e\in \operatorname{FIN} &\iff W_e\text{ is finite}\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies x\notin W_e\bigr)\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies \varphi_e(x)\uparrow\bigr)\\ &\iff \exists b\,\forall x\,\forall s\,\bigl(x>b\implies \neg T(e,x,s)\bigr). \end{align*} The last equivalence uses the definition of the bounded-stage predicate: $\varphi_e(x)\uparrow$ means that there is no finite stage $s$ by which the computation has halted. The matrix $x>b\implies \neg T(e,x,s)$ is computable, because comparison on natural numbers is computable and $T$ is computable. Pair the two universal variables into one variable $z$ with computable projections $(z)_0$ and $(z)_1$: \begin{align*} e\in \operatorname{FIN} \iff \exists b\,\forall z\,\bigl((z)_0>b\implies \neg T(e,(z)_0,(z)_1)\bigr). \end{align*} This has the form $\exists b\,\forall z\,R(e,b,z)$ with $R$ computable, so $\operatorname{FIN}\in \Sigma^0_2$. Negating the displayed definition gives \begin{align*} e\notin \operatorname{FIN} &\iff \neg \exists b\,\forall x\,\forall s\,\bigl(x>b\implies \neg T(e,x,s)\bigr)\\ &\iff \forall b\,\exists x\,\exists s\,\neg\bigl(x>b\implies \neg T(e,x,s)\bigr)\\ &\iff \forall b\,\exists x\,\exists s\,\bigl(x>b\land T(e,x,s)\bigr). \end{align*} Thus $\operatorname{INF}=\{e:W_e\text{ is infinite}\}$ lies in $\Pi^0_2$: every proposed bound $b$ is defeated by some larger input $x$ that enters $W_e$ at a finite stage $s$. [/example] Finiteness is a global negative property: after some point no new large element ever appears. Infiniteness reverses the outer quantifier and asks every proposed bound to fail. [example: Cofinite Domain] Let \begin{align*} \operatorname{COFIN}=\{e:\mathbb N\setminus W_e\text{ is finite}\}. \end{align*} We compute its arithmetical form by unpacking what it means for only finitely many inputs to be missing from $W_e$: \begin{align*} e\in \operatorname{COFIN} &\iff \mathbb N\setminus W_e\text{ is finite}\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies x\notin \mathbb N\setminus W_e\bigr)\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies x\in W_e\bigr)\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies \varphi_e(x)\downarrow\bigr)\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies \exists s\,T(e,x,s)\bigr). \end{align*} The last equivalence uses the definition of the bounded-stage predicate: $\varphi_e(x)\downarrow$ means that the computation has halted by some finite stage $s$. To put the final line into the displayed hierarchy form, rewrite the implication inside the computable matrix: \begin{align*} x>b\implies \exists s\,T(e,x,s) \iff \exists s\,\bigl(x\le b\lor T(e,x,s)\bigr). \end{align*} If $x\le b$, any value of $s$ witnesses the right-hand side; if $x>b$, the disjunction reduces to $T(e,x,s)$. Hence \begin{align*} e\in \operatorname{COFIN} \iff \exists b\,\forall x\,\exists s\,\bigl(x\le b\lor T(e,x,s)\bigr). \end{align*} The matrix $x\le b\lor T(e,x,s)$ is computable, since comparison on natural numbers is computable and $T$ is computable. Therefore $\operatorname{COFIN}\in \Sigma^0_3$. The outer witness $b$ is the finite cutoff after which every input must eventually enter the domain. [/example] The extra alternation for cofinite domains appears because membership in $W_e$ is itself existential in a stage. Asking almost all numbers to be in $W_e$ therefore produces an existential bound, a universal input, and an existential stage. [example: Totality] Let \begin{align*} \operatorname{TOT}=\{e:\varphi_e\text{ is total}\}. \end{align*} For a fixed index $e$, totality means that every input $x$ belongs to the domain $W_e$: \begin{align*} e\in \operatorname{TOT} &\iff \varphi_e\text{ is total}\\ &\iff \forall x\,\bigl(\varphi_e(x)\downarrow\bigr)\\ &\iff \forall x\,\exists s\,T(e,x,s). \end{align*} The last equivalence uses the definition of the bounded-stage predicate: $\varphi_e(x)\downarrow$ means that the computation has halted by some finite stage $s$. The predicate $T(e,x,s)$ is computable, so the final line has the form $\forall x\,\exists s\,R(e,x,s)$ with $R$ computable. Hence $\operatorname{TOT}\in \Pi^0_2$. The formula records exactly the computational content of totality: each input has its own finite halting witness, but the witnesses are not required to be bounded by any computable function of the input. [/example] Totality is the canonical $\Pi^0_2$ property in recursion theory. It is universal over inputs and existential over halting stages, and this pattern cannot be reduced to a c.e. or co-c.e. condition. [example: Equality of Partial Computable Functions] Let \begin{align*} \operatorname{EQ}=\{(e,i):\varphi_e=\varphi_i\}. \end{align*} When $\operatorname{EQ}$ is treated as a subset of $\mathbb N$, the pair $(e,i)$ is coded by a fixed computable pairing function. We show that $\operatorname{EQ}\in\Pi^0_2$ by replacing equality of partial functions with a condition about finite-stage evidence. For a fixed input $x$, the functions $\varphi_e$ and $\varphi_i$ agree on $x$ exactly when every observed halting value on either side is eventually matched by the other side with the same value. Thus \begin{align*} (e,i)\in \operatorname{EQ} &\iff \forall x\,\Bigl(\varphi_e(x)\downarrow=\varphi_i(x)\downarrow\text{ with the same value when they halt}\Bigr)\\ &\iff \forall x\,\forall s\,\Bigl( (\varphi_{e,s}(x)\downarrow \implies \exists t\,\varphi_{i,t}(x)=\varphi_{e,s}(x))\\ &\hspace{45mm}\land (\varphi_{i,s}(x)\downarrow \implies \exists u\,\varphi_{e,u}(x)=\varphi_{i,s}(x)) \Bigr). \end{align*} The first implication says that any finite-stage computation witnessing a value of $\varphi_e(x)$ must be matched by $\varphi_i(x)$, and the second implication says the symmetric condition. If both computations diverge, then no stage $s$ triggers either antecedent. If both halt with the same value, then every sufficiently late observed value on one side is matched by a sufficiently late stage on the other. Now rewrite the implications so that the computable part is visible: \begin{align*} (e,i)\in \operatorname{EQ} \iff \forall x\,\forall s\,\exists t\,\exists u\,\Bigl( (\neg \varphi_{e,s}(x)\downarrow \lor \varphi_{i,t}(x)=\varphi_{e,s}(x)) \land (\neg \varphi_{i,s}(x)\downarrow \lor \varphi_{e,u}(x)=\varphi_{i,s}(x)) \Bigr). \end{align*} The bounded-stage halting relation $\varphi_{e,s}(x)\downarrow$ is computable, and the bounded-stage value comparison $\varphi_{i,t}(x)=\varphi_{e,s}(x)$ is computable by simulating both computations for the displayed finite numbers of stages and comparing the outputs when both have halted. Pair the two universal variables $(x,s)$ into one coded variable and pair the two existential variables $(t,u)$ into one coded variable. The formula then has the form \begin{align*} (e,i)\in \operatorname{EQ} \iff \forall a\,\exists b\,R(e,i,a,b), \end{align*} where $R$ is computable. Hence $\operatorname{EQ}\in\Pi^0_2$: equality of partial computable functions is checked by universally considering every finite piece of positive convergence evidence and existentially requiring a matching finite computation on the other side. [/example] Equality of partial computable functions is more subtle than equality of total computable functions, because divergence must also match. The formulation above avoids a direct divergence predicate by saying that any observed convergent value on one side must eventually be matched by the other. ## Completeness at Low Levels Membership in a hierarchy class gives an upper bound. By itself, an upper bound may overstate the true complexity: a computable set can be written with a redundant $\exists y\, R(x,y)$ definition and hence placed in $\Sigma^0_1$, even though it lies in $\Delta^0_1$. Completeness gives the corresponding lower bound by showing that every set in the class can be many-one reduced to the example under discussion. [definition: Many-One Completeness for a Class] Let $\Gamma$ be a class of subsets of $\mathbb N$. A set $A$ is many-one complete for $\Gamma$ if $A \in \Gamma$ and for every $B \in \Gamma$ there is a total computable function $f: \mathbb N \to \mathbb N$ such that \begin{align*} x \in B \iff f(x) \in A. \end{align*} [/definition] Completeness means that the set is a universal representative of its level. At the first level, the halting set plays this role: every existential computable search can be converted into the question of whether a single program halts. The next theorem makes that universality precise and prepares the pattern for higher-level complete sets. [quotetheorem:5407] [citeproof:5407] This theorem packages all c.e. search problems into one index set. Completeness is stronger than noncomputability: it says that solving $K$ would solve every $\Sigma^0_1$ question uniformly. The reduction hypothesis is part of the content. The map $g$ must be total computable, because a partial or noncomputable translation could hide the original decision problem inside the act of producing the index. For instance, if noncomputable reductions were allowed, any set $B$ could be reduced to any nonempty proper set by sending elements of $B$ to a fixed yes-instance and elements outside $B$ to a fixed no-instance. The theorem is also specific to the first existential level: later results show that $\operatorname{TOT}$ is $\Pi^0_2$-complete, so it cannot be many-one reduced to $K$ without collapsing the hierarchy. At the next universal level, the corresponding universal problem is whether every input receives some finite halting witness. [quotetheorem:5424] [citeproof:5424] This proof explains why $\operatorname{TOT}$ sits at the second universal level. The universal quantifier over inputs is necessary: asking whether a single computation halts gives the $\Sigma^0_1$ problem $K$, while asking whether every input halts forces a uniform family of searches, one for each $u$. A first-level halting question can certify success by one finite computation, but totality has no single finite certificate: for any finite list of inputs that have halted, another input may still diverge. Trying to compress $\forall u\,\exists v\,R(x,u,v)$ into one existential halting search would require a computable procedure that recognises when all infinitely many searches have succeeded, and such a recognition procedure would decide $\operatorname{TOT}$ from $K$, contradicting the strictness later obtained from the jump. The reduction must again be total computable, since the index $e_x$ is required to be produced effectively from $x$ before any information about whether all witnesses exist is known. The theorem is a completeness statement for $\Pi^0_2$, not for all arithmetical sets; properties with a further alternation, such as cofiniteness of $W_e$, require a higher-level universal problem. This prepares the move from individual complete examples to the general jump analysis in Post's Theorem. ## Post's Theorem and the Jump So far the hierarchy has been defined by formulas, but a formula count by itself does not explain why an oracle should help. The concrete difficulty is this: an oracle for the halting problem decides one existential search over a computable relation, but it is not immediate that iterating the jump exactly matches adding further alternations rather than giving too much or too little power. Post's Theorem resolves this by identifying the $n$th Turing jump with the decision power needed for the corresponding arithmetical levels. [definition: Iterated Turing Jump] The Turing jump is the map \begin{align*} J: \mathcal P(\mathbb N) &\to \mathcal P(\mathbb N),\\ A &\mapsto A', \end{align*} where $A' \subset \mathbb N$ is the set of indices of oracle machines that halt when run with oracle $A$ on their own index. Define $A^{(0)} = A$ and $A^{(n+1)} = J(A^{(n)}) = (A^{(n)})'$. For the computable base set $\varnothing$, write $\varnothing^{(n)}$ for the $n$th jump of the empty set. [/definition] The preceding definition gives the operation, but it does not yet relate jumps to formulas. We need a theorem that identifies the computational power of $\varnothing^{(n-1)}$ with the ability to decide the first $n-1$ layers of alternation, and then perform one more c.e. search. That identification is Post's Theorem. [quotetheorem:5425] [citeproof:5425] Post's Theorem is the bridge between syntax and computation. The hypotheses matter: the theorem concerns subsets of $\mathbb N$ definable by first-order number quantifiers over computable predicates, not arbitrary second-order definitions over sets or functions. A concrete failure occurs if set quantifiers are allowed: the property "there is a set $X$ coding an infinite path through a computable tree" is analytic rather than arithmetical in general, and it need not be decided by any finite jump $\varnothing^{(n)}$. The oracle base is also part of the statement. Relative to an arbitrary oracle $B$, the set $B'$ is c.e. in $B$ and occupies the first existential level over $B$, but it need not be c.e. relative to $\varnothing$ when $B$ is noncomputable. Thus replacing $\varnothing$ by another oracle changes the hierarchy being measured; it gives the relativised arithmetical hierarchy over that oracle. This turns quantifier alternations into jumps, so the hierarchy is not merely a catalogue of formulas but a scale of Turing information. This still leaves a possible failure mode: perhaps the scale is well-defined but degenerate, with later jumps deciding no genuinely new arithmetical sets. A hierarchy of formulas would be much less useful if every apparent new alternation could always be eliminated. The obstruction to such elimination is that each level contains a relativised halting problem whose diagonal nondecidability cannot be captured one level lower. [quotetheorem:5426] [citeproof:5426] Strictness means that each alternation genuinely adds expressive power. The condition $n \ge 1$ is needed because the displayed hierarchy starts with $\Delta^0_1$, the computable sets; there is no preceding arithmetical level $\Delta^0_0$ in this convention to separate from $\Sigma^0_0$. The counterexamples are concrete at every level: $K$ witnesses $\Delta^0_1 \subsetneq \Sigma^0_1$, and at higher levels the corresponding lower-jump relativized halting sets witness the analogous separations. If an attempted collapse such as $\Sigma^0_n=\Pi^0_n$ held, then the relativised halting problem at that level would become decidable one jump earlier, contradicting the diagonal construction of the jump. This also tells us that completeness results are meaningful: $K$ cannot be pushed down to $\Delta^0_1$, and $\operatorname{TOT}$ cannot be pushed down to $\Sigma^0_1$ or $\Pi^0_1$. ## Reading Quantifiers in Practice When a new index-set property is first stated in words, the main difficulty is deciding which part of the statement is finite evidence and which part is an infinite demand. A phrase such as "halts somewhere", "halts everywhere", "misses only finitely many inputs", or "matches another program" can hide several quantifier alternations. The practical task is to expose those alternations before trying to name the level. [explanation: Classification Strategy] Start by replacing convergence $\varphi_e(x)\downarrow$ with $\exists s\,T(e,x,s)$ and replacing divergence with $\forall s\,\neg T(e,x,s)$. Next express the property using quantifiers over inputs, bounds, and stages. Pair adjacent quantifiers of the same type, absorb bounded quantifiers into the computable matrix, and simplify Boolean combinations using closure properties. To prove that the classification is sharp, reduce from a complete set at the same level, often $K$, its complement, $\operatorname{TOT}$, or a standard higher-jump analogue. [/explanation] This method is most reliable when the informal property is first phrased in terms of finite evidence. Positive evidence usually contributes existential stage quantifiers; permanent absence contributes universal stage quantifiers; statements about all inputs contribute universal input quantifiers. [example: Summary of Classifications] For this summary, fix the computable bounded-stage predicate $T(e,x,s)$, where $T(e,x,s)=1$ means that $\varphi_e(x)$ has halted by stage $s$. Each classification follows by replacing convergence with a finite stage witness and divergence with the absence of all finite stage witnesses: \begin{align*} e\in K &\iff \varphi_e(e)\downarrow\\ &\iff \exists s\,T(e,e,s), \end{align*} so $K$ has one leading existential quantifier over a computable predicate, and hence $K\in\Sigma^0_1$. For the domain properties, \begin{align*} e\in\operatorname{FIN} &\iff W_e\text{ is finite}\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies x\notin W_e\bigr)\\ &\iff \exists b\,\forall x\,\forall s\,\bigl(x>b\implies \neg T(e,x,s)\bigr). \end{align*} Pairing the two universal variables $(x,s)$ into one coded variable gives a form $\exists b\,\forall z\,R(e,b,z)$ with $R$ computable, so $\operatorname{FIN}\in\Sigma^0_2$. Negating this displayed formula gives \begin{align*} e\in\operatorname{INF} &\iff e\notin\operatorname{FIN}\\ &\iff \forall b\,\exists x\,\exists s\,\bigl(x>b\land T(e,x,s)\bigr), \end{align*} and pairing $(x,s)$ gives a $\Pi^0_2$ definition. For totality, \begin{align*} e\in\operatorname{TOT} &\iff \forall x\,\bigl(\varphi_e(x)\downarrow\bigr)\\ &\iff \forall x\,\exists s\,T(e,x,s), \end{align*} so $\operatorname{TOT}\in\Pi^0_2$. For cofiniteness, \begin{align*} e\in\operatorname{COFIN} &\iff \mathbb N\setminus W_e\text{ is finite}\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies x\in W_e\bigr)\\ &\iff \exists b\,\forall x\,\bigl(x>b\implies \exists s\,T(e,x,s)\bigr)\\ &\iff \exists b\,\forall x\,\exists s\,\bigl(x\le b\lor T(e,x,s)\bigr), \end{align*} where the last equivalence rewrites the implication into a computable matrix. Hence $\operatorname{COFIN}\in\Sigma^0_3$. Finally, equality of partial computable functions can be written without a divergence predicate by requiring every observed halting value on either side to be matched by the other side: \begin{align*} (e,i)\in\operatorname{EQ} \iff \forall x\,\forall s\,\exists t\,\exists u\,\Bigl( (\neg \varphi_{e,s}(x)\downarrow \lor \varphi_{i,t}(x)=\varphi_{e,s}(x)) \land (\neg \varphi_{i,s}(x)\downarrow \lor \varphi_{e,u}(x)=\varphi_{i,s}(x)) \Bigr). \end{align*} The bounded-stage halting and value-comparison relations in the matrix are computable, and pairing $(x,s)$ and $(t,u)$ gives a formula of the form $\forall a\,\exists b\,R(e,i,a,b)$ with $R$ computable. Thus \begin{align*} K &\in \Sigma^0_1,\\ \operatorname{FIN} &\in \Sigma^0_2,\\ \operatorname{INF} &\in \Pi^0_2,\\ \operatorname{TOT} &\in \Pi^0_2,\\ \operatorname{COFIN} &\in \Sigma^0_3,\\ \operatorname{EQ} &\in \Pi^0_2. \end{align*} The completeness results *Halting Set Completeness* and *Totality Completeness* show that the bounds for $K$ and $\operatorname{TOT}$ are sharp at $\Sigma^0_1$ and $\Pi^0_2$, respectively. [/example] The arithmetical hierarchy will be used later as a background language for degree-theoretic constructions. It gives a precise way to say how complex an index set is before asking finer questions about its Turing degree, its jump, or its role in priority arguments. The arithmetical hierarchy gives a language for complexity, but Post's problem asks for a structural separation inside the c.e. degrees themselves. Chapter 7 returns to computably enumerable sets and uses the earlier hierarchy and reducibility tools to ask whether there are degrees strictly between computable and halting. # 7. Post's Problem and Simple Sets Post's problem asks whether the computably enumerable Turing degrees contain anything strictly between the computable degree and the halting degree. Earlier chapters showed that c.e. sets arise as the domains and ranges of partial computable procedures, and that the halting problem $K$ is c.e. but not computable. This chapter uses the course's earlier material on Turing reducibility, many-one reducibility, c.e. enumerations, the recursion theorem from the reducibility chapter, and the standard listing $(W_e)_{e \in \mathbb{N}}$ of c.e. sets. The new issue is not mere noncomputability, but calibrated noncomputability: can a c.e. set be noncomputable without being able to compute $K$? ## The Degree-Theoretic Form Of Post's Problem The central question is how much information a c.e. set can contain. A noncomputable c.e. set has enough information to defeat a decision procedure, but it may still fall short of encoding the halting problem. To ask the question invariantly, we first phrase it in terms of degrees rather than particular indices or enumerations. [definition: Computably Enumerable Turing Degree] A Turing degree $a$ is computably enumerable, or c.e., if $a = \deg_T(A)$ for some computably enumerable set $A \subset \mathbb{N}$. [/definition] This definition separates a property of representatives from a property of degrees. A set is c.e. when it has an effective enumeration, while a degree is c.e. when at least one set in that degree has such an enumeration. The next question is which two benchmark degrees bound the interval studied in Post's problem. [definition: Zero And Jump Degrees] The degree $0_T$ is the Turing degree of the computable subsets of $\mathbb{N}$. The degree $0_T'$ is the Turing degree of the halting problem $K = \{e \in \mathbb{N} : \varphi_e(e)\downarrow\}$. [/definition] The interval between these two degrees is the first place where the degree structure becomes a genuine object of study. A positive solution to Post's problem would exhibit a c.e. set whose enumeration carries noncomputable information, but not enough to decide $K$. We therefore need a name for degrees that sit strictly inside this interval. [definition: Intermediate C E Degree] A c.e. degree $a$ is intermediate if \begin{align*} 0_T < a < 0_T'. \end{align*} [/definition] With this language, Post's problem becomes a statement about whether the c.e. degrees are rich enough near their bottom to contain an intermediate degree. In modern terms, the positive solution says that there exists a c.e. set $A\subseteq\mathbb N$ with \begin{align*} 0_T<\deg_T(A)<0_T'. \end{align*} This is the theorem eventually proved by the Friedberg-Muchnik priority construction; here it is introduced as the problem that motivates the chapter rather than as an already established theorem card. This assertion is not proved by simple sets alone. Its eventual proof uses a priority construction, developed later by Friedberg and Muchnik, that simultaneously prevents computability and prevents completeness. This chapter studies Post's earlier strategy: impose structural thinness on the complement of a c.e. set and ask whether that thinness forces intermediate degree. [remark: Why The Problem Is Subtle] Every c.e. set $A$ satisfies $A \le_T K$, because $K$ can decide whether a given enumeration of $A$ ever lists an input. Thus every c.e. degree lies below $0_T'$. The challenge is to keep $A$ noncomputable while also ensuring $K \nleq_T A$. [/remark] The rest of the chapter introduces simple sets, explains why they give a natural first attack on Post's problem, and then identifies the exact limitation of that attack. ## Simple Sets As A First Separation Attempt How can we build a c.e. set that is guaranteed not to be computable? One robust method is to arrange that its complement is infinite but contains no infinite c.e. subset. If the original c.e. set were computable, then its infinite complement would be computable and hence c.e., contradicting this design. [definition: Immune Set] A set $B \subset \mathbb{N}$ is immune if $B$ is infinite and no infinite computably enumerable set is contained in $B$. [/definition] Immunity expresses a strong form of effective thinness. The set may be infinite, but no algorithm can enumerate infinitely many elements from inside it. [example: Non Immune Infinite Computable Set] Let $B = 2\mathbb{N} = \{2n : n \in \mathbb{N}\}$. The set $B$ is infinite because the map $n \mapsto 2n$ gives distinct elements of $B$: if $2m = 2n$, then subtracting gives $2(m-n)=0$, so $m=n$. It is computable because, on input $x$, divide $x$ by $2$: if the remainder is $0$, then $x=2n$ for $n=x/2$ and $x \in B$; if the remainder is $1$, then no natural number $n$ satisfies $x=2n$, so $x \notin B$. Since $B$ is computable, it is computably enumerable by the procedure \begin{align*} 0,\ 2,\ 4,\ 6,\ \dots,\ 2s,\ \dots . \end{align*} This procedure enumerates only elements of $B$, and every element $2n \in B$ appears at stage $n$. Thus $B$ itself is an infinite c.e. subset of $B$. Therefore $B$ is not immune, because immunity requires that no infinite c.e. set be contained in $B$. This shows that immunity is stronger than infinitude: it forbids infinite effective substructure inside the set. [/example] The example shows that an infinite complement is not enough; a computable complement would still contain an infinite effective subset. This motivates the definition of a c.e. set whose complement has exactly the immune behaviour needed to force noncomputability. [definition: Simple Set] A set $A \subset \mathbb{N}$ is simple if $A$ is computably enumerable and $\mathbb{N} \setminus A$ is immune. [/definition] Equivalently, a simple set is a c.e. set with infinite complement such that every infinite c.e. set intersects it. This equivalent form is usually the one used during construction: for each c.e. set $W_e$, if $W_e$ is infinite then put at least one element of $W_e$ into $A$. [remark: Simple Sets Are Noncomputable] If $A$ is simple, then $A$ is not computable. Indeed, if $A$ were computable, then its infinite complement would also be computable and hence c.e., giving an infinite c.e. subset of $\mathbb N\setminus A$ and contradicting immunity. [/remark] The c.e. hypothesis in the definition of simplicity is essential for its role in Post's problem: without it, an arbitrary set with immune complement need not represent a c.e. degree at all. The infinitude of the complement is also essential; if $\mathbb{N} \setminus A$ were finite, then $A$ would be computable and the immunity condition would be vacuous if infinitude were omitted. The observation above does not say that simple sets are incomplete, only that they are not computable, so it supplies the lower inequality $0_T < \deg_T(A)$ and leaves the upper inequality $\deg_T(A) < 0_T'$ untouched. This is the first reason simple sets looked promising for Post's problem. They are c.e. and noncomputable by a structural argument rather than by coding $K$ directly. [remark: Complement Thinness Versus Degree Strength] The definition of simplicity controls which c.e. sets can fit inside the complement of $A$. It does not directly control which computations are possible using $A$ as an oracle. This distinction is the source of the failure of simplicity alone to solve Post's problem. [/remark] The construction of a simple set is the prototype of a finite-injury priority argument. Each requirement asks for a witness from a different c.e. set, while a global restraint keeps the complement infinite. ## Building A Simple C E Set The construction must solve two problems at once. It must meet every infinite c.e. set, so that the complement has no infinite c.e. subset. It must also leave infinitely many numbers out of $A$, so that the complement is not accidentally finite. [definition: Simplicity Requirement] For $e \in \mathbb{N}$, the requirement $R_e$ is \begin{align*} R_e &: W_e \text{ infinite } \implies W_e \cap A \ne \varnothing. \end{align*} [/definition] The requirements are ordered by priority: $R_1, R_2, R_3, \dots$. Requirement $R_e$ is allowed to use a witness larger than $2e$, which reserves infinitely many small initial opportunities for the complement. These requirements now have to be assembled into one effective enumeration. [quotetheorem:5427] [citeproof:5427] The threshold $x > 2e$ is not decorative: if requirements were allowed to enumerate arbitrary available witnesses, a construction meeting all infinite $W_e$ could accidentally exhaust almost every number and lose the infinite complement. For instance, if each requirement always took the least available witness, the early requirements could consume a long initial segment, and no uniform counting estimate would guarantee infinitely many omissions. The restriction that each requirement acts at most once is equally important; if a single requirement for an infinite set such as $W_e = \mathbb{N}$ were allowed to act every time it saw a new witness above $2e$, it could enumerate all sufficiently large numbers by itself. The theorem constructs simple sets, not intermediate sets, and the next sections explain why this successful priority schedule still does not control computations from $A$. This proof is more than an existence argument: it displays the scheduling idea behind priority constructions. Each requirement receives finite permission to act, and the choice of large witnesses prevents the collection of all actions from exhausting the natural numbers. [example: Meeting A Single Infinite C E Set] Fix a requirement $R_e$, whose target is \begin{align*} W_e \text{ infinite } \implies W_e \cap A \ne \varnothing . \end{align*} At stage $s$, the construction acts for $R_e$ only if $R_e$ is not yet satisfied and there is some element $x \in W_{e,s}$ with \begin{align*} x > 2e \quad\text{and}\quad x \notin A_s . \end{align*} If such an $x$ appears, the construction enumerates $x$ into $A$, so \begin{align*} x \in W_{e,s} \subseteq W_e \quad\text{and}\quad x \in A . \end{align*} Therefore $x \in W_e \cap A$, and hence \begin{align*} W_e \cap A \ne \varnothing . \end{align*} The requirement $R_e$ is then declared satisfied, so it never needs another witness. If $W_e$ first enumerates only small numbers $y \le 2e$, or numbers already in $A_s$, none of those numbers is eligible for $R_e$ at that stage. If later $W_e$ enumerates an eligible $x>2e$ outside $A_s$, the preceding argument shows that one action satisfies $R_e$. If $W_e$ is finite and no eligible witness ever appears, then the construction may never act for $R_e$; this is harmless because the implication defining $R_e$ has hypothesis "$W_e$ infinite," so a finite $W_e$ does not require any intersection with $A$. [/example] The example illustrates the local action of one requirement. To complete the global verification, we must connect these local actions to the claimed immunity of the complement: every infinite c.e. set appears as some $W_e$ and is therefore targeted. [quotetheorem:5428] [citeproof:5428] The infinitude of $B$ is the hypothesis that activates the requirement $R_e$; a finite c.e. subset of the complement may exist and causes no contradiction. The c.e. hypothesis on $B$ is also necessary, since an immune set may contain infinite non-c.e. subsets. Thus the theorem proves exactly effective immunity of the complement, not ordinary smallness, density, or any bound on the Turing strength of $A$. The proof has a useful contrapositive reading: every infinite effective attempt to stay outside $A$ is eventually caught. This is the sense in which a simple set is unavoidable by infinite c.e. searches. ## Hypersimple And Hyperhypersimple Sets Post strengthened simplicity because simple sets did not visibly prevent completeness. The next refinements ask not only that the complement avoid infinite c.e. subsets, but that it avoid more uniform ways of being split into many finite c.e. pieces. The failure mode is that an immune set may still contain one point from each member of an effective sequence of disjoint finite boxes; the union of those chosen points need not be c.e., so immunity alone does not detect it. [definition: Strong Array] A strong array is a map $n \mapsto D_n$ from $\mathbb{N}$ to the finite subsets of $\mathbb{N}$ such that the sets $D_n$ are pairwise disjoint and the relation \begin{align*} \mathbb{1}_{D_n}(x) = 1 \iff x \in D_n \end{align*} is represented by a computable indicator function $(n,x) \mapsto \mathbb{1}_{D_n}(x)$ from $\mathbb{N}^2$ to $\{0,1\}$. [/definition] Strong arrays provide a way for a set to contain infinitely many effective finite targets without containing a single infinite c.e. subset. Hypersimplicity asks that even this uniformly decidable distributed finite search cannot keep finding points in the complement. [definition: Hypersimple Set] A c.e. set $A \subset \mathbb{N}$ is hypersimple if $\mathbb{N} \setminus A$ is infinite and for every strong array $(D_n)_{n \in \mathbb{N}}$, there exists $n$ such that \begin{align*} D_n \cap (\mathbb{N} \setminus A) = \varnothing. \end{align*} [/definition] In words, the complement cannot meet every member of a uniformly computable disjoint sequence of finite tests. Since hypersimplicity was introduced as a strengthening of simplicity, we need to prove that it really implies the earlier notion rather than defining a separate unrelated property. [quotetheorem:5429] [citeproof:5429] This implication shows that hypersimplicity is a genuine strengthening of simplicity. It blocks a wider class of effective attempts to find the complement. Post's next refinement allowed the finite tests to be presented by uniform c.e. enumerations rather than by a uniformly decidable membership relation. [definition: Weak Array] A weak array is a map $n \mapsto D_n$ from $\mathbb{N}$ to the finite subsets of $\mathbb{N}$ such that the sets $D_n$ are pairwise disjoint and the binary relation $x \in D_n$ is computably enumerable uniformly in $n$. [/definition] Weak arrays are less decidable than strong arrays but more general as tests: membership in $D_n$ may be discovered by enumeration rather than decided outright. The resulting notion asks whether the complement can defeat every such uniformly enumerated finite sequence. [definition: Hyperhypersimple Set] A c.e. set $A \subset \mathbb{N}$ is hyperhypersimple if $\mathbb{N} \setminus A$ is infinite and for every weak array $(D_n)_{n \in \mathbb{N}}$, there exists $n$ such that \begin{align*} D_n \cap (\mathbb{N} \setminus A) = \varnothing. \end{align*} [/definition] Because every strong array is a weak array, hyperhypersimplicity implies hypersimplicity under these conventions. Different textbooks vary slightly in how they formalise arrays; the common theme is that hyperhypersimplicity strengthens the obstruction by quantifying over a larger class of uniformly presented finite tests. These notions were historically important because they isolated finer combinatorial properties of c.e. complements before the priority solution to Post's problem was available. [remark: Historical Role Of The Refinements] Simple, hypersimple, and hyperhypersimple sets form a ladder of attempts to force incompleteness by making the complement increasingly resistant to effective search. The ladder captures real combinatorial distinctions among c.e. sets. It does not, by itself, coincide with the Turing-degree distinction needed for Post's problem. [/remark] The failure is instructive: degree-theoretic strength is about oracle computations, while these refinements are about effective subsets of complements. The next section makes this separation explicit. ## Why Simplicity Alone Does Not Solve Post's Problem The construction of a simple set proves noncomputability, so it might seem to have produced an intermediate degree. The missing step is incompleteness. A simple c.e. set may still compute the halting problem, and then its degree is $0_T'$ rather than an intermediate degree. [definition: Creative Set] A c.e. set $C \subset \mathbb{N}$ is creative if there is a computable function $p: \mathbb{N} \to \mathbb{N}$ such that whenever $W_e \subset \mathbb{N} \setminus C$, we have \begin{align*} p(e) \in \mathbb{N} \setminus C \quad\text{and}\quad p(e) \notin W_e. \end{align*} [/definition] Creativity is a productive diagonal property of the complement. It does more than keep infinite c.e. subsets out: it supplies a computable way to escape any proposed c.e. subset of the complement. That productive escape is exactly the extra structure needed to recover the halting problem from the set. [quotetheorem:5430] [citeproof:5430] The c.e. hypothesis on $C$ is needed for the final equivalence $C \le_T K$; the productive argument alone gives the reduction $K \le_m C$. The productivity hypothesis is much stronger than simplicity: an immune complement only blocks infinite c.e. subsets, whereas creativity supplies a uniform escaping point for every proposed c.e. subset of the complement. A simple set that is incomplete, such as the kind produced later by the Friedberg-Muchnik method, is a boundary case showing that c.e. noncomputability plus immune complement need not provide this productive uniformity. The theorem does not say that every simple set is creative, and the next result shows why this distinction matters for Post's original strategy. [quotetheorem:5431] [citeproof:5431] The moving markers are essential. A computable infinite set cannot be reserved permanently outside $A$, because that set would itself be an infinite c.e. subset of the complement and would violate immunity. The theorem does not produce an intermediate set, but rather a counterexample to the idea that simplicity forces incompleteness. This result is the decisive warning against confusing noncomputability with intermediate degree. Simplicity proves $A >_T \varnothing$, but it does not prove $A <_T K$. [example: Two Independent Design Goals] The complete simple-set construction balances two different aims. The simplicity requirements make the constructed set meet every infinite c.e. set, while the coding requirements arrange enough stable information for the constructed set to compute the halting problem. The important conceptual point is that these aims are compatible only because the construction separates positive meeting actions from protected coding positions. The simplicity side is local: each infinite $W_e$ needs only one successful meeting with $A$. The coding side is global: it uses stable information in the constructed set to recover information about $K$. For the present discussion, the example should be read as a warning that noncomputability and completeness are controlled by different mechanisms, not as a proof sketch for the complete simple-set theorem. [/example] The conceptual lesson is that Post's problem requires two-sided control. We must force noncomputability, and we must also diagonalise against every attempted Turing reduction $K \le_T A$. To state the missing kind of control, we need requirements whose target is not a c.e. set $W_e$ but an oracle computation. The enemy is now a proposed procedure that reads finitely much of $A$ and tries to recover $K$ on every input, so the construction must create disagreement with each such procedure while preserving enough restraint for higher-priority computations. We write $\Phi_e^A$ for the $e$th oracle partial computable functional with oracle $A \subset \mathbb{N}$; when it is total as a characteristic function, it is viewed as a map $\mathbb{N} \to \{0,1\}$. The next requirement names the task of defeating one proposed oracle computation, so a full construction would need to satisfy all such requirements simultaneously. [definition: Incompleteness Requirement] For $e \in \mathbb{N}$, the incompleteness requirement $N_e$ is \begin{align*} N_e &: \Phi_e^A \ne K. \end{align*} [/definition] The requirements $N_e$ are not satisfied merely by putting elements into $A$. They require controlling oracle computations, preserving computations long enough to diagonalise against them, and injuring lower-priority plans when the oracle changes. [remark: From Simple Sets To Priority Arguments] Simple sets introduce the positive side of priority: satisfy countably many requirements by assigning witnesses in an effective construction. Post's problem needs the negative side as well: protect computations so that no oracle functional computes $K$ from the constructed set. The Friedberg-Muchnik construction combines both kinds of requirements and produces incomparable c.e. degrees, from which intermediate c.e. degrees follow. [/remark] ## Immunity As The Boundary Of The Method What exactly did the simple-set method achieve? It transformed the search for noncomputable c.e. sets into a combinatorial construction of immune complements. By definition, a set $A$ is simple exactly when $A$ is computably enumerable and $\mathbb N\setminus A$ is immune: the complement is infinite, but contains no infinite computably enumerable subset. That is a lasting idea, but its reach stops before degree incompleteness. The c.e. condition and the immune-complement condition both matter. A computable coinfinite set fails the immune-complement condition because its complement is an infinite c.e. set. Conversely, an arbitrary non-c.e. set with immune complement still fails to be simple in Post's sense because it does not give a c.e. degree. Thus the equivalence separates the two ingredients: c.e.-ness places $A$ inside the degree structure below $0_T'$, while immunity of the complement is the combinatorial reason that $A$ cannot be computable. The statement is definitional, but it records the exact boundary of the simple-set method. The equivalence lets us summarise the chapter in a precise way. Simple sets solve the problem of constructing noncomputable c.e. sets without directly coding the halting set; they do not solve the problem of locating a degree strictly below $0_T'$. [quotetheorem:5432] [citeproof:5432] The word "alone" is important: adding further requirements to a simple-set construction may produce an intermediate c.e. degree, but simplicity by itself permits both incomplete candidates and complete examples. The existence of complete simple sets is the counterexample to any attempted implication from simple to intermediate, while noncomputability of all simple sets explains why the property was still a serious first approximation. This boundary points directly to the Friedberg-Muchnik method, where requirements are designed to control oracle reductions rather than only c.e. subsets of a complement. This boundary is historically important because it explains why priority methods had to become more refined. The simple-set construction contributes the template of countably many requirements and witnesses; the solution to Post's problem adds restraints and injury to control oracle computations. [example: Reading The Simple Construction As A Template] For a fixed $e$, the simplicity requirement is \begin{align*} R_e &: W_e \text{ infinite } \implies W_e \cap A \ne \varnothing . \end{align*} Its target is the conclusion $W_e \cap A \ne \varnothing$ under the hypothesis that $W_e$ is infinite. Its witness is a number $x$ chosen from the finite stage approximation $W_{e,s}$ with \begin{align*} x \in W_{e,s}, \qquad x > 2e, \qquad x \notin A_s . \end{align*} Since $W_{e,s} \subseteq W_e$ and the construction enumerates this same $x$ into $A$, we have \begin{align*} x \in W_e \quad\text{and}\quad x \in A . \end{align*} Therefore \begin{align*} x \in W_e \cap A, \end{align*} so \begin{align*} W_e \cap A \ne \varnothing . \end{align*} After this one enumeration, $R_e$ is declared satisfied, so this requirement has completed its finite action. The same pattern reappears in later priority arguments: a requirement waits for a configuration, chooses a witness, and acts once the witness gives the desired disagreement or meeting property. The new feature is restraint. If a higher-priority requirement has produced an oracle computation such as \begin{align*} \Phi_i^{A_s}(n) = 0 \end{align*} using only oracle questions below some bound $u$, then preserving that computation means preventing later lower-priority actions from enumerating any number $y < u$ into $A$. Thus the later construction keeps the same witness-and-action template, but adds the rule that lower-priority witnesses must respect higher-priority protected initial segments. This is the passage from meeting c.e. sets, which proves combinatorial avoidance, to controlling oracle computations, which is needed for degree-theoretic diagonalisation. [/example] The chapter's main conclusion is therefore negative and positive at once. Negatively, simple, hypersimple, and hyperhypersimple sets do not by themselves solve Post's problem. Positively, they supply the first systematic priority constructions and reveal the distinction between being noncomputable, being immune in the complement, and being incomplete in Turing degree. Simple sets show that c.e. sets can be highly nontrivial, but they do not by themselves resolve the degree-theoretic questions raised by Post's problem. Chapter 8 takes up the construction methods needed to meet infinitely many requirements at once, organizing diagonalization into finite-injury priority arguments. # 8. Priority Arguments: Finite Injury Priority arguments answer a recurring problem in computability theory: how can we build a computably enumerable set while meeting infinitely many incompatible-looking diagonal requirements? Earlier constructions used one diagonal action at a time. In this chapter the construction is organised as a negotiation among requirements, where stronger requirements may disturb weaker ones, but each weaker requirement is eventually allowed to settle. The finite injury method is the first priority method in the course. It is strong enough to build simple sets with additional control, and it gives the working pattern behind later solutions to Post's problem. The central discipline is to separate the local strategy for one requirement from the global verification that every strategy is injured only finitely many times. ## Why Priority Is Needed The basic obstruction is that computably enumerable sets are built by positive action only: once a number is enumerated, it cannot be removed. A construction may therefore want to keep a number out of a set for the sake of one requirement, while another requirement wants to enumerate it. Priority gives a rule for deciding which demand wins at a given finite stage. [definition: Priority Requirement] A priority requirement is a condition $R_e$ imposed on the object being constructed, indexed by $e \in \mathbb N$, together with an intended strategy for ensuring that condition. [/definition] The index $e$ usually records the requirement's strength: $R_1$ has higher priority than $R_2$, and so on. This convention does not mean that lower-priority requirements are optional; it means that they must succeed after surviving the disturbances caused by stronger requirements. [example: Separating From A Computable Candidate] Fix one requirement $R_e$ and a reserved witness $x_e$. The intended diagonal condition is \begin{align*} A(x_e) \ne W_e(x_e), \end{align*} because one disagreement at a single number is enough to give $A \ne W_e$. At the stage when $x_e$ is chosen, the construction keeps $x_e \notin A$. If later a stage $s$ appears with $x_e \in W_{e,s}$, the strategy enumerates $x_e$ into $A$, so after that action \begin{align*} x_e \in A \quad\text{and}\quad x_e \in W_e. \end{align*} This does not diagonalise by itself; it only matches $W_e$ at $x_e$. The usual successful version instead uses the opposite convention: keep $x_e$ out of $A$ until it is safe to declare permanent restraint, and if the construction can ensure \begin{align*} x_e \notin A \quad\text{while}\quad x_e \in W_e, \end{align*} then $A$ and $W_e$ disagree at $x_e$. If a stronger requirement has already enumerated $x_e$ into $A$, then this planned disagreement is lost, because $x_e \in A$ is now permanent. Thus the witness method only works when the bookkeeping records which numbers are protected and forces an injured requirement to choose a fresh witness. [/example] The example shows why a single diagonal instruction is not enough. We need a bookkeeping mechanism that says which numbers are currently protected, when a protection is cancelled, and how a requirement recovers after a cancellation. [definition: Restraint] A restraint is a finite condition imposed by a strategy, usually of the form that some numbers below a bound $r$ must not be enumerated into the constructed c.e. set. [/definition] A restraint is the technical expression of a promise made to a strategy. If a stronger strategy later enumerates a number below that bound, the promise has been broken and the weaker strategy may need to choose fresh data. [definition: Injury] A requirement $R_e$ is injured at stage $s$ if an action by a higher-priority requirement at stage $s$ invalidates the current witness, restraint, or computation on which the strategy for $R_e$ depends. [/definition] Injury is not failure. It is a finite-stage event that forces a strategy to restart with fresh parameters. The finite injury method works when each requirement can tolerate finitely many restarts and still meet its goal. ## Strategies, Restraints, and Stage Constructions The practical question is how to turn the priority order into a construction that is computable stage by stage. At each stage we approximate the c.e. sets $W_e$, inspect a finite initial segment of the requirements, and let the highest-priority requirement needing attention act. [definition: Strategy] A strategy for a requirement $R_e$ is a partial computable stage procedure \begin{align*} \sigma_e:\{ \text{finite construction states} \}\times \mathbb N \rightharpoonup \{ \text{permitted finite actions} \} \end{align*} which, given the current finite approximation to the construction, the current finite approximations to the relevant c.e. sets, and the stage number, returns the next action prescribed for $R_e$ when such an action is available. [/definition] The strategy definition is intentionally operational. In finite injury constructions, the proof is not only that a final set has a property, but also that the construction is a computable enumeration procedure. [definition: Requires Attention] A requirement $R_e$ requires attention at stage $s$ if its current strategy has not yet reached a declared satisfied state and the stage procedure $\sigma_e$ is defined on the finite construction state at stage $s$. [/definition] After defining attention, the construction can be written as an algorithm. The typical rule is: at stage $s$, find the least $e < s$ such that $R_e$ requires attention, carry out its action, and initialise every lower-priority requirement $R_j$ with $j > e$. [definition: Initialisation] Initialisation of a requirement $R_j$ discards its active witness, restraint, and temporary data, and returns its strategy to its starting state. [/definition] Initialisation is how higher-priority action is propagated down the priority list. It keeps lower strategies from relying on information that may have been made unusable by a stronger strategy. [example: Two-Requirement Trace] Consider two requirements $R_1$ and $R_2$, with $R_1$ higher priority. At stage $1$, let $R_1$ choose a witness $x_1$ and impose the restraint that no lower-priority action may enumerate $x_1$ into $A$. At stage $2$, let $R_2$ choose a witness $x_2$ with $x_2>x_1$, so its witness is outside the number currently protected for $R_1$. Suppose that at stage $3$ the approximation to $W_1$ changes in the way required by the strategy for $R_1$, for example by showing that $x_1\in W_{1,3}$. Since $R_1$ has higher priority, the construction lets $R_1$ act first and enumerate $x_1$ into $A$: \begin{align*} A_3 = A_2 \cup \{x_1\}. \end{align*} The old data for $R_2$ was chosen under the earlier restraint configuration, so the stage-$3$ action of $R_1$ invalidates the active witness and restraint for $R_2$. Thus after stage $3$, $R_2$ no longer relies on $x_2$. At a later stage $t>3$, if $R_2$ again requires attention, it chooses a fresh witness $y_2$ above the current stronger restraint. If the new restraint bound imposed by $R_1$ is $r$, then the choice is made with \begin{align*} y_2>r, \end{align*} so any later action by $R_2$ using $y_2$ respects the computation or witness currently protected by $R_1$. This is the basic finite-injury pattern: the lower-priority requirement may lose its first witness, but after the higher-priority action has settled, it restarts with fresh data compatible with the stronger restraint. [/example] This trace contains the whole finite injury picture in miniature. The lower requirement may lose its first witness, but once the higher requirement has finished acting, the lower requirement can choose a new witness and is no longer disturbed by that particular cause. ## The Low Simple Set Construction We now use priority to meet two kinds of demands at once. Simplicity asks that a c.e. set be coinfinite but meet every infinite c.e. set. Lowness asks that the jump of the set carry no more information than the ordinary halting problem. [definition: Simple Set] A c.e. set $A \subseteq \mathbb N$ is simple if $\mathbb N \setminus A$ is infinite and $A \cap W_e \ne \varnothing$ for every infinite c.e. set $W_e$. [/definition] A simple set is a direct answer to Post's search for noncomputable c.e. sets: it is c.e. and not computable, because a computable coinfinite c.e. set would have an infinite computable complement, hence an infinite c.e. set disjoint from it. The next theorem shows that this can be achieved while keeping the jump low. [definition: Low Set] A set $A \subseteq \mathbb N$ is low if $A' \equiv_T \varnothing'$. [/definition] Lowness is a restraint condition on the jump: although $A$ may be noncomputable, computations relative to $A$ do not solve more halting problems than $\varnothing'$ already solves. The finite injury construction below is a model because the positive requirements making $A$ simple are balanced against negative requirements preserving computations. The two goals interfere. To make $A$ simple, the construction must enumerate witnesses into $A$ whenever infinite c.e. sets present them; to keep $A$ low, it must also prevent oracle computations from changing without control. The theorem is needed because neither property automatically preserves the other. [quotetheorem:5433] [citeproof:5433] The theorem is delicate because simplicity and lowness pull in opposite directions. Simplicity needs positive enumeration into $A$, while lowness needs computations relative to $A$ to stop changing after a finite stage. Each hypothesis rules out a genuine boundary case. If $A$ were not required to be c.e., the construction would no longer be a positive enumeration argument and the jump comparison would not follow from a computable stage approximation. If coinfinitude were dropped, the degenerate c.e. set $A=\mathbb N$ would meet every infinite $W_e$ but would not be simple, because simplicity is meant to produce a noncomputable c.e. set whose complement still survives. If the requirement were imposed on all nonempty $W_e$ rather than infinite $W_e$, no coinfinite $A$ could meet it: for any $x\notin A$, the finite c.e. set $\{x\}$ would be a missed target. The theorem also does not say that every simple set is low, nor that lowness is automatic for c.e. constructions. It shows that the finite injury method can coordinate enumeration and protection strongly enough to realise both properties at once. [example: A Single Positive Requirement Under Restraint] Fix $e$, and suppose that all stronger negative requirements currently protect computations whose oracle uses are $< r$. The positive requirement $P_e$ is \begin{align*} W_e \text{ infinite} \implies A \cap W_e \ne \varnothing . \end{align*} Its strategy waits for a stage $s$ and a fresh number $x$ such that \begin{align*} x \in W_{e,s}, \qquad x>r, \qquad x \text{ has not previously been chosen by this strategy}. \end{align*} When such an $x$ appears, the construction enumerates it into $A$, so \begin{align*} A_{s+1}=A_s\cup\{x\}. \end{align*} Since $x\in W_{e,s}$ and $W_{e,s}\subseteq W_e$, we have $x\in W_e$. Since $x\in A_{s+1}$ and the construction of $A$ is monotone, $x\in A$. Therefore \begin{align*} x\in A\cap W_e, \end{align*} so $P_e$ is met. It remains to justify that a suitable $x$ exists when $W_e$ is infinite. The forbidden numbers below the current restraint lie in the finite set \begin{align*} \{0,1,\dots,r\}, \end{align*} which has exactly $r+1$ elements. The strategy has also used only finitely many earlier witnesses. Hence the set of currently unavailable numbers is finite. If $W_e$ is infinite, then $W_e$ cannot be contained in this finite unavailable set, so there is some $x\in W_e$ with \begin{align*} x>r \end{align*} and $x$ fresh for this strategy. Since $W_e=\bigcup_s W_{e,s}$, that same $x$ appears in $W_{e,s}$ at some finite stage $s$, and the strategy eventually acts. Finally, choosing $x>r$ preserves the stronger protected computations: every protected computation has use $<r$, so its oracle questions are all numbers $<r$, while the only new enumeration made by this action is the number $x>r$. Thus this positive action meets $P_e$ without changing any oracle answer below the stronger restraint. [/example] The example explains why infinitude of $W_e$ is exactly the right hypothesis. A finite target set might never present a safe element, but an infinite c.e. set must eventually enumerate numbers above any fixed finite restraint. ## Verification Templates The main proof burden in a priority argument is not the stage construction itself. The burden is the verification: every requirement is met, every lower-priority process is injured only finitely many times, and the object produced by the stages belongs to the promised syntactic class. In practice this verification has a standard shape. Order the requirements by priority. Prove, by induction on that order, that each requirement is injured only finitely many times. After its last injury, show that its local strategy either acts successfully or no longer needs to act because the computation or enumeration it was waiting for never appears. Finally, check that all stage actions are generated by a computable finite procedure and that the constructed set is the union of its monotone finite approximations. The template isolates exactly where finite injury is used. If some higher-priority requirement acted infinitely often, a lower-priority strategy could be repeatedly returned to its starting state and might never keep a witness or restraint long enough to succeed; a construction in which $R_0$ toggles a marker at every stage gives the boundary case where no lower strategy has a last initialisation. If initialisation were allowed to come from lower-priority strategies, induction on priority would not apply, because $R_e$ could be injured by requirements not covered by the induction hypothesis. If the local success lemma failed, finite injury alone would be empty bookkeeping: a strategy could be left undisturbed forever while still waiting for a witness that never appears. Its value is that, after the local lemmas are proved, the global verification reduces to induction on the priority ordering. This induction proves satisfaction of requirements, but it does not by itself prove that the object produced by the construction has the promised syntactic form. In the low simple set argument, for instance, the priority verification shows that the requirements are met, while a separate check is needed to see that the stage-by-stage process really enumerates a c.e. set. [remark: C.e. Union Check] For an increasing computable approximation \begin{align*} A := \bigcup_{s=1}^{\infty} A_s, \end{align*} the set $A$ is c.e. when each finite difference $A_{s+1}\setminus A_s$ is effectively computable: an enumeration procedure prints those new elements stage by stage. [/remark] This second template is short but important. Priority arguments often look nonconstructive because their verification talks about eventual stability, but the enumeration itself must be generated by a computable finite procedure. The monotonicity and effectiveness hypotheses are the safeguards: with removals, a computable approximation may converge to a merely $\Delta^0_2$ set, and with non-effective finite differences the union could hide outside information such as $\varnothing'$. The check proves only that the final set is c.e.; it says nothing by itself about simplicity, lowness, or any of the priority requirements. [example: Checking Coinfinitude By Restraints] In a simple-set construction, one way to verify coinfinitude is to build a sequence of protected markers $m_0,m_1,m_2,\dots$ such that \begin{align*} m_n>n \end{align*} and the construction never enumerates $m_n$ into $A$. Then for every $n$ we have \begin{align*} m_n\in \mathbb N\setminus A \qquad\text{and}\qquad m_n>n. \end{align*} Thus $\mathbb N\setminus A$ is unbounded: given any bound $n$, the marker $m_n$ is a complement element larger than $n$. An unbounded subset of $\mathbb N$ is infinite. Indeed, if $\mathbb N\setminus A$ were finite, say \begin{align*} \mathbb N\setminus A=\{b_0,\dots,b_k\}, \end{align*} then the maximum \begin{align*} B=\max\{b_0,\dots,b_k\} \end{align*} would bound every element of $\mathbb N\setminus A$. But the marker condition with $n=B$ gives \begin{align*} m_B\in \mathbb N\setminus A \qquad\text{and}\qquad m_B>B, \end{align*} contradicting that $B$ is an upper bound. Therefore $\mathbb N\setminus A$ is infinite, so the construction avoids the degenerate outcome $A=\mathbb N$ while still allowing the positive requirements to enumerate selected witnesses into $A$. [/example] The point of this verification is that simplicity has two halves. Meeting every infinite $W_e$ makes $A$ immune to computable separation, while coinfinitude prevents the construction from taking the degenerate route $A=\mathbb N$. ## Sacks Splitting as a Preview Finite injury arguments do not stop with simple sets. They also explain how to divide computably enumerable information into two nontrivial pieces while preserving enough control to avoid computing the original set from either piece alone. The Sacks splitting theorem will be stated in the next chapter after the order-theoretic join operation has been introduced; here it serves as a signpost for why the finite-injury verification pattern is worth isolating. [remark: What Finite Injury Teaches] Finite injury priority arguments have a stable rhythm: assign requirements, give each requirement a local strategy, order the strategies, define injury and initialisation, then verify by induction on priority. Later priority methods change the shape of the injury, but they keep this separation between local action and global bookkeeping. [/remark] The chapter's reusable lesson is therefore methodological. A priority construction is not a bag of diagonal tricks; it is a controlled finite-stage process whose correctness comes from the interaction between restraints, injuries, and induction over the priority ordering. Finite-injury priority arguments supply the method, and the Friedberg-Muchnik theorem is the first major success of that method. Chapter 9 applies the framework to build incomparable c.e. degrees, showing how careful bookkeeping can solve Post's problem without sacrificing computable enumerability. # 9. Friedberg-Muchnik Theorem Chapter 8 introduced finite-injury priority arguments as a method for building computably enumerable sets while meeting countably many competing requirements. This chapter assumes the basic theory of computably enumerable sets, Turing reductions, oracle computations, and the halting problem degree $0'$. It applies those tools to Post's problem: whether there is a computably enumerable Turing degree strictly between the computable degree and the halting problem degree. The answer is yes, and the Friedberg-Muchnik construction gives two computably enumerable sets whose degrees are incomparable, so neither can compute the other. The central difficulty is not diagonalisation by itself. A single computation can be destroyed by enumerating one carefully chosen number, but higher-priority requirements may later enumerate numbers that lower-priority requirements were relying on. The finite-injury method organises these conflicts by assigning restraints, allowing each requirement to be injured only finitely many times. ## Post's Problem and Incomparability Requirements Post's problem asks whether every noncomputable computably enumerable set is Turing complete. To refute that possibility, it is enough to build two c.e. sets $A$ and $B$ such that $A \nleq_T B$ and $B \nleq_T A$. Since both sets are c.e., they will automatically satisfy $A \leq_T K$ and $B \leq_T K$, where $K$ is the halting problem. [definition: Turing Incomparable Sets] Let $A,B \subseteq \mathbb N$. The sets $A$ and $B$ are Turing incomparable if $A \nleq_T B$ and $B \nleq_T A$. [/definition] This definition turns Post's problem into a pair of negative reduction tasks. Instead of trying to measure the exact degree of one set, we build two sets that defeat every possible oracle computation from one to the other. [definition: Friedberg-Muchnik Requirements] Fix effective listings $(\Phi_e)_{e \in \mathbb N}$ and $(\Psi_e)_{e \in \mathbb N}$ of oracle Turing functionals, where each functional is a partial map \begin{align*} \Phi_e &: 2^{\mathbb N} \times \mathbb N \rightharpoonup \{0,1\}, & \Psi_e &: 2^{\mathbb N} \times \mathbb N \rightharpoonup \{0,1\}. \end{align*} For an oracle set $C \subseteq \mathbb N$, write $\Phi_e^C(x)$ and $\Psi_e^C(x)$ for the corresponding partial computations on input $x$. The Friedberg-Muchnik construction uses the requirements \begin{align*} \mathcal R_e &: \Phi_e^A \neq B, \\ \mathcal S_e &: \Psi_e^B \neq A, \end{align*} for each $e \in \mathbb N$. [/definition] The requirements are symmetric: $\mathcal R_e$ prevents $B$ from being computed from $A$, while $\mathcal S_e$ prevents $A$ from being computed from $B$. The possible gap is that each requirement only mentions one proposed oracle functional, while Turing reducibility is an existential claim over all such functionals. To prove incomparability, the whole countable scheme must block every possible reduction in both directions. [quotetheorem:5434] [citeproof:5434] The hypotheses that $A$ and $B$ satisfy every indexed requirement are essential: satisfying only finitely many requirements would merely rule out finitely many proposed reductions, while a later functional could still compute one set from the other. For example, if $A=B=K$, then many individual diagonal requirements can be met by accident, but $A \leq_T B$ and $B \leq_T A$ still hold. The theorem does not construct the sets or prove that the requirements are jointly consistent; it only explains why meeting the whole scheme is enough. The construction therefore becomes a controlled way of satisfying each individual requirement. We first isolate what a single requirement wants to do, and then explain why doing this independently for all requirements creates conflicts. ## Diagonalisation With Witnesses How can a single requirement $\mathcal R_e$ force $\Phi_e^A \neq B$? The usual diagonal strategy is to choose a fresh witness $x$ and try to arrange disagreement at $x$. Since $B$ is under construction, the requirement waits for a computation predicting that $x \notin B$, then enumerates $x$ into $B$ while protecting the oracle information used in that computation. [definition: Witness for a Requirement] A witness for $\mathcal R_e$ is a natural number $x$ reserved by $\mathcal R_e$ for producing a disagreement between $\Phi_e^A(x)$ and $B(x)$. A witness for $\mathcal S_e$ is defined symmetrically, with $A$ and $B$ interchanged. [/definition] A witness is not useful merely because it is large or unused. It becomes useful when the relevant oracle computation converges, and the upcoming definition is needed to name the finite oracle segment that must be protected after convergence. [definition: Use of an Oracle Computation] Let $\Phi_e:2^{\mathbb N} \times \mathbb N \rightharpoonup \{0,1\}$ be an oracle Turing functional, let $A \subseteq \mathbb N$ be an oracle set, and let $x \in \mathbb N$. If $\Phi_e^A(x)$ converges at a finite stage using only oracle questions below $u$, then $u$ is called the use of that computation at that stage. [/definition] The use is the finite part of the oracle that must remain unchanged for the computation to remain valid. In the c.e. setting, oracle answers can only change from no to yes, so preserving a computation means forbidding new enumerations below its use. [example: A Single Friedberg-Muchnik Requirement] Suppose $\mathcal R_e$ has chosen a fresh witness $x$ at stage $s$, with $x \notin B_s$. At a later stage $t$, assume that \begin{align*} \Phi_{e,t}^{A_t}(x)=0 \end{align*} and that this computation has use $u$, meaning that during the computation the oracle $A_t$ is queried only below $u$. The requirement then enumerates $x$ into $B$, so at the next stage after the action, \begin{align*} B(x)=1. \end{align*} Now suppose that no later number below $u$ enters $A$. Then for every $n<u$, the oracle answer to the question "$n \in A$?" is the same in the final oracle $A$ as it was in the finite oracle $A_t$. Since the computation of $\Phi_{e,t}^{A_t}(x)$ only used those oracle answers, the same computation still runs with the same answers in the final oracle, and hence \begin{align*} \Phi_e^A(x)=0. \end{align*} Therefore \begin{align*} \Phi_e^A(x)=0 \neq 1=B(x), \end{align*} so $\Phi_e^A \neq B$. The restraint $u$ is exactly the finite promise needed to keep the diagonalising computation valid. [/example] This example shows the local diagonal move. The next issue is that imposing restraint on $A$ may prevent some requirement for $A$ from acting, while enumerating into $B$ may destroy computations that other requirements were protecting. [example: Failure of Diagonalisation Without Restraint] Let $\mathcal R_e$ choose a witness $x$ with $x \notin B_s$, and suppose it acts at stage $s$ because \begin{align*} \Phi_{e,s}^{A_s}(x)=0 \end{align*} with use $u$. Acting means that $x$ is enumerated into $B$, so after this action \begin{align*} B(x)=1. \end{align*} Now suppose a later requirement enumerates some $y<u$ into $A$. Before that later action, \begin{align*} y \notin A_s, \end{align*} while in the final oracle, \begin{align*} y \in A. \end{align*} Thus the oracle answer to the query "$y \in A$?" has changed from $0$ at stage $s$ to $1$ in the final set $A$. Since $y<u$, this changed answer lies inside the finite oracle segment that the computation $\Phi_{e,s}^{A_s}(x)=0$ was allowed to query. Therefore the original computation is no longer guaranteed to run with the same oracle answers in $A$: \begin{align*} \Phi_{e,s}^{A_s}(x)=0 \end{align*} does not imply \begin{align*} \Phi_e^A(x)=0. \end{align*} It may happen instead that $\Phi_e^A(x)=1$, in which case \begin{align*} \Phi_e^A(x)=1=B(x), \end{align*} so the intended disagreement at $x$ has disappeared. The failure is exactly the loss of control over the finite oracle information below the use $u$. [/example] The word "restraint" refers to exactly this memory. A requirement that has acted can demand that lower-priority requirements avoid changing the relevant initial segment of the opposite oracle. ## Priority Ordering and Restraints How do we allow every requirement to act while preventing incompatible promises? The solution is to linearly order the requirements by priority and permit higher-priority requirements to injure lower-priority ones. A lower-priority requirement must choose witnesses beyond all restraints currently imposed on the set it wants to enumerate into. [definition: Priority Ordering] The Friedberg-Muchnik requirements are ordered as \begin{align*} \mathcal R_0,\mathcal S_0,\mathcal R_1,\mathcal S_1,\mathcal R_2,\mathcal S_2,\dots . \end{align*} A requirement earlier in this list has higher priority than a requirement later in the list. [/definition] Priority is not a measure of importance; it is a bookkeeping convention that makes conflicts decidable during the construction. When a requirement acts, it may depend on a finite initial segment of an oracle set remaining unchanged. The construction therefore needs a precise way to record which lower-priority enumerations are temporarily forbidden so that the computation just protected is not immediately destroyed. [definition: Restraint] At a finite stage, a requirement imposes restraint $r$ on a c.e. set $C$ if lower-priority requirements are forbidden from enumerating numbers below $r$ into $C$ unless they are first reset by a higher-priority action. [/definition] A restraint is finite because every oracle computation uses only finitely many oracle answers. Restraints explain how computations are preserved, but they also create the possibility that a later action invalidates a lower-priority strategy's current plan; the next definition is needed for that kind of disruption. [definition: Injury] A requirement is injured when a higher-priority requirement acts in a way that cancels its current witness, removes its current restraint, or changes the oracle segment on which its protected computation depended. [/definition] After injury, a requirement starts over with a new large witness. The proof of the construction will show that each requirement is injured only finitely many times, so this restarting process eventually stops for every fixed requirement. ## The Finite-Injury Construction What should happen at a stage of the construction? We inspect the requirements in priority order and let the first requirement that is ready to act perform its diagonal move. All lower-priority requirements that conflict with that move are then initialised, so their old witnesses and restraints no longer count. [definition: Readiness] A requirement $\mathcal R_e$ with current witness $x$ is ready at stage $s$ if $x \notin B_s$ and there is a computation $\Phi_{e,s}^{A_s}(x)=0$ with use $u$. A requirement $\mathcal S_e$ with current witness $y$ is ready at stage $s$ if $y \notin A_s$ and there is a computation $\Psi_{e,s}^{B_s}(y)=0$ with use $v$. [/definition] Readiness is a finite-stage condition, so it can be checked effectively during the construction. The remaining difficulty is coordination: several requirements may have witnesses, protected computations, and restraints at the same finite stage, but acting on all of them at once could destroy earlier commitments. A workable construction must choose actions effectively, respect higher-priority restraints, and reset only the lower-priority data that has become unreliable. [quotetheorem:5435] [citeproof:5435] The fixed listings are needed because the construction must confront every possible oracle algorithm, not a selected subfamily. If a functional were absent from the list, the final sets might still be reducible by precisely that absent computation. The construction records enough information to coordinate the requirements effectively, and the next section verifies that this coordination succeeds: each fixed requirement is reset only finitely many times, and after its final reset it either acts successfully or wins because the attempted computation never appears. ## Verification of the Requirements The proof details live in the theorem's proof accordion; the page-level point is the architecture. The construction is arranged so that higher-priority strategies may reset lower-priority ones, but each fixed requirement has only finitely many stronger requirements above it. Once those stronger strategies have settled, the lower requirement works in a stable environment. This stable-tail viewpoint is what finite injury contributes. It separates temporary failed plans from final outcomes: a requirement may lose early witnesses or restraints, but after its last reset it either obtains a preserved diagonal disagreement or the attempted computation it was waiting for never materializes. The formal verification checks these alternatives requirement by requirement; the exposition here keeps only the guiding structure needed for the rest of the course. The final-injury hypothesis supplied by the previous lemma is essential. Without a stable witness, a requirement could diagonalise at one stage and later lose the computation it was preserving when the opposite oracle changes below the use; the earlier example of enumerating below a protected use is the model counterexample. The theorem does not say that the construction avoids all temporary failures, only that every temporary plan is eventually replaced by a final successful one or by a permanent absence of the relevant computation. This is the point at which priority arguments differ from ordinary diagonal arguments. The witness is not merely chosen and used; it is chosen, used, protected, and then shown to remain protected after finitely many injuries. ## Post's Problem Solved The construction gives two c.e. sets that are not reducible to each other. To connect this with Post's original question, we also record where their degrees sit in the Turing degrees. [remark: Incomparable C.E. Degrees] The Friedberg-Muchnik construction produces computably enumerable sets $A$ and $B$ with $A\nleq_T B$ and $B\nleq_T A$. [/remark] The c.e. hypothesis is part of the content, not decoration: arbitrary incomparable Turing degrees can be obtained by less delicate methods, while Post's problem asks specifically about degrees below $0'$. The theorem also does not identify the exact degree of either set, and it does not claim uniqueness of the construction; many priority constructions can produce different incomparable c.e. degrees. Its role is to supply the raw incomparability needed to extract an intermediate c.e. degree. The theorem is stronger than merely producing a single intermediate degree. It gives two different c.e. degrees below the halting problem degree which cannot be compared by Turing reducibility. [remark: Post's Problem Consequence] In particular, at least one of the constructed c.e. degrees gives a degree strictly between $0$ and $0'$, so Post's problem has a positive solution. [/remark] The noncomputability and noncompleteness arguments both use incomparability. If $A$ and $B$ were merely distinct c.e. sets, $A$ could still be computable or complete; for instance, $K$ and $K \oplus \varnothing$ are distinct c.e. sets but have the same complete degree. The result does not classify all intermediate c.e. degrees, but it proves that the c.e. degrees are not collapsed into only $0$ and $0'$. This completes the course's first major application of finite injury. The construction answers Post's problem and introduces the template used throughout later recursion theory: write requirements, assign priority, protect finite computations by restraints, and verify that every requirement eventually has a stable outcome. The same template explains why the Friedberg-Muchnik theorem became a starting point rather than an endpoint. Splitting arguments refine the construction by asking for a c.e. degree to be decomposed into two strictly smaller pieces, so the requirements must preserve not only incomparability but also information about joins. Definability questions in the c.e. degrees use priority constructions to build degrees with prescribed order-theoretic behaviour, turning finite injury into a way of controlling how a constructed degree sits among many others. Stronger priority arguments, such as infinite-injury constructions, keep the same language of witnesses, restraints, and outcomes, but replace the finite-injury verification with more elaborate bookkeeping because a fixed requirement may be affected infinitely often while still having a limiting strategy. The Friedberg-Muchnik construction proves that the c.e. degrees are far from linear, but the deeper question is how much more structure they contain. Chapter 10 studies that internal geometry, using the same priority technology to analyze splitting, density, minimal pairs, and jump-related refinements. # 10. Structure of the c.e. Degrees Chapters 7 through 9 developed c.e. sets, Turing reducibility, the jump, and finite-injury priority arguments as tools for separating computational power and solving Post's problem. This chapter turns those tools back onto the partially ordered structure of the c.e. degrees themselves. The main question is no longer whether a particular set is computable, but how c.e. degrees sit above, below, and beside one another under Turing reducibility. The c.e. degrees form a rich interval between the computable degree $0$ and the halting degree $0'$. They have enough structure to support splitting and density, but not enough structure to behave like a lattice with every finite pattern present. The priority method is the central construction technique, and the chapter also marks the point where finite injury stops being the whole story. ## Splitting and Minimal Pair Phenomena What does it mean for a noncomputable c.e. problem to be decomposable into two weaker noncomputable parts? Post's problem asked whether there is a c.e. degree strictly between $0$ and $0'$, and the later structure theory asks the sharper question of how many ways intermediate degrees can be arranged. Splitting theorems show that nonzero c.e. degrees are not indivisible atoms. [definition: C.e. Degree] A c.e. degree is a Turing degree containing at least one computably enumerable set. [/definition] The elements of the c.e. degrees are ordered by $a \leq b$ when some, equivalently every, representative of $a$ is Turing reducible to some representative of $b$. In these notes we write $0$ for the computable degree and $0'$ for the degree of the halting problem. [example: The Extremal C.e. Degrees] The degree $0$ contains exactly the computable sets, so the computable c.e. sets $\varnothing$ and $\mathbb N$ both represent $0$: membership in $\varnothing$ is always answered “no,” and membership in $\mathbb N$ is always answered “yes.” Let $K$ be the halting problem, so $K \in 0'$. If $A$ is c.e., fix an index $e$ for a machine enumerating $A$. To decide whether $x \in A$ using oracle $K$, build a program $P_{e,x}$ which runs the enumeration of $A$ and halts exactly when $x$ appears. Then \begin{align*} x \in A &\Longleftrightarrow \text{the enumeration of } A \text{ eventually lists } x \\ &\Longleftrightarrow P_{e,x} \text{ halts} \\ &\Longleftrightarrow \langle P_{e,x}\rangle \in K. \end{align*} Since the map $x \mapsto \langle P_{e,x}\rangle$ is computable, this gives a Turing reduction $A \leq_T K$. Hence every c.e. degree is below $0'$, while the computable c.e. sets have degree $0$; the c.e. degrees therefore lie in the interval $[0,0']$ of the full Turing degrees. [/example] The example identifies the ambient interval, but it does not yet describe how degrees inside that interval combine. The next definition records the order-theoretic operation that priority constructions often aim to control. It is not enough to build two incomparable c.e. sets; to split a degree, their join must recover exactly the original computational content. [definition: Join of Degrees] The join operation on Turing degrees is the map \begin{align*} \vee : \mathcal D_T \times \mathcal D_T \to \mathcal D_T \end{align*} defined by \begin{align*} (a,b) \mapsto a \vee b = \deg_T(A \oplus B), \end{align*} where $A \in a$, $B \in b$, and \begin{align*} A \oplus B = \{2n : n \in A\} \cup \{2n+1 : n \in B\}. \end{align*} [/definition] The join is the least upper bound in the full Turing degrees, and it remains the natural way to combine c.e. information. Splitting asks whether a degree can be expressed as the join of two strictly smaller nonzero degrees. Sacks splitting answers yes: if $a$ is a nonzero c.e. degree, then there are nonzero c.e. degrees $b,c<a$ with $a=b\veec$. The hypothesis $a \neq 0$ is essential: the computable degree cannot be split into two nonzero degrees below it, since every c.e. degree below $0$ is itself $0$. The theorem also does not say that an arbitrary pair of c.e. degrees below $a$ gives a splitting; the construction must coordinate the enumeration so that the join recovers $A$ while each side remains too weak to compute $A$ alone. Nor does splitting make the interval below $a$ into a lattice with all finite patterns, since later nondensity phenomena impose global restrictions. Thus the theorem gives a strong local decomposition principle, and the next question asks for the opposite kind of control: arranging two nonzero degrees so that their common c.e. information is only computable. To express that downward separation, we need the following order-theoretic notion. [definition: Minimal Pair] Two nonzero c.e. degrees $a$ and $b$ form a minimal pair if their greatest lower bound in the c.e. degrees is $0$; that is, every c.e. degree $c$ satisfying $c \leq a$ and $c \leq b$ is $0$. [/definition] A minimal pair is not a pair of minimal degrees. It is a pair whose common c.e. information collapses to computable information. The existence of such pairs is not forced by incomparability alone, since two incomparable degrees may still share a nonzero lower c.e. degree. Lachlan's minimal-pair theorem says that priority constructions can force the common lower cone to be as small as possible: there exist c.e. degrees $a$ and $b$ forming a minimal pair. The requirement that both degrees be nonzero matters: if one side were $0$, the pair would satisfy the lower-bound condition for the uninteresting reason that $0$ lies below every degree. The theorem also does not say that incomparable c.e. degrees automatically form a minimal pair; two incomparable degrees may still share a nonzero c.e. degree below them, for example if they both lie above a fixed nonzero degree obtained earlier in a splitting construction. Conversely, a minimal pair is a statement about common lower bounds, not about the existence or behaviour of a join above the pair. Together, splitting and minimal pairs show that the c.e. degrees are neither a chain nor a simple tree: a degree can divide into incomparable pieces, while two nonzero degrees can still have no nonzero common c.e. part. [example: Splitting Versus Minimal Pair] Suppose $a=b\veec$ is a Sacks splitting of a nonzero c.e. degree, so \begin{align*} b<a, \qquad c<a, \qquad a=b\veec. \end{align*} If $b\leq c$, then $c$ is an upper bound for both $b$ and $c$. Since $b\veec$ is the least upper bound, \begin{align*} b\veec\leq c. \end{align*} Also $c\leq b\veec$ because the join is an upper bound, so \begin{align*} b\veec=c. \end{align*} Thus \begin{align*} a =b\veec =c, \end{align*} contradicting $c<a$. The same argument with $b$ and $c$ interchanged shows that $c\leq b$ would imply $a=b$, contradicting $b<a$. Hence the two pieces in a splitting must be incomparable. By contrast, for a minimal pair $p,q$, the defining condition points downward. If a c.e. set $D$ is computable from representatives $P\inp$ and $Q\inq$, then \begin{align*} \deg_T(D)\leq p \qquad\text{and}\qquad \deg_T(D)\leq q. \end{align*} Since $p$ and $q$ form a minimal pair, every c.e. degree below both is $0$, so \begin{align*} \deg_T(D)=0. \end{align*} Therefore $D$ is computable. Splitting controls how two smaller degrees combine upward to recover a given degree, while minimal pairs control how little c.e. information two nonzero degrees can share below them. [/example] ## Density and Nondensity Patterns Given two c.e. degrees $a < b$, must there be another c.e. degree strictly between them? Density asks whether the order has gaps. Sacks density says that if $a$ and $b$ are c.e. degrees with $a<b$, then there is a c.e. degree $c$ with $a<c<b$. Thus the c.e. degrees have a strong positive density theorem, but the same structure blocks certain finite lattice patterns. The course states Sacks Density as a landmark theorem rather than developing the full construction. The proof uses a priority argument relative to representatives of $a$ and $b$ and builds an intermediate c.e. set whose degree is forced above $a$ but prevented from reaching $b$. The strict hypothesis $a < b$ is part of the content, not a technical decoration. If $a=b$, then no degree can lie strictly between them, so density is a statement only about genuinely nondegenerate intervals. The theorem also does not assert that the interval has a canonical midpoint, a least intermediate degree, or an intermediate degree with any prescribed jump behaviour; it gives existence inside the order and leaves finer properties to additional construction. This distinction matters later because density supplies many comparable degrees, while the nondiamond theorem shows that the same order still forbids certain finite lattice-shaped initial segments. [example: No Adjacent C.e. Degrees] Let $A$ and $B$ be c.e. sets with c.e. degrees $a<b$. By *Sacks Density Theorem* applied to the strict interval from $a$ to $b$, there is a c.e. degree $c$ such that \begin{align*} a<c<b. \end{align*} Choose a c.e. set $C$ with $\deg_T(C)=c$. The two displayed inequalities mean, explicitly, that \begin{align*} a\leq c, \qquad a\neq c, \end{align*} and \begin{align*} c\leq b, \qquad c\neq b. \end{align*} Since $a<c$ is again a strict inequality between c.e. degrees, applying *Sacks Density Theorem* to that smaller interval gives a c.e. degree $d$ with \begin{align*} a<d<c. \end{align*} Likewise, since $c<b$ is strict, applying *Sacks Density Theorem* to the interval from $c$ to $b$ gives a c.e. degree $e$ with \begin{align*} c<e<b. \end{align*} Thus every strict c.e. degree interval contains another c.e. degree strictly inside it, so the c.e. degrees have no immediate successor steps. [/example] Density might suggest that the c.e. degrees are order-theoretically flexible. To state the first obstruction cleanly, we isolate the finite lattice pattern that would combine a minimal pair with a common top. [definition: Diamond Lattice] A diamond lattice is the four-element lattice with least element $0$, greatest element $1$, and two incomparable middle elements $p$ and $q$ satisfying \begin{align*} p \wedge q = 0, \qquad p \vee q = 1. \end{align*} [/definition] The diamond is the smallest finite lattice pattern combining a nonzero minimal pair with a common join. Since the c.e. degrees have both splitting and minimal pairs, it is natural to ask whether a diamond can appear as the complete lower structure beneath some c.e. degree. Lachlan's nondiamond theorem says that this tempting picture is forbidden: the diamond lattice cannot be embedded as an initial segment of the c.e. degrees. Its proof is an infinite injury argument showing that any attempted diamond-shaped initial segment must produce additional c.e. degrees below the proposed top or collapse part of the proposed lattice relation. The initial-segment hypothesis is essential to what the theorem rules out. It says not only that four named degrees have the order relations of a diamond, but that every c.e. degree below the proposed top is already one of those four degrees. Without that closure condition, the statement would be much stronger than the theorem: it would try to forbid local configurations whose surrounding interval may contain extra degrees. The theorem therefore does not rule out every embedding of a diamond-shaped partial order into the c.e. degrees, nor does it deny the existence of minimal pairs or joins in particular cases. Its force is that the c.e. degrees cannot have the whole lower cone below a c.e. degree look exactly like the four-element diamond. [remark: Density Does Not Imply Lattice Freedom] Sacks Density controls intervals of the order, while the nondiamond theorem controls finite patterns involving meets and joins. These are logically different kinds of structure. A partial order may be dense and still forbid a particular finite lattice as an initial segment. [/remark] The nondiamond theorem is also a guide to the limitations of intuitive pictures. The c.e. degrees are crowded between any two comparable degrees, yet they still remember computability-theoretic constraints imposed by enumeration and injury. [example: Why the Diamond Is Stronger Than a Minimal Pair] A minimal pair consists of nonzero c.e. degrees $p$ and $q$ such that every c.e. degree below both is computable. Equivalently, if $d$ is c.e. and \begin{align*} d\leq p \qquad\text{and}\qquad d\leq q, \end{align*} then \begin{align*} d=0. \end{align*} This only controls common lower bounds of $p$ and $q$. A diamond initial segment would require more data. It would require a c.e. degree $r$ with \begin{align*} p\leq r, \qquad q\leq r, \end{align*} and it would require the entire lower cone below $r$ to contain no c.e. degrees except the four named ones: \begin{align*} \{d : d\text{ is c.e. and }d\leq r\} = \{0,p,q,r\}. \end{align*} Thus a diamond initial segment includes the minimal-pair condition \begin{align*} p\wedge q=0, \end{align*} but also asserts that $p$ and $q$ have a common top $r$ and that no fifth c.e. degree appears anywhere below that top. The *Lachlan Nondiamond Theorem* says this extra whole-interval demand is impossible in the c.e. degrees, so minimal pairs exist but cannot be completed into a four-element diamond initial segment. [/example] ## Low and High C.e. Degrees How can two c.e. degrees both be incomplete while still differ in their computational strength? The jump operator provides a second axis of comparison. Instead of asking only where $a$ sits below $0'$, we ask how complicated the halting problem relative to a representative of $a$ is. [definition: Low C.e. Degree] A c.e. degree $a$ is low if, for some c.e. set $A \in a$, \begin{align*} A' \equiv_T 0'. \end{align*} [/definition] Lowness says that using $A$ as an oracle does not raise the jump beyond the ordinary halting problem. This is a refinement of incompleteness: a low c.e. degree can be noncomputable but still have weak jump. [example: Interpreting a Low C.e. Degree] Let $A$ be a noncomputable c.e. set of low degree. Noncomputable means \begin{align*} A \not\leq_T \varnothing, \end{align*} so membership in $A$ cannot be decided by an ordinary algorithm. Lowness says that the jump of $A$ has exactly the same Turing degree as the ordinary halting problem: \begin{align*} A' \equiv_T 0'. \end{align*} Unpacking the equivalence gives both reductions \begin{align*} A' \leq_T 0' \qquad\text{and}\qquad 0' \leq_T A'. \end{align*} Thus an oracle for $0'$ can decide the halting problem relative to $A$, and an oracle for $A'$ can decide the ordinary halting problem. So $A$ itself may contain noncomputable information, but passing from $A$ to its jump does not move beyond the degree $0'$. Lowness measures weakness at the level of the relative halting problem $A'$, not computability of $A$ itself. [/example] The opposite refinement asks for c.e. degrees whose jump reaches the next possible level. For c.e. sets, every jump is bounded above by $0''$, so highness is maximal jump complexity among c.e. degrees. [definition: High C.e. Degree] A c.e. degree $a$ is high if, for some c.e. set $A \in a$, \begin{align*} A' \geq_T 0''. \end{align*} [/definition] Since $A \leq_T 0'$ for c.e. $A$, we have $A' \leq_T 0''$. Thus in the c.e. setting highness is the same as $A' \equiv_T 0''$. [example: Comparing Highness and Lowness] Let $A$ be a low c.e. set and $B$ a high c.e. set. Lowness gives \begin{align*} A' \equiv_T 0', \end{align*} which means exactly that \begin{align*} A' \leq_T 0' \qquad\text{and}\qquad 0' \leq_T A'. \end{align*} Thus the relative halting problem for $A$ has the same degree as the ordinary halting problem. Highness gives \begin{align*} B' \geq_T 0'', \end{align*} that is, \begin{align*} 0'' \leq_T B'. \end{align*} Since $B$ is c.e., we have \begin{align*} B \leq_T 0'. \end{align*} By monotonicity of the jump under Turing reducibility, \begin{align*} B' \leq_T (0')'. \end{align*} Since $(0')'=0''$, this becomes \begin{align*} B' \leq_T 0''. \end{align*} Combining the two inequalities, \begin{align*} 0'' \leq_T B' \qquad\text{and}\qquad B' \leq_T 0'', \end{align*} so \begin{align*} B' \equiv_T 0''. \end{align*} The contrast is therefore not about whether $B$ computes $0'$; it is that the jump of $B$ reaches the full second-jump degree, while the jump of a low c.e. set remains at $0'$. [/example] The comparison shows that jump complexity gives a finer scale than incompleteness alone. A natural question is whether noncomputable objects arising from effective compactness can be chosen with low jump, rather than carrying unnecessary jump complexity. The Low Basis Theorem answers this question in a setting adjacent to the c.e. degrees. [quotetheorem:5436] [citeproof:5436] The theorem is stated here for orientation, since its usual proof belongs to the theory of effectively closed classes rather than to the internal order theory of c.e. degrees. Its relevance is conceptual: low objects can often be chosen even when a construction seems to require noncomputable information. The nonemptiness hypothesis is necessary because an empty $\Pi^0_1$ class has no member to choose, low or otherwise. The $\Pi^0_1$ hypothesis is also doing real work: effectively closed classes have computable trees whose paths can be controlled by basis arguments, while arbitrary nonempty classes of reals need not support that kind of effective approximation. The theorem does not say that every c.e. degree contains a low representative, and it does not produce a c.e. set in general; the member of the class may be non-c.e. This is why the result is used here as a comparison point for lowness rather than as an internal classification theorem for the c.e. degrees. [remark: Lowness Is Not Computability] A low set need not be computable. Lowness compares jumps, so it says that the oracle $A$ does not add power to the halting problem after one jump. It does not say that membership in $A$ can be decided without an oracle. [/remark] ## Prompt Simplicity and Minimal Degrees Which c.e. degrees behave as if their enumerations respond quickly to computational pressure? Simplicity and promptness are not only properties of sets; they also feed into degree-theoretic refinements. They measure how a c.e. set meets infinite c.e. sets and how quickly it can do so along an enumeration. [definition: Simple Set] A c.e. set $A \subset \mathbb N$ is simple if $A$ is coinfinite and every infinite c.e. set intersects $A$. [/definition] Simple sets were Post's first attempt to solve the intermediate-degree problem. They are noncomputable because their complements are immune, but simplicity alone does not determine the Turing degree. [example: Simple Does Not Determine Degree] Let $S$ be an incomplete simple c.e. set and let $T$ be a complete simple c.e. set; these exist by the standard simple-set constructions. Since $S$ is incomplete, \begin{align*} 0' \not\leq_T S, \end{align*} while completeness of $T$ means \begin{align*} 0' \leq_T T. \end{align*} Because $T$ is c.e., every c.e. set is below $0'$, so in particular \begin{align*} T \leq_T 0'. \end{align*} Thus \begin{align*} T \equiv_T 0', \end{align*} but $S \not\equiv_T 0'$. Hence two simple c.e. sets can have different c.e. degrees. What simplicity asserts is only that $A$ is coinfinite and that every infinite c.e. set $W_e$ satisfies \begin{align*} W_e \cap A \neq \varnothing. \end{align*} This condition controls how $A$ meets c.e. subsets that try to stay inside its complement; it does not determine which oracle computations $\Phi_e^A$ are possible. Therefore simplicity is an immunity-style property of a representative set, not a complete invariant of its c.e. degree. [/example] The example shows that ordinary simplicity is too coarse to locate a c.e. set in the degree structure. The next definition is needed because it adds a timing requirement to the act of meeting infinite c.e. sets. Instead of recording only that $A$ eventually intersects each infinite $W_e$, prompt simplicity records that the meeting occurs with a computable bound on the waiting time. [definition: Promptly Simple Set] A c.e. set $A$ is promptly simple if $A$ is coinfinite and, for fixed computable stage enumerations $(A_s)_{s \in \mathbb N}$ and $(W_{e,s})_{s \in \mathbb N}$ with $A=\bigcup_s A_s$ and $W_e=\bigcup_s W_{e,s}$, there exists a computable nondecreasing function $p: \mathbb N \to \mathbb N$ such that for every index $e$, if $W_e$ is infinite, then there is an element $x$ and a stage $s$ with \begin{align*} x \in W_{e,s} \setminus W_{e,s-1}, \qquad x \in A_{p(s)}. \end{align*} [/definition] Promptness is a timing condition. It says that when an infinite c.e. set offers a new element, $A$ can meet it within a computably bounded delay along the chosen enumeration. Since degree theory classifies sets up to Turing equivalence, the next question is whether a degree contains at least one representative with this prompt behaviour. [definition: Promptly Simple Degree] A c.e. degree $a$ is promptly simple if it contains a promptly simple set. [/definition] This definition is degree-theoretic because promptness can be arranged inside certain degrees and obstructed in others. It becomes useful when comparing definable subclasses of c.e. degrees. [remark: Minimal Degrees and C.e. Degrees] There are minimal nonzero Turing degrees in the full degree structure, but there are no minimal nonzero c.e. degrees. The absence of minimal c.e. degrees follows from Sacks Splitting: every nonzero c.e. degree contains two strictly smaller nonzero c.e. degrees below it. Thus references to minimal degrees must specify whether the ambient structure is the full Turing degrees or the c.e. degrees. [/remark] The preceding remark prevents a common confusion. Minimality can exist in the full Turing degrees, while the c.e. degrees have splitting at every nonzero point. [example: A Structural Refinement Table] Let $a$ be a c.e. degree and let $A\in a$ be c.e. If $a$ is low, then \begin{align*} A' \equiv_T 0', \end{align*} which means exactly that \begin{align*} A' \leq_T 0' \qquad\text{and}\qquad 0' \leq_T A'. \end{align*} Thus the jump of $A$ has no more Turing degree than the ordinary halting problem, and no less. If $a$ is high, then for some c.e. $A\ina$, \begin{align*} 0'' \leq_T A'. \end{align*} Since $A$ is c.e., we have \begin{align*} A \leq_T 0'. \end{align*} By monotonicity of the jump under Turing reducibility, \begin{align*} A' \leq_T (0')'. \end{align*} Since $(0')'=0''$, this gives \begin{align*} A' \leq_T 0''. \end{align*} Combining the two reductions, \begin{align*} 0'' \leq_T A' \qquad\text{and}\qquad A' \leq_T 0'', \end{align*} so \begin{align*} A' \equiv_T 0''. \end{align*} Thus high c.e. degrees have maximal possible jump among c.e. degrees. Promptly simple degrees are different in kind: a c.e. degree $a$ is promptly simple when it contains a c.e. set $A$ with a computable nondecreasing bound $p$ such that, whenever $W_e$ is infinite, some new element entering $W_e$ at stage $s$ satisfies \begin{align*} x \in W_{e,s}\setminus W_{e,s-1} \qquad\text{and}\qquad x \in A_{p(s)}. \end{align*} This records a computably bounded response time in an enumeration, not a jump equivalence. Finally, there are no minimal nonzero c.e. degrees. Indeed, if $a\neq 0$ is c.e., then by *Sacks Splitting Theorem* there are nonzero c.e. degrees $b$ and $c$ with \begin{align*} b<a, \qquad c<a, \qquad a=b\veec. \end{align*} The inequality $b<a$ already gives a nonzero c.e. degree strictly below $a$, so $a$ cannot be minimal. This does not contradict the existence of minimal pairs: by *Lachlan Minimal Pair Theorem*, there are nonzero c.e. degrees $p,q$ such that every c.e. degree below both is $0$. Minimality of one degree and minimal-pair behavior of two degrees are separate order-theoretic properties. [/example] ## Finite Injury and Infinite Injury in Degree Constructions What can the priority method decide about the c.e. degrees, and where does it become inadequate in its simplest form? Earlier constructions used finite injury: each requirement may be disrupted, but only finitely often. The structure theorems of this chapter show both the power and the limits of that method. [definition: Finite Injury Priority Argument] A finite injury priority argument is a priority construction in which every requirement is injured only finitely many times. [/definition] Finite injury is suited to diagonalising against countably many computations when restraints eventually settle. It underlies the Friedberg-Muchnik theorem and the standard splitting theorem. [example: Finite Injury in a Splitting Construction] In the Sacks splitting construction, fix a requirement \begin{align*} R_e:\qquad \Phi_e^B \neq A. \end{align*} A typical strategy chooses a number $x$ and waits for a stage $s$ at which the computation \begin{align*} \Phi_{e,s}^{B_s}(x)\downarrow = A_s(x) \end{align*} appears. Suppose this computation uses only oracle questions below $u$. The strategy then imposes the restraint \begin{align*} B_t\upharpoonright u = B_s\upharpoonright u \qquad\text{for later stages }t \end{align*} unless a higher-priority requirement injures it. If the restraint is preserved and $x$ later enters $A$, then the construction puts the permitting change into the other side $C$, so that \begin{align*} B_t\upharpoonright u = B_s\upharpoonright u \end{align*} still holds. The oracle computation is therefore unchanged: \begin{align*} \Phi_e^{B_t}(x)=\Phi_{e,s}^{B_s}(x)=A_s(x), \end{align*} while the enumeration of $x$ into $A$ gives \begin{align*} A_t(x)=1-A_s(x). \end{align*} Hence \begin{align*} \Phi_e^{B_t}(x)\neq A_t(x), \end{align*} so this witness permanently refutes $\Phi_e^B=A$ as long as the protected part of $B$ is not changed. If a higher-priority requirement later enumerates an element below $u$ into $B$, then the equality \begin{align*} B_t\upharpoonright u = B_s\upharpoonright u \end{align*} fails, so the computation used for $x$ is no longer protected and the witness is abandoned. Finite injury means that only finitely many such higher-priority injuries occur. After their final injury, the higher-priority restraints stop changing, the requirement chooses a fresh witness above the settled restraints, and the same calculation gives a permanent disagreement between $\Phi_e^B$ and $A$. This is the finite-injury pattern in the splitting argument: lower-priority work may be reset finitely often, but each requirement eventually keeps one protected computation long enough to diagonalise. [/example] The example displays the finite-injury pattern: each requirement eventually reaches a final stable witness. Some structural facts involve requirements whose apparent witnesses are revised without a last injury, while the construction still has a limiting outcome. This motivates a broader form of priority argument. [definition: Infinite Injury Priority Argument] An infinite injury priority argument is a priority construction in which some requirements may be injured infinitely often, but the construction is organised so that the desired global outcome still follows from a limiting verification. [/definition] The definition enlarges the priority toolkit from eventually stable finite restraints to controlled limiting behaviour. This enlargement matters because local separations can often be handled by finite injury, while restrictions on whole initial segments often require repeated revision of approximations. [remark: Finite And Infinite Injury Boundary] Finite injury arguments are built around requirements whose restraints eventually stabilise, so they are effective for meeting countably many independent diagonalisation requirements. Splitting and basic incomparability constructions fit this pattern because each requirement can settle after higher-priority action stops affecting its finite computation. Initial-segment restrictions such as nondiamond phenomena involve interactions among many potential reductions throughout an interval, and the construction must repeatedly revise approximations to preserve the intended global order information. Infinite injury supplies a bookkeeping mechanism for such repeated revision while still giving a limiting verification. [/remark] This boundary should be read as a guide to the course rather than as a classification theorem. Finite injury is not ruled out by a formal impossibility criterion; rather, it becomes inadequate when requirements depend on a changing global interval rather than on isolated diagonalisation witnesses. The nondiamond theorem is the counterexample to the tempting stronger picture: density and splitting suggest local flexibility, but they do not permit every finite initial-segment pattern. This explains why the same broad priority idea can look elementary in Post-style separation arguments and highly intricate in the fine structure of c.e. degrees. [remark: What Priority Does Not Automatically Decide] A successful priority construction proves the existence of a degree or configuration satisfying specified requirements. It does not by itself provide a simple classification of all c.e. degrees, and it does not guarantee that every finite partial order compatible with density embeds into the c.e. degrees. The nondiamond theorem is the warning example: the absence of local gaps coexists with a global obstruction. [/remark] The chapter's main lesson is that the c.e. degrees are structured but not tame. Splitting and density show richness inside every nontrivial interval, minimal pairs show sharp downward separation, lowness and highness refine degrees by jump complexity, and nondiamond phenomena show that priority constructions also reveal rigid constraints. The c.e. degrees reveal a rich ordered world, yet they are still only one part of the full Turing degree structure. Chapter 11 broadens the view to sets beyond c.e. complexity, where trees, basis theorems, lowness, highness, and randomness show how diverse degree-theoretic phenomena can become. # 11. Degrees Beyond c.e. Sets This chapter moves away from the computably enumerable degrees and asks what happens in the wider Turing degree structure. The c.e. degrees studied in Chapters 7 through 10 are rich enough for priority arguments and Post's problem, but they are only a small part of the degrees. We now meet several degree-theoretic notions that are most naturally produced by compactness, forcing with trees, and diagonal constructions outside the c.e. setting. The guiding theme is that noncomputability can be weak in different senses. A set may compute no nonzero c.e. degree, may fail to compute fast-growing domination power, may compute a complete extension of Peano arithmetic, or may arise as a path through a computable tree. These distinctions prepare for the reverse-mathematical role of weak König's lemma and for the later contact between computability and randomness. ## Minimal Degrees and Weak Noncomputability The first question is whether there are noncomputable degrees with no simpler noncomputable degree below them. For c.e. degrees, Sacks splitting prevents this kind of atom-like behaviour. Outside the c.e. degrees, however, the construction can be arranged so that every attempted reduction from the object we build either becomes computable or computes the whole object back. [definition: Minimal Degree] A Turing degree $a$ is minimal if $a \ne 0_T$ and for every Turing degree $b$, if $0_T < b \leq a$, then $b = a$. [/definition] After the definition, the interval below a minimal degree has only two elements: the computable degree and the degree itself. Minimality is therefore a statement about the absence of intermediate information, not about being close to computable in every possible sense. [example: Why Minimal Degrees Are Not C E Degrees] Let $a$ be a nonzero c.e. degree. By *Sacks Splitting Theorem*, there are nonzero c.e. degrees $b$ and $c$ such that \begin{align*} b &< a,\\ c &< a,\\ a &= b\vee c. \end{align*} The strict inequality $b<a$ means exactly that \begin{align*} b &\leq a,\\ b &\ne a. \end{align*} Since $b$ is nonzero, we also have $0_T<b$. Hence \begin{align*} 0_T<b\leqa \end{align*} but $b\nea$. This contradicts the defining condition for $a$ to be minimal. Therefore no nonzero c.e. degree is minimal, so minimal degrees must be constructed outside the c.e. degrees. [/example] The example rules out the most familiar source of noncomputable degrees, so the next problem is existence. The theorem below answers that problem by replacing c.e. approximation with a tree construction that controls all reductions from the eventual set. [quotetheorem:5437] [citeproof:5437] This proof is the first major use of tree forcing in the course, and the hypotheses explain why the result belongs outside the c.e. degrees. The nonzeroness clause is not cosmetic: the computable degree $0_T$ has no nonzero degree below it, so without $a\ne0_T$ the definition would count the computable degree as a degenerate minimal object and would miss the point of Post-style noncomputability. The restriction to degrees below $a$ is also essential; a minimal degree does not restrict incomparable degrees, and there are many degrees neither below nor above a given minimal degree. Finally, the c.e. boundary is sharp: if $a$ is a nonzero c.e. degree, Sacks splitting gives nonzero c.e. degrees $b,c<a$ with $a=b\veec$, so no nonzero c.e. degree satisfies minimality. The theorem therefore controls the lower cone of the constructed degree only; it does not say that the degree is close to computable in growth strength, jump strength, or measure-theoretic behaviour. That limitation motivates the next weakness notion, where the question is no longer what lies below a degree but whether its functions can outrun all computable bounds. [definition: Hyperimmune Free Degree] A Turing degree $a$ is hyperimmune-free if every function $f:\mathbb N\to\mathbb N$ with $f \leq_T A$ for some $A \in a$ is dominated by a computable function $g:\mathbb N\to\mathbb N$. [/definition] Here domination means that there is $N\in\mathbb N$ such that $f(n)\leq g(n)$ for all $n\geq N$. Hyperimmune-free degrees may still be noncomputable, but their computable functions are growth-controlled by computable bounds. [example: A Degree That Is Not Hyperimmune Free] Let $A=\emptyset'$. Fix a computable stage approximation $(K_s)_{s\in\mathbb N}$ to the halting set $K=\emptyset'$, where $e\in K_s$ means that the computation with index $e$ has halted by stage $s$. Define \begin{align*} f(n)=\min\{s:\text{ for every }e<n,\ e\in K \text{ iff } e\in K_s\}. \end{align*} This function satisfies $f\leq_T\emptyset'$: with oracle $K$, compute the finite set $K\cap\{0,\dots,n-1\}$, then search for the first stage $s$ such that \begin{align*} K_s\cap\{0,\dots,n-1\}=K\cap\{0,\dots,n-1\}. \end{align*} We show that no computable function eventually dominates $f$. Suppose, toward a contradiction, that $g$ is computable and there is $N$ such that \begin{align*} f(n)\leq g(n) \end{align*} for every $n\geq N$. Then $K$ is computable as follows. For each $e\geq N$, run the computation with index $e$ for exactly $g(e+1)$ stages. Since $e<e+1$ and $e+1\geq N$, the definition of $f(e+1)$ gives \begin{align*} e\in K &\iff e\in K_{f(e+1)}\\ &\iff e\in K_{g(e+1)}, \end{align*} because $f(e+1)\leq g(e+1)$ and once a halting computation appears in the approximation it remains there. For the finitely many inputs $e<N$, hard-code whether $e\in K$. This gives a computable decision procedure for $K=\emptyset'$, contradicting the noncomputability of the halting problem. Hence $f\leq_T\emptyset'$ is not dominated by any computable function, so the degree of $\emptyset'$ is not hyperimmune-free. This separates domination strength from mere noncomputability. [/example] Minimality and hyperimmune-freeness are restrictive notions: they limit what sits below a degree or what grows inside it. The next section reverses the emphasis and studies degrees strong enough to make complete arithmetical choices. ## PA Degrees and Diagonally Noncomputable Functions The next problem is to identify the computational content of complete theories extending Peano arithmetic. A complete consistent extension of PA must decide every arithmetic sentence while avoiding contradiction. In degree terms, this turns out to be the same kind of strength as producing paths through certain computable binary trees. [definition: PA Degree] A Turing degree $a$ is a PA degree if some set $A \in a$ computes a complete consistent extension of Peano arithmetic. [/definition] The name records the connection with Peano arithmetic, but the degree-theoretic behaviour is often easier to see through anti-diagonal functions. The problem is to name the exact kind of function that makes a fresh choice against each effective diagonal computation. The next definition supplies that name and turns completeness into a computability-theoretic avoidance principle. [definition: Diagonally Noncomputable Function] A total function $f:\mathbb N\to\mathbb N$ is diagonally noncomputable if for every $e\in\mathbb N$, whenever $\varphi_e(e)$ is defined, $f(e)\ne \varphi_e(e)$. [/definition] A DNC function escapes the diagonal values of the partial computable functions. This is stronger than being noncomputable: it gives a uniform anti-diagonal value at every index where the diagonal computation converges. [example: The Halting Problem Computes A DNC Function] Let $K=\emptyset'$ be the halting problem. Define $f:\mathbb N\to\mathbb N$ by \begin{align*} f(e)= \begin{cases} \varphi_e(e)+1, & \text{if } \varphi_e(e)\downarrow,\\ 0, & \text{if } \varphi_e(e)\uparrow. \end{cases} \end{align*} The oracle $K$ decides whether $\varphi_e(e)$ halts: ask whether the computation with index $e$ on input $e$ belongs to $K$. If the answer is no, output $0$. If the answer is yes, simulate the computation until it halts, obtaining its value $\varphi_e(e)$, and then output $\varphi_e(e)+1$. Hence $f$ is total and $f\leq_T\emptyset'$. Now fix any $e$ such that $\varphi_e(e)\downarrow$. By the first case in the definition, \begin{align*} f(e)&=\varphi_e(e)+1. \end{align*} Since $\varphi_e(e)+1\ne \varphi_e(e)$ in $\mathbb N$, we have \begin{align*} f(e)\ne \varphi_e(e). \end{align*} Thus $f$ disagrees with every defined diagonal value, so $f$ is diagonally noncomputable. This gives an explicit DNC function computable from the complete c.e. degree $\deg_T(\emptyset')$. [/example] The example shows that complete information can produce diagonal avoidance, but PA degrees ask for a more exact calibration. The theorem below identifies PA strength with binary diagonal avoidance after the enumeration has been fixed appropriately. [quotetheorem:5438] [citeproof:5438] This theorem turns a model-theoretic object into a degree-theoretic anti-diagonal principle, but the binary-valued and fixed-acceptable-enumeration clauses are hypotheses with real content. If the function is allowed to take arbitrary natural-number values relative to the usual enumeration of all partial computable functions, the condition becomes too broad: $\emptyset'$ computes such a DNC function, but the theorem is not identifying PA degrees by unbounded numerical escape alone; it is identifying the binary choice power needed to choose complete consistent extensions. If the enumeration is not acceptable, the statement can be distorted by omitting or duplicating diagonal tasks; for example, an enumeration consisting only of the everywhere-undefined partial function would make every binary function vacuously DNC and would falsely put computable degrees on the PA side. The acceptable enumeration requirement prevents this by ensuring that every partial computable binary procedure appears with effective translations between standard listings. The result also does not say that every DNC function computes a complete theory by the same functional, nor that a PA degree is complete for the halting problem. It gives a recognition test for PA degrees in exercises: convert a path or theory problem into a computable binary tree, then look for the DNC choice that avoids the forbidden diagonal branch. ## Computable Trees and Paths The central compactness question is whether every infinite finitely branching computable tree has a computable infinite path. Classical compactness says such a path exists. Computability theory asks how difficult it is to compute one. [definition: Binary Tree] A binary tree is a set $T\subseteq 2^{<\mathbb N}$ such that if $\sigma\in T$ and $\tau\preceq\sigma$, then $\tau\in T$. [/definition] A binary tree records finite approximations closed under taking earlier approximations. The next problem is to say what counts as completing all those approximations at once. This leads from finite nodes to the infinite paths whose degrees measure the computational content of compactness. [definition: Infinite Path] Let $T\subseteq 2^{<\mathbb N}$ be a binary tree. An infinite path through $T$ is a function $X:\mathbb N\to\{0,1\}$ such that $X\upharpoonright n\in T$ for every $n\in\mathbb N$. [/definition] Trees package finite consistency conditions. A node is a finite approximation, and an infinite path is a complete object satisfying every finite constraint. [example: A Computable Infinite Binary Tree With No Computable Path] Let $(\varphi_e)_{e\in\mathbb N}$ be an effective enumeration of partial computable $\{0,1\}$-valued functions. Define $T\subseteq 2^{<\mathbb N}$ by putting $\sigma\in T$ exactly when, for every $e<|\sigma|$, if $\varphi_e(e)$ halts within $|\sigma|$ steps, then \begin{align*} \sigma(e)\ne \varphi_e(e). \end{align*} Membership in $T$ is computable: on input $\sigma$, run each computation $\varphi_e(e)$ for $|\sigma|$ steps for the finitely many $e<|\sigma|$, and reject exactly if some halted computation has value $\sigma(e)$. The set $T$ is a binary tree. If $\sigma\in T$ and $\tau\preceq\sigma$, then for any $e<|\tau|$, a computation $\varphi_e(e)$ halting within $|\tau|$ steps also halts within $|\sigma|$ steps. Since $\sigma\in T$, \begin{align*} \sigma(e)\ne \varphi_e(e). \end{align*} Because $\tau\preceq\sigma$ and $e<|\tau|$, we have $\tau(e)=\sigma(e)$, hence \begin{align*} \tau(e)\ne \varphi_e(e). \end{align*} Thus $\tau\in T$. The tree is infinite. For each $n$, define a string $\sigma_n\in 2^n$ by \begin{align*} \sigma_n(e)= \begin{cases} 1-\varphi_e(e), & \text{if } e<n \text{ and } \varphi_e(e) \text{ halts within } n \text{ steps},\\ 0, & \text{if } e<n \text{ and } \varphi_e(e) \text{ does not halt within } n \text{ steps}. \end{cases} \end{align*} If $e<n$ and $\varphi_e(e)$ halts within $n$ steps, then $\varphi_e(e)\in\{0,1\}$, so \begin{align*} \sigma_n(e)&=1-\varphi_e(e),\\ \sigma_n(e)&\ne \varphi_e(e). \end{align*} Therefore $\sigma_n\in T$, so $T$ has a node of every length. Now let $X$ be any infinite path through $T$. If $\varphi_e(e)\downarrow$, choose a stage $s$ by which this computation has halted, and take \begin{align*} n=\max(e+1,s). \end{align*} Since $X$ is a path, $X\upharpoonright n\in T$. Also $e<n$, and $\varphi_e(e)$ halts within $n$ steps, so the definition of $T$ gives \begin{align*} X(e)=(X\upharpoonright n)(e)\ne \varphi_e(e). \end{align*} Thus every path through $T$ is a binary diagonally noncomputable function. If such a path were computable, it would appear as some $\varphi_i$ in the enumeration, and then \begin{align*} X(i)=\varphi_i(i) \end{align*} would contradict the diagonal disagreement above. Hence $T$ is a computable infinite binary tree with no computable path. [/example] This example is the degree-theoretic content of compactness in miniature: finite computable constraints can guarantee paths while defeating computable paths. The next discussion isolates the compactness principle whose computational strength we are measuring. [explanation: Weak Konigs Lemma In Degree Terms] Weak König's lemma asserts that every infinite binary tree has an infinite path. In degree terms, it says that for every computable infinite binary tree $T$, there exists some set $X$ with $X$ a path through $T$. The infinitude hypothesis is necessary: the empty tree is computable but has no path, and a finite tree also has no infinite path once all branches terminate. The binary finite-branching setting is part of the compactness content; for arbitrary computable subsets of $\mathbb N^{<\mathbb N}$, finite branching can fail and path-existence becomes a different principle with stronger computational behaviour. The computability of the tree matters because degree theory is measuring effective compactness: a noncomputable tree can hide noncomputable information directly in its membership relation, so the degree of a path may reflect the presentation rather than the compactness principle. The DNC tree above gives the central limitation: even with a computable infinite binary tree, a path need not be computable. Different basis theorems therefore measure how weak a noncomputable path can be chosen. [/explanation] The PA-degree characterization is the most important special case for this chapter. PA degrees are exactly the degrees that can solve every nonempty computable binary tree path problem. [quotetheorem:5439] [citeproof:5439] This result locates weak König's lemma in the degree structure, but its quantifiers should be read carefully. It asserts that a fixed PA degree is strong enough to compute some path for each computable tree; it does not provide one uniform Turing functional that, from an index for any tree and an oracle in the degree, always returns a path. Nonemptiness cannot be dropped, because the empty $\Pi^0_1$ class and any computable well-founded tree have no path for any degree to compute. Effective closedness is also essential: an arbitrary closed singleton $\{Y\}$ may contain a set $Y$ of any prescribed degree, so a PA degree need not compute its unique member unless that closed class is presented by computable forbidden prefixes. The binary Cantor-space formulation matters as well; path-choice principles for non-finitely branching trees on $\mathbb N^{<\mathbb N}$ can encode stronger search problems and are not the same degree-theoretic calibration. In practice, this theorem is used by coding a mathematical choice problem as a computable tree and then invoking PA degree strength to choose a compatible infinite branch. ## Basis Theorems If computable trees may lack computable paths, the next question is how weak a path can be forced to be. Basis theorems answer this by showing that every nonempty effectively closed class has a member satisfying some degree-theoretic restraint. They are called basis theorems because they provide a stock of low-complexity representatives in every nonempty $\Pi^0_1$ class. [definition: Low Set] A set $A\subseteq\mathbb N$ is low if $A'\equiv_T\emptyset'$. [/definition] A low set may be noncomputable, but its jump is no stronger than the ordinary halting problem. Lowness therefore measures weakness after one application of the jump. [remark: Low Basis Theorem] Every infinite computable binary tree has an infinite path $P$ with $P'\equiv_T\emptyset'$. [/remark] The Low Basis Theorem shows that weak König's lemma does not require high computational strength for each individual computable tree, but each hypothesis marks a boundary. Nonemptiness is necessary because an empty $\Pi^0_1$ class contains no member, low or otherwise. The $\Pi^0_1$ restriction is necessary because arbitrary nonempty classes can be too complex: for instance, the singleton $\{\emptyset''\}$ is nonempty and closed as an ordinary topological set, but it has no low member. The effective closed presentation is what gives the forcing construction computable finite conditions; without it, the construction cannot search for extensions inside the class. The theorem also does not promise a computable path, as the DNC tree already rules that out. Its practical role is to let us solve a computable compactness problem while keeping the jump weak, which is exactly the kind of restraint needed in later degree-theoretic and reverse-mathematical arguments. [example: Applying The Low Basis Theorem To DNC Paths] The tree $T$ constructed above is a computable infinite binary tree, and the previous example proved that every infinite path through $T$ is a binary diagonally noncomputable function. Since $T$ is infinite and computable, *Low Basis Theorem* gives an infinite path $X$ through $T$ such that \begin{align*} X' \equiv_T \emptyset'. \end{align*} Because $X$ is a path through the DNC tree, for every $e$, if $\varphi_e(e)\downarrow$, then \begin{align*} X(e)\ne \varphi_e(e). \end{align*} Also $X(n)\in\{0,1\}$ for every $n$, since $X$ is a path through a binary tree. Hence $X$ is a low binary DNC function. Let $a=\deg_T(X)$. The lowness calculation above gives \begin{align*} a'=\deg_T(X')=\deg_T(\emptyset')=0_T', \end{align*} so $a$ is low. Since $X$ itself is a binary DNC function and $X\leq_T X$, *PA Degrees And DNC Functions* implies that $a$ is a PA degree. Thus PA strength and jump strength separate: a degree can compute a complete consistent extension of PA while still having only the ordinary halting-problem jump. [/example] Basis theorems often reveal that compactness principles are weaker than their first examples suggest. The no-computable-path tree only proves that computable degrees are insufficient; it does not force completeness or highness. ## Martin Lof Randomness as a Bridge The last question is how these degree notions interact with effective measure. Randomness is a full subject of its own, but a first encounter helps place degrees beyond c.e. sets into a wider map. Instead of building objects by forcing through trees, randomness excludes membership in effectively null exceptional classes. The concrete obstruction is that ordinary measure-zero avoidance is too weak for computability: every singleton has measure zero, but without an effective description this does not give a computable test that can detect a particular sequence. [definition: Martin Lof Test] A Martin-Löf test is a uniformly c.e. sequence $(U_n)_{n\in\mathbb N}$ of open subsets of $2^{\mathbb N}$ such that $\mu(U_n)\leq 2^{-n}$ for every $n\in\mathbb N$, where $\mu$ is the fair-coin product measure. [/definition] The sets $U_n$ are effective approximations to small exceptional sets. A single test catches sequences with one specified effective defect, but randomness must avoid all such defects at once. This motivates the following universal avoidance condition. [definition: Martin Lof Random Sequence] A sequence $X\in 2^{\mathbb N}$ is Martin-Löf random if for every Martin-Löf test $(U_n)_{n\in\mathbb N}$, there exists $n\in\mathbb N$ such that $X\notin U_n$. [/definition] This chapter uses randomness only as a bridge. Random degrees provide many examples of non-c.e. behaviour, but their fine structure requires martingales, Kolmogorov complexity, and measure-theoretic tools that lie outside this course's main path. [quotetheorem:5440] [citeproof:5440] This theorem is deliberately modest, and its hypotheses explain what it does and does not prove. The Martin-Löf-test requirement is essential: if tests were arbitrary measure-zero sets rather than uniformly c.e. open covers with the bounds $\mu(U_n)\leq 2^{-n}$, then a noncomputable sequence could be rejected merely by the singleton set containing it, so the notion would no longer measure effective randomness. Uniform c.e. openness is also needed because the proof captures a computable sequence by effectively enumerating its shrinking cylinders; without effectivity, the construction would not be a computability-theoretic test. The theorem gives only one direction: it excludes computable sequences, but there are many noncomputable sequences that are not Martin-Löf random, such as a sequence that is eventually all zeros after coding a noncomputable set into sparse positions. Later results in the subject analyse which random degrees compute c.e. information, which are low for randomness, and how randomness interacts with PA degrees. [remark: Degrees Beyond The C E Landscape] Minimal degrees, hyperimmune-free degrees, PA degrees, low paths, and random degrees give different answers to the same organising question: what can a noncomputable set compute? Minimal degrees restrict their lower cone, hyperimmune-free degrees restrict domination, PA degrees solve compactness problems, low degrees have weak jumps, and random degrees arise from effective measure. The rest of the course uses these examples to view reverse mathematics and degree theory as two languages for the strength of existence principles. [/remark] The examples from the broader degree structure make clear that computability and proof strength are two aspects of the same phenomenon. Chapter 12 uses this perspective to connect Turing degrees with reverse mathematics, asking which subsystems are needed to prove the existence principles that earlier chapters analyzed algorithmically. # 12. Connections to Reverse Mathematics After Chapter 11's move beyond c.e. degrees to trees, paths, PA degrees, and basis theorems, the guiding question is not whether a theorem is true in the full universe of sets, but how much comprehension is required to prove it. The subsystems $\mathsf{RCA}_0$, $\mathsf{WKL}_0$, $\mathsf{ACA}_0$, and $\Pi^1_1\text{-}\mathsf{CA}_0$ form a scale of increasing strength. Computability theory supplies both the examples and the countermodels used to calibrate that scale. ## Subsystems as Comprehension Calibrations What does it mean to prove ordinary mathematics using only computable information? Second-order arithmetic separates statements about numbers from statements about sets of numbers, so that the allowed set-existence axioms can be varied. We first need the ambient formal language in which this separation is made. [definition: Second-Order Arithmetic] Second-order arithmetic is a formal theory with number variables ranging over $\mathbb N$ and set variables ranging over subsets of $\mathbb N$. Its language includes $0$, successor, addition, multiplication, order, membership $n \in X$, and equality. [/definition] This definition identifies the two sorts whose interaction reverse mathematics studies. To compare different choices of second-order sets without changing the arithmetic of natural numbers, we restrict attention to models with the usual first-order part. That leads to the model notion used throughout the chapter. [definition: Omega Model] An $\omega$-model of second-order arithmetic is a structure $(\mathbb N, \mathcal S)$, where $\mathcal S \subseteq \mathcal P(\mathbb N)$ is the second-order part of the model. A set quantifier ranges over elements of $\mathcal S$. [/definition] An $\omega$-model is therefore controlled by a collection of reals. For recursion theory, the next question is which closure properties such a collection must have if it is to support computable constructions relative to its own sets. The answer is the degree-theoretic notion of an ideal. [definition: Turing Ideal] A Turing ideal is a nonempty collection $\mathcal S \subseteq \mathcal P(\mathbb N)$ such that: 1. if $A \in \mathcal S$ and $B \le_T A$, then $B \in \mathcal S$; 2. if $A,B \in \mathcal S$, then $A \oplus B \in \mathcal S$. [/definition] The downward closure condition says that the model contains everything computable from information it already has, while the join condition says that two available sets can be used together as a single oracle. We need the following theorem because it identifies exactly when these degree-theoretic closure conditions are the same as satisfying the base subsystem $\mathsf{RCA}_0$. This turns the phrase recursive mathematics into a precise model-theoretic statement. [quotetheorem:5441] [citeproof:5441] Both hypotheses in the Turing-ideal description are needed. Downward closure alone would allow a collection containing $A$ and all sets computable from $A$ but not the join $A \oplus B$ of two separately available oracles, so the model could not uniformly use two parameters in one recursive definition. Join closure alone would not force the model to contain a set $B \le_T A$, so recursive comprehension relative to an existing oracle could fail. Thus $\mathsf{RCA}_0$ captures the computable core of mathematics. Once the base theory is fixed, the next calibration asks what happens when compactness for infinite binary trees is added. This motivates the subsystem built around weak Konig's lemma. [definition: Weak Konig Lemma System] The system $\mathsf{WKL}_0$ is $\mathsf{RCA}_0$ plus the assertion that every infinite binary tree $T \subseteq 2^{<\mathbb N}$ has an infinite path. [/definition] Weak Konig's lemma is a compactness principle: every finite stage may be extendible even when no computable infinite path is available. It is not the same as allowing all arithmetical definitions. We need a separate definition for the stronger threshold where every arithmetically specified set is available. [definition: Arithmetical Comprehension System] The system $\mathsf{ACA}_0$ is $\mathsf{RCA}_0$ plus comprehension for every arithmetical formula, allowing set parameters. [/definition] Arithmetical comprehension permits definitions with alternating number quantifiers. In computability terms, those definitions are governed by finite iterations of the Turing jump. The next subsystem goes beyond number quantifiers and allows a restricted form of quantification over sets. [definition: Pi-One-One Comprehension System] The system $\Pi^1_1\text{-}\mathsf{CA}_0$ is $\mathsf{RCA}_0$ plus comprehension for formulas of the form $\forall X\,\varphi(n,X)$ where $\varphi$ is arithmetical. [/definition] This last system reaches beyond arithmetical information into genuinely analytic quantification over sets. In the usual reverse-mathematical hierarchy, it corresponds to the strength needed for many theorems involving well-orders, countable ordinals, and higher inductive constructions. A comparison example helps locate the four systems on the same scale. [example: Comparing The Four Systems] The four systems can be compared by looking at what set-existence operation each one guarantees. In $\mathsf{WKL}_0$, the extra axiom says exactly that if $T \subseteq 2^{<\mathbb N}$ is an infinite binary tree, then there is a function $P:\mathbb N \to \{0,1\}$ such that $P|_n \in T$ for every $n$. Thus $\mathsf{WKL}_0$ adds a compactness principle: it supplies a path through an infinite finitely branching tree, without saying that every arithmetically defined set exists. For $\mathsf{ACA}_0$, a standard test is the range of an injection. If $f:\mathbb N \to \mathbb N$ is an injection, then membership in its range is the arithmetical condition \begin{align*} n \in \operatorname{rng}(f) \quad\Longleftrightarrow\quad \exists m\,\bigl(f(m)=n\bigr). \end{align*} Arithmetical comprehension therefore forms the set $\operatorname{rng}(f)=\{n:\exists m(f(m)=n)\}$. Conversely, suppose every injection has its range as a set. Given an oracle $A$, define an $A$-computable injection $g$ as follows: at stage $s$, if $e$ is the least number whose computation $\varphi_e^A(e)$ halts for the first time at stage $s$, output $2e$; if no such new halting computation appears at stage $s$, output the least odd number not previously output. Then no value is repeated, and \begin{align*} 2e \in \operatorname{rng}(g) &\Longleftrightarrow \text{some stage outputs }2e\\ &\Longleftrightarrow \varphi_e^A(e)\downarrow\\ &\Longleftrightarrow e \in A'. \end{align*} So the range of $g$ computes $A'$, and closure under ranges of injections forces closure under the Turing jump, which is the $\omega$-model content of $\mathsf{ACA}_0$. For $\Pi^1_1\text{-}\mathsf{CA}_0$, consider a countable sequence $(W_i)_{i\in\mathbb N}$ of coded countable linear orders. The assertion that $W_i$ is a well-order says that there is no infinite descending sequence through $W_i$: \begin{align*} W_i \text{ is well-founded} \quad\Longleftrightarrow\quad \forall X\,\neg\bigl(X(0)>_{W_i}X(1)>_{W_i}X(2)>\cdots\bigr). \end{align*} The quantifier over $X:\mathbb N\to\mathbb N$ is a set quantifier, so the set \begin{align*} \{i\in\mathbb N : W_i \text{ is a well-order}\} \end{align*} is governed by $\Pi^1_1$ comprehension rather than merely arithmetical comprehension. This places the systems on a computational scale: $\mathsf{RCA}_0$ gives recursive closure, $\mathsf{WKL}_0$ adds compactness for binary trees, $\mathsf{ACA}_0$ adds finite arithmetical jump information, and $\Pi^1_1\text{-}\mathsf{CA}_0$ adds comprehension for well-foundedness and similar analytic predicates. [/example] The examples show the calibration role of subsystems. A theorem equivalent to $\mathsf{ACA}_0$ is not merely nonconstructive in a vague sense; it needs enough set existence to close the universe under the jump. ## Recursive Mathematics and the Turing Jump Which sets must exist if we want to perform all arithmetical constructions relative to known data? The answer is controlled by the jump. Earlier chapters introduced $A'$ as the halting problem relative to $A$; here it becomes the model-theoretic test for arithmetical comprehension. [definition: Closure Under Turing Jump] The Turing jump is the operator $J:\mathcal P(\mathbb N) \to \mathcal P(\mathbb N)$ given by $J(A)=A'$. A collection $\mathcal S \subseteq \mathcal P(\mathbb N)$ is closed under the Turing jump if $A \in \mathcal S$ implies $J(A)=A' \in \mathcal S$. [/definition] Closure under the jump is stronger than being a Turing ideal, since $A'$ is not computable from $A$ in general. It adds exactly the information needed to decide all $\Sigma^0_1(A)$ questions, and by iteration it supports all finite arithmetical levels. The theorem below states the promised equivalence between formal comprehension and jump closure. [quotetheorem:5442] [citeproof:5442] The assumption that the model already satisfies $\mathsf{RCA}_0$ is not cosmetic: without the Turing-ideal closure supplied by the base theory, having $A'$ for some sets would not guarantee that all sets computable from the relevant finite jumps are present. Closure under the first jump is also exactly the missing ingredient beyond $\mathsf{RCA}_0$: the computable sets form an $\omega$-model of $\mathsf{RCA}_0$, but they omit $\varnothing'$ and therefore cannot satisfy arithmetical comprehension. This theorem is the central bridge between the course's degree-theoretic material and reverse mathematics. It says that the formal axiom scheme $\mathsf{ACA}_0$ has the same computational content, over $\omega$-models, as allowing the jump operation. The most basic instance is the recovery of the ordinary halting problem. [example: Arithmetical Comprehension Computes The Halting Problem] Work in an $\omega$-model $(\mathbb N,\mathcal S)$ of $\mathsf{ACA}_0$ with $\varnothing \in \mathcal S$. For each pair $(e,s)$, let $H(e,s)$ mean that the computation $\varphi_e(e)$ halts within exactly $s$ steps when run with no oracle. The relation $H(e,s)$ is primitive recursive once a standard coding of finite computations is fixed: it asserts that there is a finite computation history of length $s$ whose initial configuration is program $e$ on input $e$, whose successive configurations follow the machine transition rules, and whose final configuration is halting. Hence \begin{align*} e \in K &\Longleftrightarrow \varphi_e(e)\downarrow \\ &\Longleftrightarrow \exists s\,H(e,s). \end{align*} The formula $\exists s\,H(e,s)$ has only number quantifiers and no set quantifier, so it is arithmetical. Since $(\mathbb N,\mathcal S)$ satisfies $\mathsf{ACA}_0$, arithmetical comprehension gives the set \begin{align*} K=\{e\in\mathbb N:\exists s\,H(e,s)\} \end{align*} as an element of $\mathcal S$. By the definition of the Turing jump of the empty oracle, \begin{align*} \varnothing' =\{e\in\mathbb N:\varphi_e^\varnothing(e)\downarrow\} =\{e\in\mathbb N:\varphi_e(e)\downarrow\} =K. \end{align*} Thus every $\omega$-model of $\mathsf{ACA}_0$ containing the computable empty oracle also contains the halting problem, so it contains a noncomputable set. [/example] The same reasoning relativizes. If the model contains an oracle $A$, then it contains the halting problem relative to $A$, and hence contains every arithmetical set relative to $A$. [remark: Recursive Mathematics As The Base Theory] The slogan that $\mathsf{RCA}_0$ is recursive mathematics should be read through $\omega$-models: starting with some oracle information, the model contains exactly the sets obtainable by computable reductions and finite joins, unless stronger principles are added. [/remark] This interpretation also explains why many elementary theorems fall into $\mathsf{RCA}_0$. Their proofs only require algorithms relative to the input data, not new jumps or compactness principles. ## Degrees in Omega Models and Basis Theorems How can a theorem assert the existence of an object without forcing the model to contain very high degrees? Basis theorems answer this by finding solutions of controlled computational strength. They are among the main recursion-theoretic tools for proving that a principle is weaker than $\mathsf{ACA}_0$. [definition: Path Through A Binary Tree] A path through a binary tree $T \subseteq 2^{<\mathbb N}$ is a function $P:\mathbb N \to \{0,1\}$ such that $P|_n \in T$ for every $n \in \mathbb N$. [/definition] An infinite computable binary tree may have no computable path, so $\mathsf{WKL}_0$ cannot be reduced to $\mathsf{RCA}_0$. The relevant question is whether paths can be chosen with controlled degree. We use the Low Basis Theorem stated earlier: infinite computable binary trees have low paths. The computability of the tree is essential to this form of the theorem. If the tree is only computable relative to an oracle $A$, the conclusion becomes relative lowness, namely $P' \equiv_T A'$ over the parameter $A$, rather than absolute lowness. The infinitude hypothesis is also sharp: a finite tree may have no path of length $n$ for arbitrarily large $n$, so compactness has no object to select. The theorem says that compactness for binary trees can be witnessed without jumping beyond the halting problem. This is why $\mathsf{WKL}_0$ is much weaker than $\mathsf{ACA}_0$ in degree-theoretic terms. The next example turns the basis theorem into an $\omega$-model construction. [example: An Omega Model Of Weak Konig Lemma From Low Paths] Begin with $\mathcal S_0=\{X\subseteq\mathbb N:X\le_T\varnothing\}$, the computable sets. This is a Turing ideal: it is nonempty because $\varnothing\in\mathcal S_0$; if $B\le_T A$ and $A$ is computable, then $B\le_T A\le_T\varnothing$, so $B$ is computable; and if $A,B\le_T\varnothing$, then $A\oplus B\le_T\varnothing$, so $A\oplus B$ is computable. Suppose $\mathcal S_n$ is a countable Turing ideal. Enumerate the members of $\mathcal S_n$ that code infinite binary trees as \begin{align*} T_{n,0},T_{n,1},T_{n,2},\ldots . \end{align*} For each $k$, choose a path $P_{n,k}$ through $T_{n,k}$ which is low relative to the code for $T_{n,k}$, as supplied by the relativized *Low Basis Theorem*. Thus \begin{align*} P_{n,k}\text{ is a path through }T_{n,k} \quad\text{and}\quad (P_{n,k}\oplus T_{n,k})'\equiv_T T_{n,k}'. \end{align*} Define $\mathcal S_{n+1}$ to be the collection of all sets computable from a finite join of elements of $\mathcal S_n$ together with finitely many of the new paths: \begin{align*} \mathcal S_{n+1} = \left\{ B: B\le_T A\oplus P_{n,k_0}\oplus\cdots\oplus P_{n,k_r} \text{ for some }A\in\mathcal S_n \text{ and }k_0,\ldots,k_r\in\mathbb N \right\}. \end{align*} Then $\mathcal S_n\subseteq\mathcal S_{n+1}$, because if $B\in\mathcal S_n$, then \begin{align*} B\le_T B, \end{align*} so $B$ belongs to $\mathcal S_{n+1}$ by taking $A=B$ and no new paths. The class $\mathcal S_{n+1}$ is downward closed by transitivity of Turing reducibility: if $C\le_T B$ and \begin{align*} B\le_T A\oplus P_{n,k_0}\oplus\cdots\oplus P_{n,k_r}, \end{align*} then \begin{align*} C\le_T A\oplus P_{n,k_0}\oplus\cdots\oplus P_{n,k_r}. \end{align*} It is also closed under joins. Indeed, if \begin{align*} B_0&\le_T A_0\oplus P_{n,i_0}\oplus\cdots\oplus P_{n,i_r},\\ B_1&\le_T A_1\oplus P_{n,j_0}\oplus\cdots\oplus P_{n,j_s}, \end{align*} then, since $\mathcal S_n$ is a Turing ideal, $A_0\oplus A_1\in\mathcal S_n$, and \begin{align*} B_0\oplus B_1 \le_T (A_0\oplus A_1)\oplus P_{n,i_0}\oplus\cdots\oplus P_{n,i_r} \oplus P_{n,j_0}\oplus\cdots\oplus P_{n,j_s}. \end{align*} Hence $B_0\oplus B_1\in\mathcal S_{n+1}$. Now let \begin{align*} \mathcal S=\bigcup_{n\in\mathbb N}\mathcal S_n. \end{align*} This union is a Turing ideal. If $B\le_T A$ and $A\in\mathcal S$, then $A\in\mathcal S_n$ for some $n$, so $B\in\mathcal S_n\subseteq\mathcal S$. If $A,B\in\mathcal S$, choose $m$ with $A,B\in\mathcal S_m$; since $\mathcal S_m$ is a Turing ideal, \begin{align*} A\oplus B\in\mathcal S_m\subseteq\mathcal S. \end{align*} Finally, if $T\in\mathcal S$ is an infinite binary tree, then $T\in\mathcal S_n$ for some $n$, so $T=T_{n,k}$ for some $k$ in the stage-$n$ enumeration. The construction put a path $P_{n,k}$ through $T_{n,k}$ into $\mathcal S_{n+1}$, and therefore into $\mathcal S$. Thus $(\mathbb N,\mathcal S)$ satisfies $\mathsf{WKL}_0$. The point of choosing the paths low relative to their tree codes is that each compactness witness is added with controlled degree, so adding paths through all trees in the ideal does not by itself amount to closing the model under the full Turing-jump hierarchy. [/example] The construction illustrates a standard reverse-mathematical method: build the second-order part of an $\omega$-model in stages, adding witnesses required by the target theorem while controlling the degrees of those witnesses. The same construction is useful because it can separate weak Konig's lemma from arithmetical comprehension. We now record that separation explicitly. [quotetheorem:5443] [citeproof:5443] The hypothesis that the model is allowed to add controlled paths is the point of the argument. If arbitrary paths were added, the construction could accidentally include $\varnothing'$ or enough jumps to satisfy arithmetical comprehension. Conversely, if no paths were added, an infinite computable tree with no computable path would already violate $\mathsf{WKL}_0$. This separation does not say that weak Konig's lemma lacks mathematical force. It says its force is compactness-like rather than arithmetical-comprehension-like. ## Conservation and Degree-Sensitive Principles When does adding a set-existence principle produce new first-order consequences? Conservation theorems measure whether a subsystem proves new number-theoretic statements, while degree-sensitive examples show how different solutions to the same instance can have very different computational strength. [definition: Conservation] Let $T$ and $U$ be formal theories with $T \subseteq U$, and let $\Gamma$ be a class of sentences. The theory $U$ is conservative over $T$ for $\Gamma$ if every sentence in $\Gamma$ provable in $U$ is already provable in $T$. [/definition] Conservation results are important because they separate proof-theoretic strength from set-existence strength. A principle may add new sets without adding new theorems of a certain syntactic kind about natural numbers. For weak Konig's lemma, controlled-path constructions lead to conservation phenomena. [remark: Pi-Two Conservation Orientation] Weak Konig's lemma is conservative over $\mathsf{RCA}_0$ for first-order $\Pi^0_2$ consequences: adding weak Konig's lemma does not by itself produce new number-theoretic assertions of this form beyond those already provable in the base system. [/remark] The restriction to first-order $\Pi^0_2$ sentences is essential for this formulation. Weak Konig's lemma itself is a second-order assertion about sets coding binary trees and paths, so it is not conserved over $\mathsf{RCA}_0$ as a second-order theorem. The model-extension proof preserves number-theoretic failures because the first-order part is unchanged; it does not say that no new sets have been added. This form of argument explains why basis theorems have proof-theoretic consequences. They let us add solutions while avoiding computational strength that would settle unrelated arithmetical questions. To state a degree-sensitive test case, we move to [Ramsey's theorem](/theorems/2046) for pairs, whose solutions can have subtle Turing degrees. [definition: Ramsey Theorem For Pairs] Ramsey's theorem for pairs and two colours, denoted $\mathsf{RT}^2_2$, asserts that for every colouring $c:[\mathbb N]^2 \to \{0,1\}$, there is an infinite set $H \subseteq \mathbb N$ such that $c$ is constant on $[H]^2$. [/definition] This principle has a simple finite-combinatorial statement but a subtle reverse-mathematical profile. The existence of an infinite homogeneous set may be guaranteed, yet the degree of such a set can be constrained or forced depending on the colouring. The following example records the computational issue rather than a full classification. [example: Degree Sensitivity In Ramsey-Type Principles] Let $K=\{e:\varphi_e(e)\downarrow\}$. There is a computable colouring $c:[\mathbb N]^2\to\{0,1\}$, constructed by a standard diagonalisation, with the property that every infinite homogeneous set computes enough information to avoid being computable. More explicitly, the construction meets, for each index $e$, the requirement \begin{align*} R_e:\quad W_e\text{ infinite computable } \Longrightarrow W_e\text{ is not homogeneous for }c. \end{align*} To meet $R_e$, wait until two unused numbers $a_e<b_e$ appear in $W_e$, assign \begin{align*} c(a_e,b_e)=0, \end{align*} then wait until a third unused number $d_e>b_e$ appears in $W_e$, and assign \begin{align*} c(a_e,d_e)=1. \end{align*} All other pair colours are filled in effectively, say with colour $0$, unless already assigned. If $W_e$ is infinite, then the waiting eventually succeeds, and $W_e$ contains both pairs $\{a_e,b_e\}$ and $\{a_e,d_e\}$ with \begin{align*} c(a_e,b_e)=0 \quad\text{and}\quad c(a_e,d_e)=1. \end{align*} Thus $W_e$ is not homogeneous. Since every computable infinite set appears as some $W_e$, this computable colouring has no computable infinite homogeneous set. This shows that $\mathsf{RT}^2_2$ is not just recursive closure in disguise: even a computable instance can require adding a noncomputable solution. But the principle still does not behave like full arithmetical comprehension. Results such as the *Low Basis Theorem for Ramsey-type instances* show that many computable colourings have infinite homogeneous sets $H$ with low or low$_2$ degree, meaning respectively \begin{align*} H'\equiv_T \varnothing' \quad\text{or}\quad H''\equiv_T \varnothing''. \end{align*} So Ramsey-type principles sit between purely computable mathematics and jump-closure principles, which is why they test the limits of the Big Five classification. [/example] The broader lesson is that a theorem's reverse-mathematical strength is not read only from whether its statement mentions sets. It depends on the computational complexity of its instances and of the solutions that must be added to a model. ## The Recursion-Theoretic View of Reverse Mathematics The course ends by returning to its main object: the Turing degrees. Reverse mathematics uses degrees not merely as examples of noncomputability, but as structural tools for building models and proving separations. [explanation: What The Subsystems Mean Computationally] The base system $\mathsf{RCA}_0$ corresponds, over $\omega$-models, to Turing ideals: collections closed under computable information and finite combination. The system $\mathsf{WKL}_0$ adds paths through infinite binary trees, but basis theorems show that these paths can often be chosen with low computational strength. The system $\mathsf{ACA}_0$ adds closure under the Turing jump, which is why it captures arithmetical definitions. The system $\Pi^1_1\text{-}\mathsf{CA}_0$ reaches beyond finite jump information and belongs to the study of analytic comprehension and well-foundedness. This viewpoint also explains the methodology of reversals. To prove that a theorem implies $\mathsf{ACA}_0$, encode the jump or an arithmetical comprehension instance into the theorem's conclusion. To prove that a theorem does not imply $\mathsf{ACA}_0$, build an $\omega$-model satisfying the theorem while failing jump closure. Priority arguments, basis theorems, and degree constructions are therefore not side topics; they are the machinery by which reverse-mathematical classifications are established. [/explanation] The explanation summarises the main dictionary between subsystems and degree-theoretic closure. To see how a reversal uses that dictionary in practice, it is useful to revisit a familiar equivalent of arithmetical comprehension. The range of an injection can be made to code the jump. [example: Proving A Reversal To Arithmetical Comprehension] Suppose an $\omega$-model $(\mathbb N,\mathcal S)$ of $\mathsf{RCA}_0$ satisfies the statement that every injection $f:\mathbb N\to\mathbb N$ has its range as a set. Fix $A\in\mathcal S$. We build an $A$-computable injection $g$ whose range uniformly codes $A'=\{e:\varphi_e^A(e)\downarrow\}$. At stage $s$, search for the least $e\le s$ such that $\varphi_e^A(e)$ halts within $s$ steps and $2e$ has not already been output. If such an $e$ exists, set \begin{align*} g(s)=2e. \end{align*} If no such $e$ exists, set $g(s)$ equal to the least odd number not already output. The value chosen at stage $s$ has not previously appeared by construction, so if $t<s$, then \begin{align*} g(t)\ne g(s). \end{align*} Thus $g$ is an injection. Its graph is computable from $A$, so $g$ is available in the $\omega$-model by the recursive closure supplied by $\mathsf{RCA}_0$. By the assumed theorem, the range \begin{align*} R=\operatorname{rng}(g)=\{n:\exists s\,(g(s)=n)\} \end{align*} belongs to $\mathcal S$. For each $e$, \begin{align*} e\in A' &\Longleftrightarrow \varphi_e^A(e)\downarrow\\ &\Longleftrightarrow \text{there is some }s\text{ such that }\varphi_e^A(e)\text{ halts within }s\text{ steps}\\ &\Longleftrightarrow \text{there is some }s\text{ such that stage }s\text{ or a later stage outputs }2e\\ &\Longleftrightarrow 2e\in R. \end{align*} The third equivalence holds because once a halting computation $\varphi_e^A(e)$ has appeared, the construction keeps searching for the least unreported such index until $2e$ is eventually output. Therefore $A'\le_T R$: given $e$, compute $2e$ and ask whether $2e\in R$. Since $R\in\mathcal S$ and $\mathcal S$ is a Turing ideal, downward closure gives $A'\in\mathcal S$. As this holds for every $A\in\mathcal S$, the model is closed under the Turing jump, and by *Arithmetical Comprehension And Jump Closure* it satisfies $\mathsf{ACA}_0$. Thus the range-of-injections principle forces arithmetical comprehension over $\omega$-models of $\mathsf{RCA}_0$. [/example] This closes the circle begun with the halting problem. The same diagonal set that first showed the limits of computation becomes, in reverse mathematics, the benchmark for when ordinary mathematical arguments require arithmetical comprehension. ## Connections and Further Directions Recursion theory supplies a common language for several neighbouring parts of mathematical logic. In proof theory, computability measures the effective content of formal derivations: conservation theorems ask which numerical consequences survive when stronger set-existence principles are added, while ordinal and cut-elimination analyses track how much induction or comprehension a proof has actually used. In model theory, computable presentations and degree spectra ask how much information is needed to describe a countable structure, connecting Turing degrees with isomorphism types rather than with sets alone. The course also points toward descriptive set theory and effective analysis. The arithmetical hierarchy is the finite, number-theoretic shadow of larger definability hierarchies; $\Pi^0_1$ classes already appear as effectively closed subsets of Cantor space, and basis theorems show how topological compactness can be paired with degree control. In analysis, computable functions, effective closed sets, and algorithmic randomness all refine classical existence statements by asking not only whether an object exists, but what information is required to find or name it. The priority constructions in the middle chapters are not isolated technical feats. They show how to build mathematical objects while meeting infinitely many competing requirements, a pattern that reappears in forcing, computable structure theory, reverse mathematics, and algorithmic randomness. The main lesson is therefore structural: the Turing jump, c.e. degrees, basis theorems, and $\omega$-models form a toolkit for detecting exactly where a theorem crosses from effective mathematics into stronger forms of comprehension. ## References - Androma, [Halting Sets Are Computably Enumerable](/theorems/1822). - Androma, [Computably Enumerable Sets Are Sigma 1](/theorems/1824). - Androma, [Prenex Normal Form Theorem](/theorems/4653). - R. I. Soare, *Recursively Enumerable Sets and Degrees*, Springer, 1987. - Piergiorgio Odifreddi, *Classical Recursion Theory*, North-Holland, 1989. - Robert I. Soare, *Turing Computability: Theory and Applications*, Springer, 2016. - Stephen G. Simpson, *Subsystems of Second Order Arithmetic*, Cambridge University Press, 2009.