Math 2.0

Mathematical logic and foundations Computability theory Theorem

Post's theorem

Builds on Arithmetical hierarchyComputably enumerable setTuring jumpTuring reductionMany-one reduction

Statement

Let ∅(0)=∅\emptyset^{(0)} = \emptyset, and let ∅(n+1)\emptyset^{(n+1)} be the Turing jump of ∅(n)\emptyset^{(n)}. Let A⊆ℕA \subseteq \N and n∈ℕn \in \N.

  1. AA is Σn+10\Sigma^0_{n+1} in the arithmetical hierarchy if and only if AA is computably enumerable relative to the oracle ∅(n)\emptyset^{(n)}.
  2. If n≥1n \ge 1, the set ∅(n)\emptyset^{(n)} is Σn0\Sigma^0_n-complete: it is Σn0\Sigma^0_n, and every Σn0\Sigma^0_n set is many-one reducible to it.
  3. AA is Δn+10\Delta^0_{n+1} if and only if AA is Turing reducible to ∅(n)\emptyset^{(n)}.

Remarks

The proof is by induction on nn. For n=0n = 0, part 1 says that Σ10\Sigma^0_1 sets are the computably enumerable sets, which follows from Kleene's normal form. For the inductive step, an existential quantifier over a set computable from ∅(n)\emptyset^{(n)} is a search with that oracle. A Πn0\Pi^0_n condition can be answered by one question to ∅(n)\emptyset^{(n)}, by the completeness in part 2.

Example: the set of programs that compute total functions is Π20\Pi^0_2, so it is computable from ∅′′\emptyset''.

Going deeper

For a student

The theorem is the bridge between definability in arithmetic and relative computability. It shows that the arithmetical hierarchy is proper, because ∅(n+1)\emptyset^{(n+1)} is not computable from ∅(n)\emptyset^{(n)}. In computability arguments, one often bounds the quantifier complexity of a set to know which oracle can decide it. Iterating the jump through computable ordinals beyond ω\omega leads to the hyperarithmetical sets.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph
Arithmetical hierarchy, concept, no evidence levelArithmetical hierarchyconceptComputably enumerable set, concept, no evidence levelComputably enumerable…conceptMany-one reduction, concept, no evidence levelMany-one reductionconceptTuring jump, concept, no evidence levelTuring jumpconceptTuring reduction, concept, no evidence levelTuring reductionconceptPost's theorem, statement, no evidence levelPost's theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Arithmetical hierarchy concept
  2. Computably enumerable set concept
  3. Many-one reduction concept
  4. Turing jump concept
  5. Turing reduction concept
  6. Post's theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Post's_theorem
About this page
TagNYJX5QXX1T
URIm2://NYJX5QXX1T
Kindstatement, theorem
WritingW0 stub
MSC03D55, 03D30
StatusThis copy of the site has no build data. Run m2 status NYJX5QXX1T.
AboutArithmetical hierarchy, Turing jump
UsesArithmetical hierarchy, Computably enumerable set, Turing jump, Turing reduction, Many-one reduction
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.