Teng kuchli formulalar va asosiy teng kuchliliklar Ta’rif

(Post teoremasi). M to ‘plamning о‘zi va to‘Idiruvchisi C M effektiv rekursiv sanaluvchi bo'lganda va faqat shundagina M to ‘plam rekursivdir.
I s b o t i . a) M to‘plam va uning C M to'ldiruvchisi effektiv rekursiv sanaluvchi bo'lsin. U holda, 2- ta’rifga asosan, bu to‘plamlaming elementlarini sanab chiqa oladigan A va В algoritmlar mavjud bo'ladi. U holda M va C M to'plamlaming elementlarini sanab chiqish paytidalarning ro'yxatida x element uchraydi. Demak, shunday С algoritmyuzaga keladiki, u orqali Jt element M to'plamga qarashlimi yoki qarashli emasmi degan muammoni hal qilish mumkin. Shunday qilib, M rekursiv to‘plam bo'ladi.
b) M rekursiv to‘plam bo'lsin. U holda, 1- ta’rifga asosan, x bu to'plamning elementimi yoki elementi emasmi degan muammoni hal qiluvchi algoritm mavjud bo‘ladi. Bu algoritmdan foydalanib, M va C M to‘plamlarga kiruvchi elementlarning ro‘yxatini tuzamiz. Shunday qilib, M va C M to‘plamlar elementlarini sanab chiquvchi ikkita A va В algoritmni hosil qilamiz. Demak, M va C M to‘plamlar effektiv rekursiv sanaluvchi to‘plamlar bo'ladi.
3- t e o r e m a . Rekursiv bo ‘Imagan effektiv rekursiv sanaluvchi natural sonlar to 'plami mavjud.
I s b o t i . Effektiv rekursiv sanaluvchi ixtiyoriy U natural sonlar to‘plami berilgan bo'lsin. U to'plamning rekursiv emasligini isbotlash uchun, Post teoremasiga (2- teorema) ko'ra, uning C U to'ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli.
- hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo isin. Demak, har qanday (m,n) uchun to‘plamni tiklash mumkin. Endi U to‘plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m , n) raqamli qadamda ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A algoritm uni U to‘plamga kiritadi, ya’ni .
Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan C U to‘plam hech boimaganda bitta element bilan farq qiladi, chunki C U shunday n elementlardan iboratki, . Shuning uchun ham C U rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan U rekursiv to‘plam boim aydi.
I z о h . Isbot qilingan bu teorema aslida Gyodelning formal arifme-tika
toiiqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan.