What does a higher level in the hierarchy mean?

More alternating quantifiers mean a more complex definition and, by Post's theorem, a problem that requires more iterations of the halting problem to decide. Sets higher in the hierarchy are strictly less accessible to computation than those below them.

Where do computably enumerable sets sit?

They occupy the sigma-one level, definable by a single existential quantifier over a computable relation. Their complements occupy the pi-one level, and the sets that are both, the delta-one sets, are exactly the computable sets.

The Arithmetical Hierarchy

The arithmetical hierarchy classifies sets of natural numbers by the number of alternating quantifiers needed to define them, linking logical complexity to degrees of uncomputability.

Find Topic with PaperMindSoonFind papers & topics

Tools & resources

Download slides

Learn & explore

VideoSoon

Definition

The arithmetical hierarchy stratifies the sets definable in first-order arithmetic by counting alternations of unbounded quantifiers in front of a computable matrix, with sigma-n sets defined by a block starting with an existential quantifier and pi-n sets by one starting with a universal quantifier.

Scope

This topic covers the classification of definable sets into the sigma, pi, and delta levels by quantifier alternation over computable relations, Post's theorem relating the hierarchy to the iterated halting problem and Turing jumps, the strictness of the hierarchy, and its extension to the analytical hierarchy.

Core questions

How does quantifier alternation measure the complexity of a set?
How do the sigma, pi, and delta classes at each level relate to one another?
How does the hierarchy correspond to iterating the halting problem?
Why is the hierarchy strict, with each level properly larger than the last?

Key theories

Quantifier classification: A set is sigma-n if definable by n alternating quantifier blocks beginning existentially over a computable relation, and pi-n if beginning universally; the computably enumerable sets are exactly the sigma-one sets.
Post's theorem: A set is sigma-(n+1) exactly when it is computably enumerable relative to the n-th Turing jump, tying the levels of the hierarchy to iterated relativized halting problems.
Strictness of the hierarchy: Each Turing jump is strictly more complex than the previous one, so every level of the arithmetical hierarchy properly contains the levels below it and the hierarchy does not collapse.

Clinical relevance

The arithmetical hierarchy is the standard yardstick for the complexity of definable problems in logic and computer science: it locates problems such as totality, finiteness, and cofiniteness of computable sets at precise levels, and it frames the boundary between what is computably enumerable and what requires stronger noncomputable resources.

History

Kleene and Mostowski independently introduced the arithmetical hierarchy around 1943, classifying sets by quantifier complexity over computable predicates. Post's theorem connected the hierarchy to the Turing jump, unifying the definability-based and computability-based perspectives, and the framework was later extended upward into the analytical hierarchy.

Key figures

Stephen Cole Kleene
Andrzej Mostowski
Emil Post

Seminal works

rogers1987
soare1987
cutland1980

Frequently asked questions

What does a higher level in the hierarchy mean?: More alternating quantifiers mean a more complex definition and, by Post's theorem, a problem that requires more iterations of the halting problem to decide. Sets higher in the hierarchy are strictly less accessible to computation than those below them.
Where do computably enumerable sets sit?: They occupy the sigma-one level, definable by a single existential quantifier over a computable relation. Their complements occupy the pi-one level, and the sets that are both, the delta-one sets, are exactly the computable sets.