Théorème de Post

Ce théorème fait le lien entre hiérarchie arithmétique et degré de Turing.

Théorème (Post): pour tout n>0

• B appartient à Σ_{n + 1} si et seulement si B est récursivement énumérable avec oracle Π_n (ou Σ_n).
• ${\varnothing }^{(n)}$, c'est-à-dire le n-ième degré de Turing après $\varnothing$, est Σ_n-complet.

En particulier,

• B est dans Σ_{n + 1} si et seulement si B est récursivement énumérable avec l'oracle ${\varnothing }^{(n)}$.
• B est dans Δ_{n + 1} si et seulement si B est Turing-réductible à ${\varnothing }^{(n)}$.