Fact-checked by Grok 2 weeks ago

Arithmetical hierarchy

The arithmetical hierarchy is a hierarchy of sets of natural numbers classified according to their definability using arithmetic formulas with a fixed number of alternating unbounded quantifiers, introduced independently by Stephen C. Kleene in 1943 and Andrzej Mostowski in 1946 to extend the notions of recursive and recursively enumerable sets in . It partitions the collection of all arithmetical sets—those definable in the language of Peano arithmetic without set quantifiers—into increasingly complex levels based on quantifier complexity, providing a measure of descriptive complexity within the framework of classical recursion theory. The is structured into three primary families of levels for each n \geq 0: the \Sigma_n^0 () class, consisting of sets definable by formulas with n alternating quantifiers beginning with an existential quantifier (\exists) followed by a decidable ; the \Pi_n^0 (pi) class, defined similarly but starting with a universal quantifier (\forall); and the \Delta_n^0 () class, which is the intersection of \Sigma_n^0 and \Pi_n^0. At the base level, \Sigma_0^0 = \Pi_0^0 = \Delta_0^0 comprises the recursive (decidable) sets, while \Sigma_1^0 corresponds to the recursively enumerable (r.e.) sets, and \Pi_1^0 to their complements, the co-r.e. sets. Higher levels capture sets requiring more quantifiers, such as the totality set TOT of indices for total computable functions, which is \Pi_2^0-complete, illustrating how the refines the undecidability results from by quantifying over s. Key properties include closure under certain operations: \Sigma_n^0 is closed under , finite unions, and intersections, while \Pi_n^0 is closed under ; moreover, the complement of a \Sigma_n^0 set is \Pi_n^0, ensuring duality between levels. The hierarchy is strict, as established by the Arithmetical Hierarchy Theorem, which proves proper inclusions like \Sigma_n^0 \subsetneq \Delta_{n+1}^0 for each n \geq 0, using to construct sets not reducible to lower levels. Equivalently, in terms of oracle Turing machines, a set is in \Sigma_n^0 if it is recursively enumerable relative to the (n-1)-th of the \emptyset^{(n-1)}, linking the hierarchy to degrees of unsolvability. This classification is fundamental in for analyzing the limits of algorithmic decidability, influencing areas like and descriptive set theory by distinguishing problems solvable with bounded resources from those requiring unbounded search. For instance, the set of finite r.e. sets belongs to \Sigma_2^0 but not \Pi_1^0, demonstrating non-trivial separations that underpin Post's problem on the existence of incomplete r.e. sets, resolved affirmatively in higher levels.

Definitions

Arithmetical Formulas

Arithmetical formulas are formulas in the of Peano arithmetic, which consists of the constant symbol , function symbols for successor (S), (+), and (×), and the logical symbols including quantifiers ∃ and ∀ over natural numbers. These formulas classify predicates on natural numbers based on the complexity of their quantifier prefixes, forming the syntactic basis of the arithmetical hierarchy introduced by Kleene. Unlike formulas in higher hierarchies such as the analytical hierarchy, arithmetical formulas involve only quantifiers ranging over natural numbers, without second-order quantifiers over sets or functions. To classify them, arithmetical formulas are typically brought into prenex normal form, where all quantifiers are moved to the front of the formula, followed by a quantifier-free matrix. The level in the hierarchy is determined by the number of alternations between blocks of existential (∃) and universal (∀) quantifiers in this prefix. The matrix is a Δ₀⁰ formula, which is quantifier-free or equivalently expressible using only bounded quantifiers (of the form ∃x ≤ t or ∀x ≤ t, where t is a term). This structure allows for a precise inductive definition of the hierarchy levels. The base level consists of Σ₀⁰ and Π₀⁰ , which coincide and are exactly the Δ₀⁰ : those in prenex form with no unbounded quantifiers, i.e., only bounded quantifiers or quantifier-free. For higher levels, the classes are defined inductively as follows:
  • A φ is Σ_{n+1}^0 if it is equivalent to ∃x₁ ∃x₂ … ∃x_k ψ, where ψ is a Π_n^0 (with k ≥ 1). Equivalently, in prenex form, it begins with a block of one or more existential quantifiers followed by a Π_n^0 .
  • A φ is Π_{n+1}^0 if it is equivalent to ∀x₁ ∀x₂ … ∀x_k ψ, where ψ is a Σ_n^0 (with k ≥ 1). Equivalently, in prenex form, it begins with a block of one or more universal quantifiers followed by a Σ_n^0 .
  • A φ is Δ_n^0 (for n ≥ 1) if it is equivalent to both a Σ_n^0 and a Π_n^0 . Note that Δ_0^0 = Σ_0^0 = Π_0^0, and in general Δ_n^0 properly contains Δ_m^0 for all m < n ≥ 1.
These definitions ensure that the hierarchy captures increasing expressive power through quantifier alternations, with Σ_n^0 formulas starting with existential blocks and Π_n^0 with universal blocks. For example, a Σ_1^0 formula has the form ∃x ψ(x, \vec{y}), where ψ is Δ_0^0, while a Π_2^0 formula has ∀x ∃z θ(x, z, \vec{y}), with θ Δ_0^0. This classification extends to defining sets of natural numbers, but the focus here is on the syntactic structure of the formulas themselves.

Definable Sets of Natural Numbers

In first-order arithmetic, subsets of the natural numbers are classified within the arithmetical hierarchy based on the definability of those sets using formulas of bounded quantifier complexity. A set S \subseteq \mathbb{N} belongs to the class \Sigma_n^0 if there exists a formula \phi(x, y_1, \dots, y_k) in the \Sigma_n^0-form (with n alternating unbounded quantifiers beginning with existential) and natural number parameters a_1, \dots, a_k \in \mathbb{N} such that S = \{ m \in \mathbb{N} \mid \mathbb{N} \models \phi(m, a_1, \dots, a_k) \}. Here, the formula \phi is interpreted in the standard model of arithmetic (\mathbb{N}, 0, S, +, \times), and the parameters allow for the specification of particular instances while keeping the definition effective. Similarly, S is in \Pi_n^0 if it can be defined by a \Pi_n^0-formula, which has n alternating unbounded quantifiers starting with universal, using the same parameter structure: S = \{ m \in \mathbb{N} \mid \mathbb{N} \models \psi(m, a_1, \dots, a_k) \} for some \Pi_n^0-formula \psi. The class \Delta_n^0 consists of sets that are both \Sigma_n^0 and \Pi_n^0, meaning they admit equivalent definitions in either form with appropriate parameters. These parameters, being tuples of natural numbers, enable the definability to capture a wide range of effectively describable sets while maintaining the hierarchy's focus on quantifier alternation. The role of such parameters is crucial, as they ground the abstract formulas in concrete numerical witnesses, ensuring the classes are closed under effective operations like Turing reductions. This classification employs lightface notation to denote the arithmetical (parameter-restricted to natural numbers) version of the hierarchy, distinguishing it from the boldface variant, which permits parameters from the reals \mathbb{R} (or equivalently, infinite sequences of naturals). The lightface hierarchy emphasizes effective definability within arithmetic, aligning with computability concerns. The arithmetical hierarchy, including these definable sets, was introduced by in the 1940s through his work on , utilizing to encode formulas and relate them to computable functions.

Notation

The standard notation for the arithmetical hierarchy classifies formulas and sets based on the number of alternations of quantifiers in first-order arithmetic over the natural numbers. The class \Sigma_n^0 denotes formulas in prenex normal form with exactly n alternations of quantifiers, beginning with an existential quantifier \exists, followed by a quantifier-free matrix using only computable predicates; the superscript $0indicates that all quantifiers range over natural numbers\mathbb{N}$, distinguishing it from higher hierarchies involving quantifiers over sets or functions. Dually, \Pi_n^0 denotes formulas with n alternations beginning with a universal quantifier \forall, again with quantifiers over \mathbb{N} and a computable matrix. The class \Delta_n^0 is defined as the intersection \Sigma_n^0 \cap \Pi_n^0, comprising sets or formulas expressible in both forms. This notation applies to both syntactic objects (formulas) and semantic ones (sets of natural numbers): a set A \subseteq \mathbb{N} belongs to \Sigma_n^0 if there exists a \Sigma_n^0 formula \phi(x, \vec{y}) and fixed natural numbers \vec{c} such that A = \{ m \in \mathbb{N} \mid \mathbb{N} \models \phi(m, \vec{c}) \}. For finite n \geq 0, the classes form a strict hierarchy with \Delta_0^0 = \Sigma_0^0 = \Pi_0^0 \subsetneq \Delta_1^0 \subsetneq \Delta_2^0 \subsetneq \cdots, where \Delta_n^0 = \Sigma_n^0 \cap \Pi_n^0, and moreover \Sigma_n^0 \subsetneq \Sigma_{n+1}^0, \Pi_n^0 \subsetneq \Pi_{n+1}^0; the base case \Sigma_0^0 consists of computable (recursive) predicates. The entire arithmetical hierarchy is the union \bigcup_{n=0}^\infty \Sigma_n^0 = \bigcup_{n=0}^\infty \Pi_n^0 = \bigcup_{n=0}^\infty \Delta_n^0, known simply as the class of arithmetical sets. In contrast, the analytical hierarchy uses superscript $1(e.g.,\Sigma_n^1) for classes involving second-order quantifiers over subsets of \mathbb{N}$, but the arithmetical notation remains focused on first-order quantifiers. This notational system originated in Kleene's development of the hierarchy, with the \Sigma and \Pi symbols drawing from traditional logical notation for existential and universal quantifiers, respectively.

Properties

Closure and Inclusion

The classes \Sigma_n^0 and \Pi_n^0 in the arithmetical hierarchy exhibit specific closure properties under Boolean operations. The class \Sigma_n^0 is closed under finite unions, meaning that if A_1, \dots, A_k \in \Sigma_n^0, then \bigcup_{i=1}^k A_i \in \Sigma_n^0, as the existential quantifiers can be combined disjunctively. Similarly, \Pi_n^0 is closed under finite intersections, so if B_1, \dots, B_k \in \Pi_n^0, then \bigcap_{i=1}^k B_i \in \Pi_n^0, reflecting the conjunctive nature of universal quantifiers. Both classes are also closed under finite unions and intersections more generally, as well as under bounded quantification and recursive substitutions. The hierarchy features strict inclusions between consecutive levels. Specifically, \Sigma_n^0 \subsetneq \Sigma_{n+1}^0 and \Pi_n^0 \subsetneq \Pi_{n+1}^0 for each n \geq 0. These inclusions are proper, as demonstrated by diagonalization arguments that construct sets in \Sigma_{n+1}^0 not definable in \Sigma_n^0; for instance, a diagonal set D satisfying x \in D \iff \neg \phi_e(x,x) for an enumerator \phi_e of \Sigma_n^0 formulas leads to a contradiction if D were in \Sigma_n^0. Post's theorem further supports this strictness by linking the levels to , showing that each \Sigma_n^0 contains sets of distinct degrees not reducible to lower levels. Consequently, the hierarchy does not collapse, remaining infinite with no level equaling the next. The diagonal classes are defined as \Delta_n^0 = \Sigma_n^0 \cap \Pi_n^0, consisting of sets expressible both existentially and universally at level n. These sets are closed under complementation, since membership in \Delta_n^0 implies the complement is also in both \Sigma_n^0 and \Pi_n^0. Moreover, \Delta_n^0 \subsetneq \Delta_{n+1}^0, as the strict inclusions of the surrounding classes ensure that higher levels introduce new decidable properties relative to oracles. The union \bigcup_{n=0}^\infty \Sigma_n^0 (equivalently \bigcup_{n=0}^\infty \Pi_n^0) comprises all arithmetical sets, those definable by formulas with finitely many alternations of quantifiers over natural numbers. This exhausts the hierarchy without reaching the full power set of the naturals.

Complementation and Reducibility

In the arithmetical hierarchy, the complement of a set in \Sigma_n^0 belongs to \Pi_n^0, and conversely, the complement of a set in \Pi_n^0 belongs to \Sigma_n^0. This duality arises directly from the prenex normal form of arithmetical formulas, where existential quantifiers in a \Sigma_n^0 definition become universal under negation, and vice versa. The classes \Delta_n^0 = \Sigma_n^0 \cap \Pi_n^0 are closed under complementation, since if a set is both \Sigma_n^0 and \Pi_n^0, its complement inherits the same dual classification. For n \geq 1, the \Sigma_n^0 classes are closed under additional existential quantification: if R \subseteq \mathbb{N}^{k+1} is a \Sigma_n^0 relation, then \{ \mathbf{x} \in \mathbb{N}^k \mid \exists y \, R(\mathbf{x}, y) \} \in \Sigma_n^0, as the leading existential quantifier block can be merged. Similarly, for n \geq 1, universal quantification preserves membership in \Pi_n^0. These properties reflect the structure of quantifier blocks in and the closure under quantification of the same type as the leading block. Within the arithmetic sets, many-one reducibility (\leq_m) provides a basic tool for comparing complexity: if A \leq_m B via a total computable function f (i.e., x \in A \iff f(x) \in B), and B \in \Sigma_n^0, then A \in \Sigma_n^0. The same holds for \Pi_n^0 and \Delta_n^0 classes, as the computable translation preserves the quantifier structure of the defining formula for B. This reducibility is stricter than and is particularly useful for showing completeness within levels, such as reducing the totality problem to other arithmetic sets without invoking oracles. The higher levels of the arithmetical hierarchy can be conceptualized through arithmetic transfinite recursion, where comprehension along well-founded arithmetic relations builds iterated structures up to any finite ordinal. This process, formalized in subsystems of second-order arithmetic, ensures the hierarchy's finite levels exhaust the arithmetic sets by recursively applying comprehension and separation principles. Every arithmetical set belongs to \Delta_n^0 for some finite n, as the union of the \Delta_n^0 classes over n < \omega coincides with the class of all sets definable by arithmetical formulas. Specifically, any \Sigma_n^0 or \Pi_n^0 set is contained in \Delta_{n+1}^0, reflecting the recursive enumerability relative to the n-th jump.

Examples

Level 0 and 1

The base level of the arithmetical hierarchy, denoted \Delta_0^0, consists of sets definable by arithmetical formulas with only bounded quantifiers, equivalent to the . These predicates can be decided by , which are total computable functions built from basic operations via composition and primitive recursion. The class \Sigma_1^0 comprises sets definable by formulas of the form \exists x \, \phi(n, x), where \phi is \Delta_0^0; these are precisely the , which can be semi-decided by that enumerate their members but may not halt on non-members. Dually, \Pi_1^0 includes sets definable by \forall x \, \phi(n, x) with \phi in \Delta_0^0, corresponding to the , which are complements of r.e. sets and can be semi-decided by machines that halt on non-members but may loop on members. The intersection \Delta_1^0 = \Sigma_1^0 \cap \Pi_1^0 yields the recursive (computable) sets, which are fully decidable by Turing machines that always halt and correctly classify membership. Primitive recursive sets form a proper subclass of \Delta_1^0, as there exist recursive functions, such as the \mu-operator applied to primitive recursive predicates, that are not primitive recursive. A canonical example in \Sigma_1^0 is the halting set K = \{ e \mid \phi_e(e) \downarrow \}, where \phi_e is the e-th partial recursive function; this set is \Sigma_1^0-complete under many-one reductions, meaning every r.e. set Turing-reduces to it. In contrast, the totality set \mathsf{Tot} = \{ e \mid \forall x \, \phi_e(x) \downarrow \} lies at the higher level \Pi_2^0, though its projection onto single inputs relates to \Pi_1^0 membership questions.

Higher Levels

The arithmetical hierarchy extends beyond the first level to capture sets definable with increasing numbers of alternating quantifiers, demonstrating progressively greater descriptive complexity. At level 2, Σ₂⁰ sets are those definable by formulas of the form ∃x ∀y R(e, x, y), where R is an arithmetical relation with no unbound quantifiers (a Δ₀₀ formula), and Π₂⁰ sets by ∀x ∃y R(e, x, y). These levels include sets that are neither recursive nor recursively enumerable, highlighting the limitations of single-quantifier definitions. A canonical Σ₂⁰ set is FIN, the set of indices e such that the recursively enumerable set W_e is finite; this can be expressed as ∃n ∀m (m > n → m ∉ W_e), where the inner condition m ∉ W_e is Π₁⁰. Dually, the complement INF = {e | W_e is }, given by ∀n ∃m > n (m ∈ W_e), is Π₂⁰. Another fundamental Π₂⁰ set is TOT, the set of indices e for which the partial φ_e is (defined on all natural numbers), formalized as ∀x ∃y (φ_e(x) = y), or equivalently ∀x ∃s T(e, x, s) using Kleene's T-predicate, where T is recursive. These examples illustrate how Σ₂⁰ and Π₂⁰ capture properties involving bounded existence or universality over computable approximations. At level 3, Σ₃⁰ sets involve double alternations starting with existential, such as ∃x ∀y ∃z R(e, x, y, z) for a Δ₀₀ relation R. A standard example is COF, the set of indices e such that W_e is cofinite (its complement is finite), expressed as ∃n ∀m ≥ n ∃s T(e, m, s), where the existential quantifier over s witnesses membership in W_e. This requires an additional alternation compared to level 2, reflecting properties that depend on eventual universal behavior verified computably. Π₃⁰ sets, as complements, include the co-cofinite sets. Higher levels follow analogously, with each increase in n adding an alternation and enabling definitions of sets with more intricate computability constraints. For each n ≥ 1, there exist Σ_n⁰-complete sets, meaning every Σ_n⁰ set many-one reduces to them, and they are not in Σ_{n-1}⁰; the universal Σ_n⁰ set, comprising codes of true Σ_n⁰ formulas, serves as such a complete set. The existence of these complete sets follows from effective reductions via the recursion theorem and s-m-n functions, ensuring the hardest problems at each level are uniformly capturable. Proving the strictness of the hierarchy— that Σ_n⁰ ⊊ Σ_{n+1}⁰ —relies on priority arguments, including Post's finite injury method, which constructs a set diagonalizing against all definitions at lower levels by prioritizing requirements and injuring only finitely many. The arithmetical hierarchy connects intimately to the Turing jump operation: the n-th jump of the , denoted ∅^{(n)}, is Σ_n⁰-complete under Turing reducibility, meaning ∅^{(n)} ≡_T a complete Σ_n⁰ set for n ≥ 1. More generally, a set A is Σ_n⁰ if and only if A is many-one reducible to ∅^{(n)}; this places the iterated jumps within the , showing that higher arithmetic levels correspond to increased relative power via oracle jumps.

Relativization

Relativized Hierarchies

The relativized arithmetical hierarchy extends the standard arithmetical hierarchy by incorporating an set A \subseteq \mathbb{N}, which serves as an additional primitive predicate in the logical definitions of sets. Formally, a R \subseteq \mathbb{N}^k belongs to \Sigma_n^{0,A} if there exists a \phi(v_1, \dots, v_k) in the of arithmetic augmented with the atomic predicate "x \in A", consisting of n alternating unbounded quantifiers beginning with an existential quantifier, followed by a quantifier-free , such that R is exactly the set of tuples satisfying \phi. The classes \Pi_n^{0,A} and \Delta_n^{0,A} are defined dually, with \Pi_n^{0,A} starting with a quantifier and \Delta_n^{0,A} = \Sigma_n^{0,A} \cap \Pi_n^{0,A}. This relativization allows the hierarchy to capture the computational complexity of sets relative to the information provided by A, mirroring the structure of Turing machines where membership queries to A can be answered instantaneously. Many properties of the unrelativized are preserved in the relativized version. For instance, the classes \Sigma_n^{0,A} are closed under finite unions and relative to A, while \Pi_n^{0,A} are closed under finite intersections and relative to A; both are closed under complementation to each other (\Sigma_n^{0,A} = \overline{\Pi_n^{0,A}}). The inclusions \Delta_n^{0,A} \subsetneq \Sigma_n^{0,A}, \Delta_n^{0,A} \subsetneq \Pi_n^{0,A}, and \Sigma_n^{0,A} \cup \Pi_n^{0,A} \subsetneq \Delta_{n+1}^{0,A} hold strictly for every n, as established by the relativized version of Post's theorem, which shows that there exist sets complete for each level via many-one reductions relative to A. Furthermore, the relativization principle ensures that key theorems—such as the normal form theorem, the recursion theorem, and the strictness of the hierarchy—hold relative to any oracle A, meaning proofs relativize straightforwardly by incorporating oracle access without altering the logical structure. A concrete example illustrates the utility of relativization: if A is recursively enumerable, then \Sigma_1^{0,A} coincides with the class of sets that are recursively enumerable relative to A, i.e., sets enumerable by a Turing machine with oracle access to A. This follows directly from the definition, as \Sigma_1^{0,A} sets are those for which membership can be witnessed by an existentially quantified search over a recursive relation relativized to A. In terms of Turing degrees, the arithmetical sets relative to the empty oracle ∅ (i.e., the union ⋃_n Δ_n^{0,∅}) have Turing degrees at or below some finite iterate of the jump of the empty set (0^{(n)} for finite n), illustrating the finite levels of unsolvability in the arithmetic hierarchy.

Arithmetical Reducibility and Degrees

In , arithmetical reducibility compares sets based on membership in the relativized arithmetical hierarchy. A set B \subseteq \mathbb{N} is arithmetically reducible to a set A \subseteq \mathbb{N}, written B \leq_a A, if B belongs to some level \Sigma_n^{0,A} of the arithmetical hierarchy relative to A, for finite n \geq 0. This means B can be defined by a first-order formula over the structure (\mathbb{N}, +, \times, A) with at most n alternating unbounded quantifiers, starting with an existential one. The relation \leq_a is reflexive and transitive, but not necessarily antisymmetric; the associated equivalence relation \equiv_a, defined by B \equiv_a A if B \leq_a A and A \leq_a B, partitions the power set of natural numbers into equivalence classes known as arithmetical degrees. The poset of arithmetical degrees, ordered by \leq_a, forms an upper semi-lattice under the join operation induced by arithmetic comprehension, situating it structurally between the more refined Turing degrees (under Turing reducibility \leq_T) and the coarser hyperarithmetical degrees (under hyperarithmetical reducibility). Each degree corresponds to a unique arithmetical , the smallest collection of sets containing the basic recursive relations relative to representatives of the degree and closed under arithmetic operations like and complementation. A notable is that these degrees are upward closed under relative jumps within the arithmetic context: for any degree d, the Turing jump of a set in d remains arithmetically reducible to sets in d, ensuring the structure captures escalating descriptive complexity without escaping the arithmetic framework. The degree of the halting set K = \{ e \in \mathbb{N} \mid \varphi_e(e) \downarrow \}, which is \Sigma_1^0-complete, generates the arithmetical degrees by serving as the foundational non-recursive element; all arithmetical sets (those \leq_a \emptyset) reduce to K under \leq_a, and the arithmetical of K coincides with the arithmetical sets (the over n of Δ_n^0), providing the base for higher degrees through iterated arithmetic comprehension. This implies that K bounds the initial segment of the structure, with every arithmetical degree embeddable below extensions generated from finite iterations involving K. The notions of arithmetical reducibility and degrees emerged in the 1950s through the work of Stephen Kleene and Emil Post, who extended earlier ideas on recursive enumerability to the full arithmetical hierarchy and its degree-theoretic implications.

Generalizations

Subsets of Cantor and Baire Spaces

The $2^\omega, consisting of all infinite sequences of 0s and 1s equipped with the , and the \omega^\omega, consisting of all infinite sequences of natural numbers similarly equipped, are fundamental Polish spaces in descriptive . These spaces serve as models for the real numbers up to and provide a topological setting for studying the complexity of definable sets beyond the natural numbers. In this context, the arithmetical hierarchy classifies subsets according to the number of alternations of bounded quantifiers in their definitions, extended to these spaces via effective codes for basic open sets. Subsets of these spaces are classified in the arithmetical hierarchy using lightface and boldface notations. The class \Sigma_1^0 consists of open sets, which are countable unions of basic open sets defined by finite initial segments of sequences; \Sigma_2^0 comprises F_\sigma sets, which are countable unions of closed sets; and higher levels \Sigma_n^0 are defined recursively as countable unions of sets from \Pi_{n-1}^0, with \Pi_n^0 being the complements of \Sigma_n^0. This finite-level hierarchy coincides with the initial segments of the up to countable ordinals less than \omega, where Borel sets are generated by transfinite iterations of complementation and countable unions starting from open sets. The lightface version restricts to recursive enumerations and parameter-free definitions from \omega, while the boldface version allows arbitrary real parameters from the space itself, enabling a broader class that captures all sets obtainable by finite Borel operations with parameters. A key property is that every arithmetical set in the or —meaning a set in some \Delta_n^0, the intersection of \Sigma_n^0 and \Pi_n^0—is a , as the effective constructions ensure membership in the Borel \sigma-algebra generated by open sets. Moreover, the lightface arithmetical sets are contained within the boldface \Delta_1^1 class of projective sets, which are continuous images of , though themselves. The boldface arithmetical hierarchy, through its allowance of real parameters, generates all of less than \omega, distinguishing it from the full transfinite . For instance, consider continuous functions between subsets of the : a function f: 2^\omega \to 2^\omega that is computable—meaning its values are determined by a recursive on finite approximations—is arithmetically definable, with its graph belonging to \Sigma_1^0 as an in the product space. Such functions illustrate how arithmetical definability aligns with low-level Borel complexity in these topological settings.

Extensions and Variations

Primitive recursive arithmetic (PRA) formalizes a subsystem of Peano arithmetic where induction is restricted to \Delta_0^0 formulas, identifying the base level of the arithmetical hierarchy with primitive recursive relations, in contrast to the full bounded quantification allowed in stronger systems. In PRA, all provably total functions are primitive recursive, and the theory's quantifier-free language aligns with \Delta_0^0 definability, limiting its expressive power to the primitive recursive fragment below the full arithmetical hierarchy. Higher-type arithmetical hierarchies extend the classical structure to higher-order objects, such as total functions from \mathbb{N} to \mathbb{N}, by applying analogous alternating quantifiers over type-2 variables alongside number quantifiers. These generalizations, rooted in Kleene's work on in higher types, classify definable sets and functionals beyond arithmetic while preserving the hierarchy's stratified complexity. In , the arithmetical comprehension axiom schema (\ACA_0) asserts the existence of sets defined by arbitrary arithmetical formulas, thereby validating comprehension across the entire arithmetical hierarchy and equating its strength to second-order systems capable of representing all levels \Sigma_n^0 and \Pi_n^0. Variations in weak arithmetics, such as (Q), restrict provability to \Sigma_1^0 sentences, as Q proves all true \Sigma_1^0 sentences but is unable to establish truths requiring higher quantifier alternations in the hierarchy. Modern connections to proof mining employ subsystems like PRA to extract quantitative bounds from non-constructive proofs, linking definability levels in the arithmetical hierarchy to effective uniformity. Bounded arithmetic theories, such as the S_2^i systems introduced by Buss, provide updated frameworks for analyzing proof and feasible , extending beyond early results to characterize polynomial-time hierarchies with bounded quantifier restrictions tied to arithmetical levels.

Connections to Computability

Relation to Turing Machines

The arithmetical hierarchy classifies subsets of the natural numbers based on their definability in arithmetic, but it also admits an equivalent formulation in terms of s, which provide a computational perspective on the levels of the hierarchy. A standard , without access to an , computes exactly the sets in \Delta_0^0, the recursive (or computable) sets, whose membership can be decided by an that always halts. These sets correspond to the \Delta_0^0 formulas in the logical definition, where no alternations of quantifiers occur beyond decidable predicates. The class \Sigma_1^0 consists of the recursively enumerable (r.e.) sets, which are precisely the domains of partial computable functions; that is, for a set A \in \Sigma_1^0, there exists a that, on input x, halts if and only if x \in A, but may loop otherwise. Equivalently, the \Sigma_1^0 sets are the ranges of total computable functions from \mathbb{N} to \mathbb{N}. The complementary class \Pi_1^0 comprises the co-recursively enumerable sets, whose complements are in \Sigma_1^0. For higher levels, the is defined recursively using the operation on the \emptyset. The n-th \emptyset^{(n)} is obtained by iterating the n times starting from \emptyset, where the of a set X is the set of indices e such that the e-th with X halts on input e. The class \Sigma_{n+1}^0 contains the sets that are recursively enumerable relative to \emptyset^{(n)}, meaning they are the domains of partial computable functions with \emptyset^{(n)}. Correspondingly, \Delta_{n+1}^0 consists of the sets computable by with \emptyset^{(n)}, which are the sets decidable using queries to \emptyset^{(n)}. The \Pi_{n+1}^0 sets are the complements of the \Sigma_{n+1}^0 sets. This -based definition aligns precisely with the quantifier-prefix characterization of the . Post's theorem establishes the strictness of the arithmetical hierarchy by showing that each level properly extends the previous ones, using constructions involving Turing machines to exhibit sets in \Sigma_{n+1}^0 \setminus \Delta_{n+1}^0 for every n \geq 0. Specifically, Post demonstrated that there exist recursively enumerable sets that are not recursive, and more generally, sets at higher levels that cannot be placed lower, via arguments adapted to oracle computations. This result underscores the infinite ascent of captured by the hierarchy.

Key Theorems and Results

Kleene's normal form theorem provides a foundational characterization of arithmetical sets using Gödel numbering and universal predicates. It states that every partial recursive function can be represented in the form \phi_e(x) = U(T(e, x, y)), where T is the Kleene T-predicate, a primitive recursive relation encoding computations via Gödel numbers, and U is a primitive recursive function extracting the output from the computation transcript. This theorem enables the representation of arithmetical predicates as those definable by first-order formulas in arithmetic with unbounded quantifiers over recursive predicates, establishing that the arithmetical hierarchy classifies sets based on the number of alternations of unbounded existential and universal quantifiers in such representations. Post's theorem establishes the completeness of sets at each level of the arithmetical hierarchy, asserting that for every n \geq 1, there exists a \Sigma_n^0-complete set, such as the nth Turing jump of the empty set [\emptyset^{(n)}](/page/Empty_set), which is \Sigma_n^0 but not \Pi_n^0. This result connects the syntactic hierarchy of quantifier alternations to the semantic degrees of unsolvability, showing that every \Sigma_n^0 set is many-one reducible to [\emptyset^{(n)}](/page/Empty_set), and thus the levels are strictly increasing. The theorem also implies that a set is \Delta_{n+1}^0 if and only if it is computable from [\emptyset^{(n)}](/page/Empty_set). Within the arithmetic degrees, jump inversion holds up to Turing equivalence, meaning that for any arithmetic set A \geq_T \emptyset^{(n)}, there exists an arithmetic set B such that A \equiv_T B', where B' is the Turing jump of B. This invertibility characterizes the structure of the arithmetic Turing degrees, showing that the jump operator is surjective onto the degrees above \emptyset^{(n)} within the arithmetic sets, and it follows from the density of the arithmetic hierarchy and properties of oracle computations. Friedberg's jump inversion theorem provides the general framework, specialized here to arithmetic sets via Shoenfield's absoluteness results ensuring that arithmetic jumps remain within the arithmetic hierarchy. The arithmetical hierarchy theorem demonstrates that the hierarchy does not collapse at any finite level, i.e., \Sigma_n^0 \subsetneq \Sigma_{n+1}^0 and \Pi_n^0 \subsetneq \Pi_{n+1}^0 for all n \geq 0. This is proven by constructing, for each n, a \Sigma_{n+1}^0 set that is not \Sigma_n^0, using diagonalization over the universal \Sigma_n^0 predicate, which enumerates all \Sigma_n^0 sets effectively. The non-collapse follows directly from Post's completeness results, as \emptyset^{(n)} witnesses the proper inclusion. In modern computability theory, the arithmetical hierarchy connects to algorithmic randomness, where sets at low levels (e.g., \Delta_2^0) capture Martin-Löf random reals relative to low oracles, but higher levels are needed for full randomness notions like Kolmogorov complexity bounds. For instance, the halting problem \emptyset' (a \Sigma_1^0 set) computes no Martin-Löf random, while \emptyset'' ( \Sigma_2^0) suffices for some randomness tests, highlighting how hierarchy levels measure the computational strength required for randomness extraction.

Relations to Other Hierarchies

Analytical Hierarchy

The analytical hierarchy extends the arithmetical hierarchy by incorporating second-order quantifiers over subsets of the natural numbers, allowing for the classification of more complex sets in descriptive set theory. While the arithmetical hierarchy relies on quantifiers over natural numbers to define levels \Sigma_n^0 and \Pi_n^0, the analytical hierarchy introduces existential and universal quantifiers over sets of natural numbers (or reals), denoted as \Sigma_n^1 and \Pi_n^1. Specifically, a set is in \Sigma_1^1 if it can be expressed as \{x \mid \exists A \subseteq \mathbb{N} \, \phi(x, A)\}, where \phi is an arithmetical formula (i.e., \Pi_0^k for some k), representing existential second-order quantification over subsets A of \mathbb{N}. Higher levels are obtained by alternating projections and complements: \Sigma_{n+1}^1 consists of existential projections of \Pi_n^1 sets, and \Pi_{n+1}^1 their complements. The class \Delta_n^1 is defined as the intersection \Sigma_n^1 \cap \Pi_n^1. All arithmetical sets belong to \Delta_1^1, as they can be defined using only quantifiers, which are a special case of second-order formulas with trivial quantification over subsets. Moreover, the union of all arithmetical levels coincides with the effective Borel sets, which form a proper subclass of the full \Delta_1^1 class. Thus, the arithmetical hierarchy is strictly contained in \Delta_1^1: arithmetical \subsetneq \Delta_1^1. The projective sets, which form the union \bigcup_n \Sigma_n^1 (or equivalently \bigcup_n \Pi_n^1), extend beyond \Delta_1^1 and include sets of higher descriptive complexity not reachable by means. A fundamental property distinguishing the analytical hierarchy is its extension of closure operations: \Sigma_1^1 sets (analytic sets) are closed under countable unions and continuous images of Borel sets, but unlike Borel sets, they include non-Borel examples, such as certain pathological sets constructed via the diagonal argument. The analytical hierarchy thus captures the projective hierarchy, where levels beyond \Delta_1^1 introduce sets that lack some regularity properties of Borel sets, like failing to be Lebesgue measurable in certain cases. Suslin's theorem establishes the boundary between these hierarchies by proving that \Delta_1^1 coincides exactly with the Borel sets: a set is Borel if and only if it is both analytic (\Sigma_1^1) and co-analytic (\Pi_1^1). This equivalence highlights that while the arithmetical sets are the "computably" definable Borel sets, \Delta_1^1 encompasses all Borel sets via second-order definitions.

Hyperarithmetical Hierarchy

The hyperarithmetical hierarchy extends the arithmetical hierarchy by iterating the Turing jump operator transfinitely along computable ordinals, up to the Church-Kleene ordinal \omega_1^{CK}, the smallest non-computable ordinal. A set is hyperarithmetical if it is Turing reducible to H_\alpha for some ordinal notation \alpha \in O, where O is Kleene's O, a \Pi_1^1-complete set providing notations for all computable ordinals below \omega_1^{CK}. The sequence (H_\alpha)_{\alpha < \omega_1^{CK}} is defined recursively: H_0 = \emptyset, successor stages apply the Turing jump H_{\alpha+1} = H_\alpha', and limit stages take the union over previous approximations. The arithmetical hierarchy forms the initial segment of the hyperarithmetical hierarchy below \omega, as the finite iterations of the Turing jump yield precisely the arithmetical sets \Sigma_n^0 and \Pi_n^0 for n < \omega. Thus, every arithmetical set is hyperarithmetical, but the converse fails, since \omega_1^{CK} is uncountable and allows for strictly finer distinctions in degrees. This extension captures all sets computable relative to the hyperjump, which generalizes the Turing jump by relativizing Kleene's O to an X, yielding O^X = \{ n : \phi_n^X computes a well-founded on \omega^{<\omega} \}, a complete \Pi_1^{1,X} set. The hyperjump enables transfinite iteration beyond finite jumps, with X^{( \alpha )} \leq_T O^X for \alpha < \omega_1^{CK}, connecting the hierarchies through effective descriptive . A key property is that the hyperarithmetical sets coincide exactly with the boldface \Delta_1^1 sets intersected with the constructible universe L_{\omega_1^{CK}}, i.e., \mathrm{HYP} = \Delta_1^1 \cap L_{\omega_1^{CK}}. This equivalence highlights the effective nature of hyperarithmetical sets within the projective hierarchy, as they are precisely those projective sets constructible before \omega_1^{CK}. The class HYP is closed under Turing reducibility, complements, and countable unions, mirroring arithmetical closure properties but at a transfinite scale.