Post's Theorem

Post's theorem is the bridge between the arithmetical hierarchy and the Turing jump hierarchy, proved by Emil Post in the 1940s. It states that a set is \u03a3\u207f\u2070\u207a\u2081 if and only if it is recursively enumerable relative to the n-th Turing jump of the empty set (0\u207f). This equivalence is not a coincidence but a structural fact: each quantifier alternation in a definition corresponds to one iteration of the jump operator, so that logical complexity and oracle strength measure the same thing in different notation.

Post's theorem is one of the central organizing results of computability theory. It shows that the arithmetical hierarchy is not merely a classification of definability but a measure of computational power — that the question "how complex is this set's definition?" and the question "how powerful an oracle is needed to compute it?" have identical answers.

Post's theorem is the Rosetta Stone of computability: it proves that the languages of logic and computation, despite their different origins and vocabularies, describe the same landscape. The fact that quantifier depth and oracle strength coincide is not a translation but a discovery — the two were never separate.