---
tag: M6JGF4TPM6
kind: concept
name: Analytical hierarchy
msc: [03D55, 03F35]
sources:
  - url: https://en.wikipedia.org/wiki/Analytical_hierarchy
same_as:
  wikidata: Q2878515
  wikipedia: Analytical hierarchy
---

## Summary

The analytical hierarchy classifies sets of natural numbers by the quantifiers over sets of numbers needed to define them in [[second-order arithmetic|DC60FYCSPM]].
Its levels are the classes $\Sigma^1_n$, $\Pi^1_n$ and $\Delta^1_n$.
It extends the [[arithmetical hierarchy|7CVJCQKY41]], whose sets all sit in $\Delta^1_1$.
It is the effective, or lightface, counterpart of the [[projective hierarchy|8DZTNVTGY2]] of descriptive set theory.

## Explanations

### L1 human

Arithmetic can talk about numbers; second-order arithmetic can also talk about infinite sets of numbers.
A definition that says "there is a set $X$ such that ..." or "for every set $X$ ..." can describe far more complicated sets.
For example, "this computable ordering of numbers has no infinite descending sequence" says something about all infinite sequences.
The analytical hierarchy counts how many alternations of such set quantifiers a definition needs.