نمایش مبدأ برای قضیه پست

در [[نظریه محاسبه‌پذیری|نظریهٔ محاسبه‌پذیری]] '''قضیهٔ پست'''، نام‌گرفته از [[امیل پست]]، رابطهٔ بینِ [[سلسله‌مراتب حسابی]] و [[درجه تورینگ|درجهٔ تورینگ]] را نشان می‌دهد.

می‌گوییم زیرمجموعهٔ <math>X \!</math> از <math>\omega \!</math> یک <math>\Sigma_n \!</math> است اگر فرمولِ <math>\Sigma_n \!</math>-ای با متغیر آزادِ <math>n \!</math> وجود داشته باشد که مقدارِ درست داشته باشد، اگر و فقط اگر <math>n \!</math> در <math>X \!</math> باشد.

به‌طور دقیق قضیهٔ پست می‌گوید:
* برای هر <math>n \geq 0 \!</math>، <math>B \in \Sigma_{n+1} \!</math> اگر و فقط اگر <math>B \!</math> یک [[مجموعه بازگشتی محاسبه‌پذیر|مجموعهٔ بازگشتی محاسبه‌پذیر]] با یک غیب‌گو، از مجموعهٔ <math>\Pi_n \!</math>-ای، یا به طورِ مترادف، از <math>\Sigma_n \!</math>-ای باشد.
* <math>\emptyset^{(n)} \!</math>، یعنی برای هر <math>n > 0 \!</math> ،''n''-اُمین [[جهش تورینگ|جهش تورینگی]] مجموعه خالی <math>\Sigma_n \!</math> کامل است.

== منابع ==
* Rogers, H. ''The Theory of Recursive Functions and Effective Computability'', MIT Press. {{isbn|0-262-68052-1}}; {{isbn|0-07-053522-1}}
* Soare, R. ''Recursively enumerable sets and degrees.'' Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. {{isbn|3-540-15299-7}}{{ریاضی-خرد}}

[[رده:سلسله‌مراتب منطق ریاضیاتی]]
[[رده:قضایای بنیان‌های ریاضیات]]
[[رده:قضیه‌های ریاضی]]
[[رده:نظریه بازگشت]]