Post's theorem

For $n=0$, the first equivalence is the ${\mathrm{\Sigma }}_1^0$/c.e. theorem; deciding a set is equivalent to recognizing it and its complement.

Assume the characterizations at $n$. In a ${\mathrm{\Sigma }}_{n+2}^0$ presentation, the predicate following the first existential block is ${\mathrm{\Pi }}_{n+1}^0$. It is co-c.e. in $0^{(n)}$, and is therefore decidable by the halting oracle $0^{(n+1)}$; the first block is consequently a c.e. search in $0^{(n+1)}$. Conversely, record a halting $0^{(n+1)}$-oracle computation together with its finite query transcript. Replace each yes-query by its ${\mathrm{\Sigma }}_{n+1}^0$ halting witness and each no-query by the dual ${\mathrm{\Pi }}_{n+1}^0$ condition. Since the transcript is finite, its conditions merge with the outer existential witness into a ${\mathrm{\Sigma }}_{n+2}^0$ formula.

A $0^{(n)}$-decider recognizes both a set and its complement, and two relative recognizers can be dovetailed into a decider. Applying the first equivalence to both sides therefore gives the $\mathrm{\Delta }$ equivalence; negation gives the $\mathrm{\Pi }$ clause. This closes the induction.