Математическая логика и теория алгоритмов

высказываний непротиворечивость была доказана сравнительно про­ сто. Для произвольной теории первого порядка установить непро­ тиворечивость в рамках этой же теории не удается. Но в некоторых частных случаях, например, для исчисления предикатов первого по­ рядка, удается доказать непротиворечивость. Непротиворечивость исчисления предикатов первого порядка (теории Ki). Теорема 4,8. Всякое исчисление предикатов первого порядка непротиворечиво. Доказательство. Для произвольной формулы А обозначим через h{A) выражение, получающееся в результате следующего преоб­ разования формулы А: в J спускаются все кванторы и термы (вместе с соответствующими скобками и запятыми). Например, h(vxia^i (ХЬ х2)=>а\ (Л'З) есть^^; => a 'I ; h(]VxiA^2(Xb^ii, Xi)=i>A^s(a2)=i-A^2(Xi) есть ']А^2 =^А^^:^А\, . По существу h(A) всегда является пропозициональной формой, в ко­ торой роль пропозициональных букв играют символы A^'j. Ясно, что имеют место hilAJ^lhiA), h{A=i>B)=h{A):^h(B). Также покалсем, что для всякой аксиомы А, получаемой по ка- кой-нибудь из схем А1-А5, h(A) является тавтологией. Для 1, А2, A3 это очевидно. Всякий частный случай А4 VxiA(xi)=>A(t) преобразуется опера­ цией h в тавтологию вида В^В, а всякий частный случай А5 \/Xi{A=>B)=i>(A=i>\fxiB)-в тавтологию вида (C=>Z))=>(C=> £)). Далее: 1) пусть h{A) и h{A^B)=h{A)^h{B) тавтологии, тогда h{B) ~ тоже тавтология; 2) если h(A) — тавтология, то h(\fXiA) - тавтология, ибо результа­ ты применения операции h к-^ и к совпадают. 174