Arithmetical hierarchy

Summary

The arithmetical hierarchy classifies sets of natural numbers by the number of alternating blocks of unbounded quantifiers needed to define them in first-order arithmetic. Its levels are the classes $\Sigma^0_n$, $\Pi^0_n$ and $\Delta^0_n$ for $n \in \N$. The first levels are familiar: $\Delta^0_1$ sets are the computable sets and $\Sigma^0_1$ sets are the computably enumerable sets. Post's theorem links each level to computability relative to iterated Turing jumps.