Fact-checked by Grok 2 weeks ago

Turing degree

In computability theory, a Turing degree is an equivalence class of subsets of the natural numbers (or equivalently, partial functions from naturals to naturals) under Turing equivalence, where two sets A and B are equivalent if each is Turing reducible to the other—that is, a Turing machine with oracle access to one can compute the other.^[1] This notion partitions decision problems by their relative computational complexity, extending beyond computable sets to quantify degrees of unsolvability.^[2] The concept of Turing degrees was formalized by Emil L. Post in 1944, building on Alan Turing's 1939 introduction of oracle machines to model computations with access to unsolvable problems.^[2] Post defined degrees of unsolvability for recursively enumerable sets, using the halting set K (the set of indices of Turing machines that halt on empty input) as a benchmark for the "complete" degree of unsolvability, to which all recursively enumerable sets are reducible.^[2] The degrees form a partial order under Turing reducibility, denoted ≤_T, with the computable (recursive) sets comprising the least element, often denoted 0.^[3] This order is an upper semilattice, closed under joins via the operation A ⊕ B (the effective disjoint union of A and B), but lacks meets in general.^[3] Fundamental results shape the structure of the Turing degrees. The Kleene-Post theorem of 1954 proves the existence of incomparable degrees: for any non-computable set B, there exists a set A such that neither A ≤_T B nor B ≤_T A.^[3] The collection of all degrees has cardinality 2^ℵ₀, matching the continuum, and contains antichains of this size.^[1] The Turing jump operator elevates a degree d to d', the degree of the halting problem relative to any set in d; this strictly increases complexity (d <_T d') and connects to the arithmetic hierarchy, where the n-th jump ∅⁽ⁿ⁾ is complete for the Σ_n⁰ level.^[1] Minimal degrees (where any set below is computable) and low degrees (where d' = 0') exist, as shown by Spector in 1956.^[3] The Turing degrees underpin much of modern computability theory, influencing studies of recursively enumerable degrees (addressing Post's problem on density via priority methods by Friedberg and Muchnik in 1956–1957), embeddings of countable partial orders (Sacks, 1963), and interdisciplinary links to set theory, randomness, and descriptive set theory.^[3] Ongoing research examines automorphisms of the degree structure, the behavior of jumps under forcing, and applications to algorithmic randomness, revealing a highly intricate poset with no linear order.^[4]

Fundamentals

Definition and historical context

In computability theory, a Turing degree is defined as the equivalence class of sets of natural numbers under Turing equivalence, where two sets A and B are Turing-equivalent if each is computable from the other using a Turing machine with the other set as an oracle.^[5] This notion captures the relative computational difficulty of deciding membership in such sets, grouping together those that impose the same level of additional "unsolvability" beyond standard computability.^[6] The concept originates from Alan Turing's foundational work on the limits of computation. In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," Turing formalized computation using abstract machines—now known as Turing machines—that simulate algorithmic processes on symbols, and he demonstrated the existence of uncomputable functions, most notably the halting problem, which asks whether a given Turing machine halts on a given input.^[7] This result resolved David Hilbert's Entscheidungsproblem negatively by showing that no general algorithm exists to determine the truth of all first-order arithmetic statements, thereby establishing the inherent unsolvability in mathematics and motivating the study of degrees of relative computability.^[7] To explore computations beyond the halting problem, Turing introduced oracle machines in his 1939 dissertation "Systems of Logic Based on Ordinals," which extend standard Turing machines by allowing queries to an external "oracle" set whose membership is assumed decidable instantaneously.^[5] These machines provide a framework for relativized computability, where the power of an oracle measures the "degree" of assistance needed to solve problems. The lowest such degree is \mathbf{0}, the Turing degree of the empty set \emptyset, comprising all recursive (computable) sets that require no oracle beyond a standard Turing machine.^[6] The systematic development of Turing degrees as a structure began with Emil Post's 1944 paper "Recursively Enumerable Sets of Positive Integers and Their Decision Problems," where he coined the term "degrees of unsolvability" to classify sets based on their decision problems' complexity relative to recursive enumeration.^[2] Building on this, Stephen Kleene and Post advanced the theory in the 1950s, particularly through their 1954 collaboration "The Upper Semi-Lattice of Degrees of Recursive Unsolvability," which established key structural properties like the semi-lattice ordering of degrees.^[8]

Turing reducibility and equivalence

A set A \subseteq \mathbb{N} is Turing reducible to another set B \subseteq \mathbb{N}, denoted A \leq_T B, if there exists an oracle Turing machine that computes the characteristic function of A using B as an oracle.^[5] This means the machine can query membership in B during computation, allowing A to be decided relative to B.^[8] Two sets A and B are Turing equivalent, denoted A \equiv_T B, if A \leq_T B and B \leq_T A.^[9] In this case, A and B possess the same computational power relative to each other.^[10] The Turing degree of a set A, denoted \mathbf{d} = \deg(A) or simply \mathbf{d}, is the equivalence class of all sets Turing equivalent to A under \equiv_T.^[8] These classes partition the power set of \mathbb{N} based on relative computability.^[9] For example, all recursive (computable) sets are Turing equivalent to the empty set \emptyset, since they require no oracle queries beyond standard computation.^[10] In contrast, the halting set K = \{e \in \mathbb{N} \mid \varphi_e(e) \downarrow \}, where \varphi_e is the e-th partial recursive function, satisfies K \equiv_T K but K \not\leq_T \emptyset, as K is not computable.^[9] The relation \equiv_T forms an equivalence relation on the family of subsets of \mathbb{N}. It is reflexive because for any A, A \leq_T A via an oracle machine that queries A to compute itself.^[10] It is symmetric because if A \equiv_T B, then B \equiv_T A by the definition of mutual Turing reducibility. Finally, it is transitive: if A \leq_T B and B \leq_T C, then queries to B in the machine for A can be resolved by querying C in the machine for B, so A \leq_T C.^[10]

Formation of Turing degrees

Turing degrees form a partition of the power set of the natural numbers, \mathcal{P}(\omega), into equivalence classes under the relation of Turing equivalence, \equiv_T. Each such class consists of all sets of natural numbers that are computationally equivalent, meaning that any set in the class can compute any other via a Turing reduction, and vice versa. This partitioning arises naturally from the study of relative computability, where sets are grouped based on their mutual solvability as decision problems.^[11]^[3] A key structural feature in the formation of Turing degrees is the concept of a Turing cone, which provides a way to uniquely represent each degree. For a given degree \mathbf{d}, the associated upward cone is the collection of all degrees \mathbf{e} such that \mathbf{e} \geq_T \mathbf{d}, forming an upward-closed class in the structure of degrees. These cones capture the "tail" of the degree hierarchy above \mathbf{d} and are invariant under Turing equivalence, allowing degrees to be identified with these principal filters in the poset.^[12] Every Turing degree contains at least one set whose characteristic function belongs to that degree, ensuring that degrees can be represented by subsets of \omega rather than arbitrary functions. This representation aligns with the focus on decision problems, as the characteristic function of a set encodes membership queries computable relative to the degree.^[13] The collection of all Turing degrees is uncountable, with cardinality $2^{\aleph_0}, as established in early work on recursion theory; each degree is countable (containing only countably many sets, due to the countability of Turing machines), while \mathcal{P}(\omega) has continuum cardinality. This infinitude, shown via diagonalization arguments in the 1940s, underscores the richness of the structure beyond computable sets.^[14]^[3] Turing degrees serve as oracles classifying the computational difficulty of decision problems in computability theory, where a degree \mathbf{d} indicates the minimal oracle power required to solve problems within it. Sets in \mathbf{d} act as oracles enabling solutions to undecidable problems below \mathbf{d}, formalizing hierarchies of unsolvability.^[13]

Core Properties

Partial ordering and basic relations

The Turing degrees are partially ordered by the relation \mathbf{d} \leq \mathbf{e} if and only if there exist representatives D \in \mathbf{d} and E \in \mathbf{e} such that D \leq_T E.^[3] This induces a partial order on the collection of all Turing degrees, denoted \mathcal{D}/\equiv_T or simply \mathbf{D}.^[11] The order is reflexive, as every set is Turing reducible to itself.^[1] Transitivity follows directly from the transitivity of Turing reducibility: if A \leq_T B and B \leq_T C, then A \leq_T C.^[1] Antisymmetry holds by construction of the degrees as equivalence classes: if \mathbf{d} \leq \mathbf{e} and \mathbf{e} \leq \mathbf{d}, then any representatives satisfy A \equiv_T B, so \mathbf{d} = \mathbf{e}.^[11] The partial order has a least element \mathbf{0}, consisting of all recursive sets, since every recursive set is Turing reducible to any set but no non-recursive set is reducible to a recursive one.^[3] The order is unbounded above: for any degree \mathbf{d}, there exist degrees strictly greater than \mathbf{d}.^[15] Degrees above \mathbf{0}'—the jump of \mathbf{0}, which bounds the Turing degrees of all arithmetic sets—include those not computable from any arithmetic oracle, illustrating the hierarchy's extension beyond arithmetical definability.^[11] A degree \mathbf{m} > \mathbf{0} is minimal if no degree \mathbf{x} satisfies \mathbf{0} < \mathbf{x} < \mathbf{m}. The existence of minimal degrees was established by Spector in 1956 using a finite injury priority construction to build a set whose degree has no intermediate elements below it.^[11] Such degrees provide the simplest non-trivial extensions above \mathbf{0} and demonstrate that the order is not a total order, as minimal degrees are incomparable to many others. Basic relations in the order include successor or covering relations, where \mathbf{e} covers \mathbf{d} if \mathbf{d} < \mathbf{e} and no degree lies strictly between them. Minimal degrees above \mathbf{0} are immediate successors to the least element.^[11] More generally, the Turing degrees are rich enough to embed arbitrary countable partial orders while preserving the order relation, a result proved using tree forcings or priority arguments to construct embeddings that respect meets and joins where defined.^[16] This embeddability underscores the complexity and universality of \mathbf{D} as an algebraic structure.

Incomparability and density results

In the poset of Turing degrees ordered by Turing reducibility, two degrees \mathbf{d} and \mathbf{e} are incomparable if neither \mathbf{d} \leq_T \mathbf{e} nor \mathbf{e} \leq_T \mathbf{d}. The existence of such incomparable degrees was demonstrated by Kleene and Post (1954), and later using finite injury priority constructions, where sets A_0 and A_1 are built to ensure mutual non-reducibility by preserving finite approximations at each stage. This result highlights that the structure is not linear, as most pairs of degrees are incomparable, forming a rich antichain of size continuum via perfect tree constructions.^[13] A striking example of incomparable degrees arises from Cohen forcing, where generic extensions add reals that are computationally independent; specifically, forcing with finite partial functions from $2^{<\omega} yields two generics G_0 and G_1 such that their degrees are incomparable, as each generic avoids computing the other due to the forcing conditions preserving independence.^[13] This forcing approach not only proves incomparability but also illustrates the poset's non-linearity through generic filters that evade mutual Turing reductions. However, density does not hold uniformly across all intervals. The existence of minimal degrees—nonzero degrees with no intermediate degrees below them—creates nondense intervals, such as ( \mathbf{0}, \mathbf{m} ) for a minimal \mathbf{m} > \mathbf{0}. Nondensity in specific intervals, such as those created by minimal degrees (Spector, 1956), shows that certain upper cones or bounded regions lack intermediate elements, relying on priority arguments to cap extensions without gaps below. These gaps underscore the intricate, non-uniform structure of the poset, where local rigidity coexists with flexibility in other regions, emphasizing its non-linear and partially dense nature.^[13]

Structural Features

Order-theoretic properties

The Turing degrees form a partial order that is universal among countable partial orders: every countable partial order embeds order-preservingly into the poset of Turing degrees. This universality follows from constructive embedding techniques developed in the 1970s, allowing the realization of arbitrary countable structures within the degrees.^[13] The poset of Turing degrees is an upper semilattice under the natural ordering ≤_T, with the zero degree as its least element. For any two degrees a and b, their join a ∨ b exists and serves as the least upper bound, obtained by taking the Turing degree of the union of representatives. However, the structure is not a lattice, as incomparable degrees do not necessarily possess a greatest lower bound; for instance, there exist pairs of degrees with no meet. This semilattice property highlights the poset's algebraic richness while underscoring its limitations compared to full lattices.^[13] Order ideals in the Turing degrees are defined as nonempty subsets I ⊆ D that include the zero degree, are downward closed (if a ∈ I and b ≤_T a, then b ∈ I), and are closed under joins (if a, b ∈ I, then a ∨ b ∈ I). Principal ideals, generated by a single degree a, consist of all degrees b such that b ≤_T a and form fundamental building blocks for studying local structure. These ideals capture downward-closed portions of the poset and play a key role in analyzing uniformity and bounds within the degrees. For example, the principal ideal below 0' (the degree of the halting problem) contains all Δ²₀ degrees. Upward-closed analogs, known as filters, are closed under meets where they exist but are less emphasized in the order-theoretic study due to the absence of general meets.^[17] The first-order theory of the Turing degrees, denoted Th(D, ≤_T), exhibits significant complexity, yet its existential fragment is decidable. This decidability arises directly from the embedding theorem: an existential sentence is true in D if and only if the finite partial order it describes (via atomic relations) is realizable, which it always is for consistent poset diagrams since all countable posets embed. Harrison orders provide illustrative examples of embeddable structures; these are countable linear orders constructed by Harrison in 1968 that embed non-well-ordered types with maximal well-ordered initial segments of all computable ordinals, demonstrating the poset's capacity to realize intricate countable chains without violating its semilattice properties. However, certain structures exhibit non-embeddability: for instance, D contains no infinite strictly descending sequence of degrees in specific contexts like initial segments below low degrees, reflecting the well-foundedness of the poset, with no infinite strictly descending sequences.^[18] Countable aspects of the poset contrast sharply with uncountable ones. While every countable partial order embeds, the uncountable cardinality of D (equal to the continuum) limits embeddings of larger structures; for example, posets requiring uncountable width beyond the antichain size in certain cones fail to embed fully. The poset thus serves as a universal countable structure but delineates boundaries for uncountable extensions through cardinality and density constraints.^[13]^[11] Martin's cone theorem addresses comeager sets within the degrees, asserting that for certain analytic (e.g., Π¹₁) classes of reals, if the class is comeager in the category sense on 2^ω, then the corresponding set of Turing degrees contains an entire cone—all degrees above some fixed degree c. This theorem implies that "generic" properties in the Baire category topology hold uniformly on tails of the poset, providing a measure-theoretic analog via the Martin measure where such cones have full measure. It underscores the concentration of structural properties in high degrees, linking descriptive set theory to order-theoretic uniformity.^[19]

The Turing jump operation

The Turing jump of a set A \subseteq \omega, denoted A', is defined as the relative halting problem

A' = \{ e \in \omega \mid \varphi_e^A(e) \downarrow \},

where \varphi_e^A denotes the e-th partial computable function relative to the oracle A, and \downarrow indicates that the computation converges (halts).^[20] The Turing degree of A', written \mathbf{d}' = \deg(A') where \mathbf{d} = \deg(A), is called the jump of the degree \mathbf{d}. This operator maps Turing degrees to Turing degrees and captures the increase in computational complexity when considering questions about the halting behavior of oracle machines.^[20] A fundamental property of the jump is that A \leq_T A' for every set A, since membership in A can be decided using the oracle A' by simulating the relevant computations. Moreover, this Turing reduction is strict (A <_T A') unless A is recursive, reflecting the inherent undecidability of the halting problem relativized to any non-recursive oracle.^[20] The jump operator is also monotone with respect to the Turing degree ordering: if \mathbf{d} \leq \mathbf{e}, then \mathbf{d}' \leq \mathbf{e}', preserving the partial order structure on the degrees.^[20] These properties ensure that the jump defines a well-behaved map on the upper semilattice of Turing degrees. Iterating the jump operator on the degree of the empty set yields the jump hierarchy: \mathbf{0}', \mathbf{0}'' = (\mathbf{0}')', \mathbf{0}''', and so on, where \mathbf{0}^{(n)} denotes the n-th iterate. Each level \mathbf{0}^{(n)} corresponds to the Turing degree of the complete sets in the n-th level of the arithmetic hierarchy, specifically the degree of the canonical \Sigma_n^0-complete set (or equivalently, \Pi_n^0-complete set).^[20] For a general degree \mathbf{d}, the iterates \mathbf{d}^{(n)} analogously increase the descriptive complexity, with \mathbf{d}^{(n)} capturing sets definable in arithmetic using n alternations of unbounded quantifiers relativized to \mathbf{d}.^[20] The Friedberg jump theorem establishes a form of surjectivity for the jump above \mathbf{0}': for every Turing degree \mathbf{d} \geq \mathbf{0}', there exists a degree \mathbf{e} such that \mathbf{e}' \equiv_T \mathbf{d}.^[21] This result, proved using a finite injury priority construction, shows that the jump operator is "onto" in the upper cone starting at \mathbf{0}', highlighting the density and richness of the degree structure under iteration.^[22] Overall, the Turing jump systematically elevates degrees by enhancing their unsolvability, with each application corresponding to an increase in the number of quantifiers needed for arithmetic definability.^[20]

Jump inversion and degrees of unsolvability

Jump inversion techniques provide a way to "reverse" the Turing jump operation, constructing degrees whose jump matches a prescribed higher degree. This is crucial for understanding the structure of the Turing degrees, particularly how lower degrees can generate higher ones via relativization. Shoenfield's jump inversion theorem establishes that for any set C such that $0'' \leq_T C and C is recursively enumerable relative to $0'', there exists a set A \leq_T 0' with A' \equiv_T C.^[23] This result, from the late 1950s, demonstrates that degrees above the double jump of the empty set can be realized as jumps of sets computable from the single jump, highlighting the density and connectivity in the upper regions of the degree lattice. Sacks extended jump inversion to the region immediately above the first jump, proving that for any degree d \geq_T 0' where d is the degree of a set recursively enumerable relative to $0', there exists a recursively enumerable set B such that B' \equiv_T d.^[24] This theorem, published in 1963, applies specifically to recursively enumerable bases and underscores the role of r.e. degrees in generating the structure just beyond $0'. Together, these inversion results show that the jump operator is surjective onto certain classes of degrees greater than $0', allowing for precise constructions in proofs of density and embedding theorems within the Turing degrees. Degrees of unsolvability classify Turing degrees according to their "level" of computational difficulty, measured by the minimal ordinal \alpha such that the \alpha-th iterate of the Turing jump on the degree exceeds the corresponding iterate on the empty set in a specific way. Formally, for an ordinal \alpha, the \alpha-degrees consist of those d where the jump hierarchy up to \alpha behaves like that of $0^{(\alpha)}, but deviates at \alpha. This notion, developed in the 1950s, provides a ordinal-indexed stratification of the degrees, generalizing finite iterations to transfinite ones and facilitating comparisons across the entire lattice.^[25] Within this classification, low degrees are those d satisfying d' \equiv_T 0', meaning their jump is no harder than the halting problem itself; such degrees represent minimal extensions beyond recursive sets in terms of unsolvability. In contrast, high degrees are defined by d' >_T 0' yet d'' \equiv_T 0'', capturing sets whose single jump is properly above $0' but whose double jump aligns with the double halting problem. These notions, central to analyzing the jump's behavior, were key in early structural results on incomparability and ordering properties. A notable application of low degrees arises in extensions of theories: every consistent recursively enumerable theory admits a completion of low Turing degree, ensuring that the added axioms do not increase the unsolvability beyond the first jump level.^[26] This result, from Feferman's work in the late 1950s, connects degrees of unsolvability to model-theoretic completeness and has implications for the computability of axiomatic systems. Post's coverage theorem asserts that every Turing degree is Turing reducible to a finite iterate of the jump of some recursively enumerable set, meaning the finite jumps from r.e. degrees encompass the entire structure of unsolvability levels. This coverage, outlined in foundational work on recursively enumerable predicates, emphasizes the generative power of r.e. sets under iterated relativization.

Arithmetic and hyperarithmetic degrees

The arithmetic Turing degrees comprise the collection of degrees d such that d ≤_T 0^{(n)} for some finite n, where 0^{(n)} denotes the n-th iterate of the Turing jump operator applied to the degree of the empty set. These degrees capture the computational complexity of arithmetic sets, which form the levels of the arithmetic hierarchy in descriptive set theory: a set belongs to Σ_n^0 (or Π_n^0) if it is definable by a formula with n alternating quantifiers beginning with existential (or universal), and the corresponding degrees satisfy deg_T(A) ≤_T 0^{(n)} for A in Σ_n^0 ∪ Π_n^0.^[13] The hierarchy is strict, as 0^{(n)} <_T 0^{(n+1)} for each n, reflecting increasing quantifier complexity and unsolvability degrees.^[13] The structure of the arithmetic degrees exhibits significant order-theoretic and logical features. The poset of arithmetic degrees below 0' is bi-interpretable with the true first-order theory of natural numbers, providing a model for Peano arithmetic whose completeness captures the arithmetic truths up to finite quantifier alternations.^[13] More broadly, the full arithmetic degrees form an upper semilattice under Turing join, with embeddings and exact pairs allowing representations of Boolean algebras within initial segments, as shown through coding mechanisms and ideal intersections.^[13] Basis theorems, such as the Kleene-Post construction, ensure the existence of incomparable arithmetic sets via finite approximations recursive in 0', facilitating the density and branching structure of the hierarchy.^[13] The hyperarithmetic Turing degrees extend the arithmetic hierarchy transfinitely, consisting of degrees d ≤_T 0^ω, where 0^ω is the hyperjump, the supremum of 0^{(α)} over computable ordinals α < ω_1^{CK}. These degrees correspond to hyperarithmetic sets, which are precisely those computable relative to some ordinal notation in Kleene's O, a complete Π_1^1 set serving as a notation system for recursive ordinals less than the Church-Kleene ordinal ω_1^{CK}, the least non-recursive ordinal.^[13] Hyperarithmetic sets coincide with the lightface Δ_1^1 definable sets relative to the empty set and populate the smallest β-model of second-order arithmetic.^[13] Key structural results for hyperarithmetic degrees include basis theorems generalizing the arithmetic case. In particular, every hyperarithmetic degree admits a hyperarithmetic basis, meaning it contains a set that is hyperarithmetic and realizes the full degree via uniform constructions from notations in Kleene's O, as established in the 1960s.^[13] Additional basis results, such as the low basis theorem, guarantee that infinite recursive trees have hyperarithmetic paths of controlled jump degree, ensuring cone avoidance and minimal covers within the hyperarithmetic structure.^[13] These properties link the hyperarithmetic degrees to descriptive set theory, where paths through trees recursive in O yield representatives for all hyperarithmetic complexities.^[13]

Recursively Enumerable Degrees

Structure of r.e. Turing degrees

The recursively enumerable (r.e.) Turing degrees comprise the equivalence classes under Turing equivalence of sets that include at least one r.e. set, forming an upper semilattice subposet of the full Turing degrees ordered by Turing reducibility.^[13] This subposet differs markedly from the full structure, as it is confined to degrees arising from r.e. sets, which impose computability constraints absent in the broader poset; for instance, the r.e. degrees embed all countable partial orders but exhibit specific gaps and density properties tied to enumerability.^[27] A fundamental distinction is the absence of any r.e. degree strictly between the degree 0 of the recursive sets and the degree 0' of the halting problem K, as Post proved that every non-recursive r.e. set A satisfies K ≤_T A, implying all nonzero r.e. degrees are at least 0'. Above 0', however, the r.e. degrees satisfy Sacks' density theorem: for any nonrecursive r.e. degrees a < b, there exists an r.e. degree c with a < c < b. This partial density highlights a key structural irregularity compared to the full Turing degrees, which are dense throughout. Maximal r.e. sets, constructed by Friedberg in 1958, provide insight into upper aspects of the structure; these are infinite r.e. sets A such that no infinite r.e. set properly extends A modulo finite sets, and their Turing degrees are simple, containing no infinite r.e. sets below them other than recursive ones. Such degrees are not dominated by other r.e. degrees in the inclusion sense for their representatives but remain extendable in the full poset, underscoring the r.e. subposet's lack of maximal elements, as every r.e. chain is infinite.^[13] In the r.e. context, productive sets—whose complements are creative r.e. sets like \bar{K}—characterize the complete r.e. degrees at 0', as Post showed that a set is productive if and only if the halting problem many-one reduces to it, linking productivity directly to the foundational gap at 0'. Computably enumerable (c.e.) traces, sequences of uniformly c.e. sets bounding the graphs of functions computable from a degree, further illuminate r.e. structure by enabling constructions of traceable r.e. degrees, which admit universal c.e. traces relative to oracles and connect to lowness properties within the poset.^[28] The r.e. degrees also feature non-branching elements, where a degree a is non-branching if there do not exist incomparable b, c > a with b ∧ c = a; such degrees exist and are dense in the r.e. poset, as Fejer proved using priority methods to interpolate non-branching degrees between any two r.e. degrees.^[29] This contrasts with branching degrees, which allow such splittings, and emphasizes the r.e. subposet's richer order-theoretic behavior above 0' compared to its isolated bottom interval.

Hierarchies within r.e. degrees

Within the recursively enumerable (r.e.) Turing degrees, hierarchies classify degrees by increasing levels of complexity, often measured through relative computability or construction dynamics. These hierarchies refine the overall structure of the r.e. poset by identifying subclasses with specific embedding or definability properties. Post introduced simple sets in 1944, defining them as r.e. sets whose complements are infinite but contain no infinite r.e. subsets. These degrees form a foundational minimal class above 0 in the r.e. poset, as no nonzero r.e. degree lies strictly between 0 and a simple degree.^[30] Low r.e. degrees, where an r.e. degree a satisfies a' ≡_T 0', represent sets whose Turing jumps remain at the base level of unsolvability. This class is dense in the r.e. degrees and crucial for splitting theorems, such as the decomposition of any nonzero r.e. degree into two low r.e. degrees. Low r.e. degrees also generate the full r.e. poset under finite joins.^[31] In the 2000s, Hirschfeldt and Jockusch developed classes like D²-minimal degrees, which are minimal over structures involving the double jump, and prompt degrees, refining simplicity via the timing of enumeration in priority constructions. Prompt degrees coincide with promptly simple degrees, a nonzero r.e. class that resists capping by low r.e. degrees and aligns with array computable degrees in algebraic decompositions.^[32]^[33] Transfinite hierarchies extend this classification using ordinals less than the Church-Kleene ordinal ω₁^CK. A set is α-r.e. if it is r.e. relative to the α-th Turing jump of the empty set, forming the α-r.e. degrees that capture ordinal-level complexity within r.e. sets. Soare's 1980s results established the density of these degrees and their embedding properties, showing that the α-r.e. hierarchy mirrors aspects of the full r.e. structure for α < ω₁^CK. Extensions in the 2020s incorporate dynamics from forcing and priority methods to refine these hierarchies. The Downey-Greenberg hierarchy of c.e. degrees, based on computable ordinal notations for construction "unboundedness," unifies lowness classes like totally ω-c.e. degrees and provides Σ₃⁰ definability for key subclasses.^[34] Downey and Hirschfeldt's 2021 survey highlights applications of this dynamic hierarchy to coding models of arithmetic and measuring construction complexity in c.e. degrees. New directions explore strengthened promptness, such as strong promptness implying promptly simple degrees, and slenderness, relating to non-cupping behaviors in array noncomputable r.e. degrees.^[35]^[36] Downey and Greenberg's 2020 monograph integrates classical hierarchies like α-r.e. degrees with modern dynamic classifications, offering a unified view of r.e. degree structures through transfinite lowness notions.^[37]

Advanced Results and Techniques

Post's problem

Post's problem, posed by Emil Post in the 1940s, asked whether there exist recursively enumerable (r.e.) Turing degrees strictly between the degree of the empty set (0) and that of the halting set (0'). Post hoped that simple sets could serve as incomplete representatives for such degrees. A simple set is defined as an r.e. set whose complement is infinite but immune, meaning the complement contains no infinite r.e. subset. This question arose from Post's efforts to understand the structure of r.e. degrees and to find representatives that "simplify" the theory by avoiding complete degrees. In 1944, Post attempted to construct simple sets motivated by his earlier work on creative sets, which are r.e. sets equipped with a productive function allowing diagonalization over all partial recursive functions. His approach sought to show that simple sets could serve as incomplete representatives for non-zero r.e. degrees, but the construction failed, leaving the problem open and highlighting the limitations of direct diagonalization techniques. The affirmative solution to Post's problem was established through the development of the priority method by Richard M. Friedberg and A. A. Muchnik in 1957. Their finite injury priority arguments not only solved the related question of the existence of incomparable non-zero r.e. degrees but also enabled constructions showing that every non-zero r.e. degree contains a simple set. Specifically, Donald A. Martin formalized this in 1966, proving that every non-zero r.e. degree contains both a hypersimple set (an r.e. set whose complement is immune with respect to a computable enumeration of r.e. sets), as previously shown by J. C. E. Dekker in 1954, and a simple set that is not hypersimple. Related questions emerged concerning stronger notions of simplicity, such as whether every non-zero r.e. degree contains a hypersimple set, which it does, as shown by Dekker's theorem. Immunity plays a central role here, as the complement of a simple or hypersimple set is immune, ensuring no infinite r.e. subsets exist within it to "contaminate" the diagonalization process. These results underscored the density and complexity of the r.e. degrees below \mathbf{0}'. The resolution of Post's problem had profound implications for degree theory, as the priority method introduced by Friedberg and Muchnik resembled forcing techniques in set theory, allowing controlled injuries to requirements during constructions. This innovation sparked a vast array of advanced results in the structural analysis of Turing degrees, including hierarchies and splitting theorems within the r.e. degrees.

Priority method and its variants

The finite injury priority method is a foundational technique in computability theory for constructing recursively enumerable (r.e.) sets with specific Turing degrees by managing conflicts among multiple requirements during the construction process. Requirements are assigned priorities, with higher-priority requirements having the authority to "injure" (temporarily disrupt) lower-priority ones, but each lower-priority requirement is injured only finitely many times, ensuring eventual stabilization. This method was independently developed by Richard Friedberg and Albert Muchnik to address longstanding problems in the structure of r.e. degrees. The method resolves Post's problem by constructing an r.e. set that is neither computable nor Turing equivalent to the halting problem (i.e., of degree 0'), thereby demonstrating the existence of incomplete non-computable r.e. degrees greater than 0. In the construction, positive requirements ensure the set is incomplete by diagonalizing against all computable enumerations of sets of degree 0', while negative requirements protect simplicity-like properties but allow controlled violations to avoid completeness; higher priorities handle global constraints, injuring lower ones finitely often to permit the overall construction to succeed. This yields a simple r.e. set in every degree strictly above 0. Variants of the priority method extend its applicability to more complex structures. The infinite injury priority method, introduced by Gerald Sacks, allows certain requirements to be injured infinitely often but in a controlled manner that preserves essential outcomes, enabling proofs of density theorems for r.e. degrees, such as the existence of r.e. degrees incomparable to a given non-computable r.e. degree.^[38] Tree methods, pioneered by Clifford Spector, employ perfect trees of finite approximations to force minimal degrees—non-zero degrees with no intermediate degrees below them—by ensuring that extensions on the tree satisfy requirements without global injury limits. Forcing with trees, a refinement akin to Sacks forcing, uses computable perfect trees to construct generics or embeddings in the Turing degrees, facilitating local structural results like initial segments.^[11] Applications of priority methods extend beyond Turing degrees to weaker reducibilities. In Muchnik degrees (under weak truth-table reducibility), the finite injury method constructs incomparable degrees, mirroring its role in Turing degrees and highlighting structural parallels between the two partial orders. Sacks' infinite injury variant proves the splitting theorem: any non-computable r.e. degree can be partitioned into two incomparable low r.e. degrees whose join is the original, preserving relative incomputability. Despite their power, priority methods have limitations in constructing certain generic objects within r.e. degrees. For instance, no r.e. set is Cohen 1-generic (meeting all density requirements for computable dense sets of strings), as any r.e. approximation would fail to satisfy the forcing conditions for avoiding computable predictions, a result unattainable by priority constructions focused on finite or controlled injuries.

Recent developments in degree hierarchies

Recent advances in the structure of Turing degree hierarchies have emphasized transfinite extensions within the computably enumerable (c.e.) degrees, introducing new scales that capture the complexity of approximations to functions in these degrees. Downey and Greenberg's 2020 monograph establishes a transfinite hierarchy of lowness notions, known as the α-c.a. degrees for ordinals α < ε₀, where a degree is totally α-c.a. if it can approximate total functions with changes bounded by α-computable norms. This framework unifies classical classes such as the low₂, tt-low, and high degrees, revealing natural definability results for degree structures through dynamic constructions that model the rate of change in computable approximations. The hierarchy demonstrates that certain upper cones collapse, meaning that for some α, the totally α-c.a. degrees coincide with all c.e. degrees above a certain point, providing insights into the global organization of the c.e. Turing degrees. ^[39] Building on this, Downey, Greenberg, and Hammatt's 2021 survey explores further developments, including interactions with maximality and collapse in upper cones of the α-c.a. hierarchy. These extensions incorporate game-theoretic elements, where constructions simulate infinite games between players controlling approximation changes, leading to finer classifications of c.e. degrees based on permission-granting mechanisms like prompt permissions. Prompt degrees, which allow rapid enumeration in requirements, play a key role in separating classes within the hierarchy and constructing minimal pairs of separating classes. Such dynamics highlight how transfinite scales address gaps in classical coverage by quantifying the "slowness" of degrees relative to oracles. Connections between Turing degrees and reverse mathematics have seen novel integrations in recent work, with emphasis on the computational strength required for proofs in subsystems like ACA₀ and ATR₀. Soare's foundational contributions continue to influence these directions, as seen in analyses of how Turing degrees correspond to the provability of comprehension axioms over partial orders. In parallel, Jockusch and Lewis-Pye's 2022 results on multiple genericity introduce a transfinite hierarchy of genericity notions between 1- and 2-genericity, refining the fine structure of degrees below generics and linking slenderness properties—where degrees avoid certain dense sets—to prompt-like behaviors in forcing constructions. ^[40] Algorithmic randomness has intersected with degree hierarchies through studies of Martin-Löf random degrees, where Nies and collaborators in the 2020s have characterized their positions relative to the hyperarithmetic hierarchy. For instance, every PA degree is the join of two Martin-Löf random degrees, and random degrees form dense structures below 0', with hierarchies emerging from relativized randomness notions like continuous measures. These results extend classical r.e. hierarchies by incorporating measure-theoretic tests that distinguish random degrees from non-random ones in Turing incomparable pairs. Despite progress, key open problems persist, particularly the full classification of Turing degrees below 0'. Martin's conjecture posits that Borel determinacy implies uniformity in the complexity of Borel equivalence relations on cones of degrees, but partial results via Borel determinacy have only confirmed conal properties without resolving universality of Turing equivalence. Recent advances using determinacy axioms have clarified that no Borel equivalence relation is universal among countable ones, yet the exact structure below 0' remains elusive. ^[12]

References

[1]
[PDF] Computability theory - Berkeley Math
Feb 25, 2024 · Key to proving Gödel and Turing's theorems was making a precise definition of a computable function. For centuries, mathematicians had an ...Missing: authoritative | Show results with:authoritative
[2]
Recursively enumerable sets of positive integers and their decision ...
A set of positive integers is recursively enumerable if there is a recursive function whose values, for positive integral values of x, constitute the given set.
[3]
[PDF] Turing degrees - Yuzhou Gu
Introduction. Turing degrees, defined by Post [Pos44], measure the degree of undecidability of sets. All recursive sets can be decided by a Turing machine, ...Missing: authoritative sources
[4]
[PDF] The theory of computability - People
The theory of computability. The Turing degrees and relative computability. Page 2. What is computability theory? □ In computability theory we study ...
[5]
[PDF] Systems of logic based on ordinals (Proc. Lond. Math. Soc., series 2 ...
Turing considered several natural ways in which ordinal logics could be constructed: (i) A p, obtained by successively adjoining statements directly overcoming ...
[6]
Recursive Functions - Stanford Encyclopedia of Philosophy
Apr 23, 2020 · ... degrees. Together with the similar study of the Turing degrees (which will be defined in Section 3.5.2), investigating the structure of ...
[7]
[PDF] ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ...
The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
[8]
The Upper Semi-Lattice of Degrees of Recursive Unsolvability - jstor
A direct proof of the equivalence of Turing reducibility to general recursive reducibility was published (independently) by. Kleene in his book [10] end ??68, ...
[9]
RECURSIVELY ENUMERABLE SETS AND DEGREES - Project Euclid
Jul 10, 1978 · As a special case of Turing reducibility. Post defined A ... [Ma3]. , Classes of recursively enumerable sets and degrees of unsolvability, Z.
[10]
https://www.math.uchicago.edu/~may/REU2014/REUPapers/Chung.pdf
[11]
[PDF] Defining the Turing Jump - UC Berkeley math
computability or Turing reducibility (from Turing (1939)). We say that A is computable from (or recursive in) B if there is a Turing machine which, when ...
[12]
[PDF] Embeddings into the Turing degrees - Berkeley Math
Apr 4, 2007 · ... Turing degrees was introduced by Kleene and Post in 1954 [KP54]. Since then, its study has been central in the area of Computability Theory.
[13]
[PDF] martin's conjecture: a classification of the naturally occurring turing ...
This paper is about naturally occurring objects in computability theory, the area inside mathematical logic that studies the complexity of infinite ...
[14]
[PDF] The Turing Degrees: Global and Local Structure - Cornell Mathematics
May 20, 2015 · . This basic approach, due to Kleene and Post, will be used for most of our constructions of degrees. It is a forerunner of the general ...
[15]
[PDF] Historical Perspectives - Computer Science
• Turing (1937); studied by Post (1944) and Kleene (1954) ... • Each Turing degree is countably infinite (has exactly ℵ. 0 sets). • There are uncountably many (2.<|separator|>
[16]
[PDF] undecidability and the structure of the turing degrees - UChicago Math
Oct 1, 2018 · Abstract. This paper explores the structure and properties of the Turing degrees, or degrees of undecidability. We introduce the Turing ...
[17]
[PDF] Embedding Partial Orderings in Degree Structures
Every countable partial ordering can be embedded. 1. Kleene and Post: in the Turing degrees, even in the ∆0. 2. Turing degrees. 2. Muchnik: in the c.e. Turing ...
[18]
[PDF] Uniform Upper Bounds on Ideals of Turing Degrees - PhilArchive
Uniform Upper Bounds on Ideals of Turing Degrees ... The relation "Iis an ideal and a is the jump of a u.u.b. on I" is first-order definable over (D, _,,').<|control11|><|separator|>
[19]
Enumerations of Turing Ideals with Applications - Project Euclid
Abstract We examine enumerations of ideals in the Turing degrees and give several applications to the model theory of first- and second-order arithmetic. A ...
[20]
Martin's cone theorem and recursion theory - MathOverflow
Nov 10, 2010 · Since x <T j(x) for all x, A is cofinal in the Turing degrees. Hence assuming Projective Determinacy, A must contain a cone in the Turing ...
[21]
Martin measure - Wikipedia
In descriptive set theory, the Martin measure is a filter on the set of Turing degrees of sets of natural numbers, named after Donald A. Martin.
[22]
[PDF] Defining the Turing Jump - UC Berkeley math
They define A, the degrees of the arithmetic sets, i.e. those sets definable in arithmetic with quantification only over numbers, in order-theoretic terms ...
[23]
[PDF] Background on Turing Degrees and Jump Operators
Existence of Non-Hyperarithmetical Functions – Kleene's O. A cardinality argument shows that existence of non-hyperarithmetical functions. As a particular ...
[24]
three theorems on recursive enumeration. i. decomposition. ii ...
THREE THEOREMS ON RECURSIVE ENUMERATION. I. DECOMPOSITION. II. MAXIMAL SET. III. ENUMERATION. WITHOUT DUPLICATION. RICHARD M. FRIEDBERG. In this paper we shall ...
[25]
On Degrees of Unsolvability - jstor
BY J. R. SHOENFIELD. (Received April 3, 1958). In this paper we present ... CLIFFORD SPECTOR, On degrees of recursive unsolvability, Ann. of Math., 64 ...
[26]
On the Degrees Less than 0<sup> - jstor
His theorem states that each non-recursive, recursively enumerable set is the union of two disjoint, non-recursive, recursively enumerable sets. Page 8. 218 ...
[27]
On Degrees of Recursive Unsolvability - jstor
This paper con- stitutes Part I of the author's Ph.D. thesis: On degrees of recursive unsolvability and re- cursive well-orderings, at the University of ...
[28]
Arithmetization of metamathematics in a general setting - EuDML
Arithmetization of metamathematics in a general setting. S. Feferman · Fundamenta Mathematicae (1960). Volume: 49, Issue: 1, page 35-92; ISSN: 0016-2736 ...Missing: Unsolvable Problems
[29]
https://www.sciencedirect.com/science/article/pii/0168007283900283
[30]
[PDF] tracing and domination in the turing degrees - George Barmpalias
A degree a c.e. traceable, if there is a computable function h such that every function f ≤T a has a c.e. trace with bound h. • (Simpson, 2006) Is there a ...
[31]
The density of the nonbranching degrees - ScienceDirect
The results in this paper are part of the author's doctoral dissertation, written at the University of Chicago under Professor Robert I. Soare. Copyright © 1983 ...Missing: non- branching
[32]
Degrees of Unsolvability - Cambridge University Press & Assessment
Subjects: Mathematics, Logic, Categories and Sets, Abstract Analysis, Programming Languages and Applied Logic ; Series: Perspectives in Logic (11).
[33]
[PDF] prompt simplicity, array computability and cupping
Introduction. The main class examined in this paper is the class of array computable degrees introduced by Downey, Jockusch and Stob in [11, 12].
[34]
On Minimal Pairs of Enumeration Degrees - jstor
Yates [19] was a minimal pair of low r.e. degrees. COROLLARY 12.1. Any lattice embedding in the low r.e. degrees is a lattice embedding in the e-degrees.
[35]
A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES
Apr 26, 2018 · We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity ...
[36]
A Hierarchy of Computably Enumerable Degrees II
Sep 19, 2021 · A transfinite hierarchy of Turing degrees of ce\ sets has been used to calibrate the dynamics of families of constructions in computability theory.Missing: via Hirschfeldt
[37]
[PDF] Strengthening prompt simplicity
Abstract. We introduce a natural strengthening of prompt simplicity, and study its relationship with existing lowness classes. We show that this notion is ...
[38]
https://www.cs.umd.edu/~gasarch/BLOGPAPERS/infinj.pdf
[39]
[PDF] The Infinite Injury Priority Method - UMD Computer Science
The next corollary is a weak form of the Sacks Jump Theorem (Theorem 4.2) below and implies that there are infinitely many r.e. degrees d which are high. (d' = ...
[40]
[PDF] A Hierarchy of Turing Degrees
As we shall see, in this monograph we introduce a transfinite hierarchy of ... the c.e. degrees (Lachlan and Soare [62]). Thus, the 1-3-1 lattice is “just ...
[41]
Multiple genericity: a new transfinite hierarchy of genericity notions
Aug 11, 2022 · We introduce a transfinite hierarchy of genericity notions stronger than 1-genericity and weaker than 2-genericity.<|separator|>