Tayanch iboralar

3- teorema. Rekursiv bo‘lmagan effektiv rekursiv sanaluvchi natural sonlar to‘plami mavjud.

Isboti. 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 CU to‘ldiruvchisi effektiv rekursiv sanaluvchi emasligini isbotlash yetarli.

M₀, M₁,M₂,… – hamma rekursiv sanaluvchi natural sonlar to‘plamlaridagi effektiv sanab chiqilgan to‘plamlar bo‘lsin. Demak, har qanday n uchun M_n to‘plamni tiklash mumkin.

Endi U to‘plamning hamma elementlarini sanab chiqadigan A algoritmni kiritaylik. Bu algoritm (m, n) raqamli qadamda m M_n ni hisoblab chiqadi. Agar bu son n son bilan ustma-ust tushsa, bu holda A algoritm uni U to‘plamga kiritadi, ya’ni n nM_n.

Bundan ko‘rinib turibdiki, har qanday rekursiv sanaluvchi to‘plamdan CU to‘plam hech bo‘lmaganda bitta element bilan farq qiladi, chunki CU shunday n elementlardan iboratki, n Mn  . Shuning uchun ham CU rekursiv sanaluvchi to‘plam emas. Demak, Post teoremasiga asosan U rekursiv to‘plam bo‘lmaydi.

Izoh. Isbot qilingan bu teorema aslida Gyodelning formal arifmetika to‘liqsizligi haqidagi teoremasini oshkormas tarzda qamrab olgan.