17-Ma’ruza. Deduksiya teoremasi. Mos keltirib chiqarish haqida lemma. To’liqlik haqida Gyodel teoremasi

4.2.5. V qoida. (Deduksiya teoremasi.) .
Isboti. Avval formulalar majmuasining har qanday keltirib chiqarishi uchun ning to‘g‘riligini matematik induksiya metodidan foydalanib isbot qilamiz.
Baza. hol uchun tasdiq to‘g‘ri. Haqiqatan ham, agar formula ning keltirib chiqarishi bo‘lsa, u vaqtda quyidagi uch hol bo‘lishi mumkin:
a) ,
b) isbotlanuvchi formuladir,
d) formula ning o‘zidir.
a) va b) hollar uchun dan quyidagi keltirib chiqarishni yozish mumkin: , , . Demak, .
d) hol uchun bo‘lishini isbotlash kerak.
Ravshanki, isbotlanuvchi formuladir. Shuning uchun uni har qanday majmuadan keltirib chiqarish mumkin.
Induksion o‘tish. Endi istalgan ( ) chuqurlikdagi har qanday keltirib chiqarish uchun tasdiq to‘g‘ri bo‘lsin deb hisoblab, uning chuqurlikdagi keltirib chiqarish uchun to‘g‘riligini isbot qilamiz.
lar majmuaning keltirib chiqarishi bo‘lsin, bu yerda . U vaqtda formulaga nisbatan quyidagi to‘rt hol yuz berishi mumkin:
a) ,
b) isbotlanuvchi formuladir,
d) formula ning o‘zidir,
e) formula xulosa qoidasiga asosan keltirib chiqarishdagi ikkita undan
oldin ketma-ket keladigan formulalardan hosil qilinadi.
a), b), d) hollar uchun isbot to‘liq ravishda holdagi isbotga mos keladi.
Shuning uchun e) holni ko‘ramiz. Bu holda formula va formulalardan hosil qilinib , formula ko‘rinishni oladi va quyidagi tasdiqlar o‘rinli bo‘ladi:
, (5)
. (6)
I₂ aksiomada

o‘rniga qo‘yishni bajarib, quyidagi isbotlanuvchi formulaga ega bo‘lamiz:
. (7)
(6), (5) va (7) ifodalar dan keltirib chiqariladigan formulalardir. Ularga murakkab xulosa qoidasini qo‘llab, ni hosil qilamiz.
Endi umumiy, ya’ni bo‘lgan holni ko‘raylik. U holda ning , keltirib chiqarishi mavjud bo‘ladi. Demak, yuqoridagi mulohazalarga asosan tasdiq to‘g‘ridir. ■
Deduksiya teoremasidan quyidagi muhim ahamiyatga ega bo‘lgan tasdiq kelib chiqadi.