И.А. Пушкарев логика
.pdf
|
151 |
Поэтому длительное |
время многие пытались построить«последнюю» |
теорию, противоречивость |
которой можно доказать исходя из неё самой, не |
прибегая к ссылке на другую теорию. До тех пор, пока Курт Гёдель не доказал теорему о том, что это невозможно. Это был удар! С тех пор все компетентные математики знают, что посвятили жизнь довольно ненадёжному делу J.
Для начала следует доказать синтаксический аналог теоремы Гёделя о неполноте.
Теорема 16.5. (о неполноте, синтаксическая форма) Если синтаксическая теория, в которой выразима арифметика, непротиворечива, то формула H (n) недоказуема в ней.
Доказательство. Предположим, что формула H (n) доказуема. Тогда у неё
имеется |
доказательство |
ζс-номером |
k. |
Поэтому |
истинна |
формула |
|||
ЕzP(k, z )Ù S(z, n, n). Поскольку |
эта формула |
определённая, то она |
имеет |
||||||
доказательство. |
Следовательно |
(правило |
Бернайса, например), доказуема и |
||||||
формула ЕxЕzP(x, z)Ù S(z, |
y, y). Но последняя формула есть отрицание H (n), |
||||||||
следовательно, |
теория Т |
противоречива. |
А |
это |
не . такПолученное |
||||
противоречие доказывает теорему.
QED
Замечание. Можно (гораздо сложнее) показать, что в непротиворечивой теории недоказуема и формула ØH (n). Но для нас это не так уж важно.
Далее, |
|
предположим, |
что |
формула О |
имеет |
номер0. |
Формула |
||||||
с = ØЕxP(x, 0) выражает свойство: «формула О недоказуема», иными словами |
|||||||||||||
«теория |
непротиворечива». |
Наверное, |
можно |
выразить |
это |
|
свойство и |
||||||
некоторыми другими формулами, для следующего рассуждения |
подойдёт |
||||||||||||
любая из них. |
|
|
|
|
|
|
|
|
|
|
|
||
Теорема |
16.6. (теорема |
Гёделя |
о недоказуемости |
непротиворечивости |
|||||||||
теории из неё самой) |
|
|
|
|
|
|
|
|
y, z) |
и P(x, y) |
|||
Пусть Т – непротиворечивая теория в которой формулы S (x, |
|||||||||||||
являются |
определёнными (то |
есть Т – любая сколько-нибудь содержательная |
|||||||||||
теория). Тогда формула с (как и все подобные ей) недоказуема в Т. |
|
H (n) |
|||||||||||
Доказательство. |
Согласно |
предыдущей |
теореме, формула |
||||||||||
недоказуема |
в Т, следовательно |
– она |
истинна. |
Поэтому |
|
она |
семантически |
||||||
следует из формулы с. По теореме Гёделя о полноте исчисления предикатов, |
|||||||||||||
она выводима из неё. |
По |
лемме |
о дедукции из этого |
следует, что |
|
формула |
|||||||
есть теорема, поэтому у неё есть доказательство. Если бы формула с была бы доказуема, то оказалась бы доказуема и формула H (n). Но это не так. Полученное противоречие доказывает теорему.
QED