در نظریهٔ محاسبه پذیری قضیهٔ پست، نام گرفته از امیل پست، رابطهٔ بینِ سلسله مراتب حسابی و درجهٔ تورینگ را نشان می دهد.
برای هر n ≥ 0 {\displaystyle n\geq 0\!} ، B ∈ Σ n + 1 {\displaystyle B\in \Sigma _{n+1}\!} اگر و فقط اگر B {\displaystyle B\!} یک مجموعهٔ بازگشتی محاسبه پذیر با یک غیب گو، از مجموعهٔ Π n {\displaystyle \Pi _{n}\!} -ای، یا به طورِ مترادف، از Σ n {\displaystyle \Sigma _{n}\!} -ای باشد.
می گوییم زیرمجموعهٔ X {\displaystyle X\!} از ω {\displaystyle \omega \!} یک Σ n {\displaystyle \Sigma _{n}\!} است اگر فرمولِ Σ n {\displaystyle \Sigma _{n}\!} -ای با متغیر آزادِ n {\displaystyle n\!} وجود داشته باشد که مقدارِ درست داشته باشد، اگر و فقط اگر n {\displaystyle n\!} در X {\displaystyle X\!} باشد.
به طور دقیق قضیهٔ پست می گوید:
برای هر n ≥ 0 {\displaystyle n\geq 0\!} ، B ∈ Σ n + 1 {\displaystyle B\in \Sigma _{n+1}\!} اگر و فقط اگر B {\displaystyle B\!} یک مجموعهٔ بازگشتی محاسبه پذیر با یک غیب گو، از مجموعهٔ Π n {\displaystyle \Pi _{n}\!} -ای، یا به طورِ مترادف، از Σ n {\displaystyle \Sigma _{n}\!} -ای باشد.
می گوییم زیرمجموعهٔ X {\displaystyle X\!} از ω {\displaystyle \omega \!} یک Σ n {\displaystyle \Sigma _{n}\!} است اگر فرمولِ Σ n {\displaystyle \Sigma _{n}\!} -ای با متغیر آزادِ n {\displaystyle n\!} وجود داشته باشد که مقدارِ درست داشته باشد، اگر و فقط اگر n {\displaystyle n\!} در X {\displaystyle X\!} باشد.
به طور دقیق قضیهٔ پست می گوید:
wiki: قضیه پست