Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для А, если либо X истинно и его гёделев номер принадлежит А, либо X ложно и его гёделев номер не принадлежит А. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит А: если это утверждение истинно, то его гёделев номер действительно принадлежит А; если же оно ложно, то его гёделев номер не принадлежит А.) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества А, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для А.
При этом самым существенным для нас пунктом является следующая теорема.
Теорема С. Если система удовлетворяет условию вз, то эта система является гёделевой.
180
1. Докажите теорему С.
2. В качестве частного случая рассмотрите систему Фергюссона. Найдите гёделево утверждение для множества А )оо.
3. Предположим, что некоторая система является гёде-левой (даже если она и не удовлетворяет условию Эз). Если эта система правильна и удовлетворяет условиям б] и 62, то обязательно ли она содержит утверждение, которое является истинным, но недоказуемым в данной системе?
4. Пусть Т—множество гёделевых номеров всех истинных утверждений. Существует ли гёделево утверждение для Г?_Существует ли гёделево утверждение для множества Т, то есть дополнения Г?
Вот теперь мы наконец можем ответить и на вопрос, поставленный Тарским. В самой общей форме теорема Тарского формулируется следующим образом:
Теорема Т. Для любой заданной системы, удовлетворяющей условиям С2 и Оз, множество Т гёделевых номеров истинных утверждений не именуемо в данной системе.
п римечание. Иногда слово «именуемо» заменяется словом «определимо», в результате чего теорему Т формулируют так: для достаточно богатой системы истинность в ее рамках не определима в этой системе.
5. Докажите теорему Т.
6. Следует отметить, что, доказав теорему Т, мы сразу в качестве непосредственного следствия получаем теорему О. Может ли читатель сообразить, как это сделать?
Двойственная форма доказательства Гёделя
Те системы, которые, как доказал Гёдель, являются неполными, обладают также следующим свойством: с
каждым утверждением X связано утверждение X, оно называется отрицанием X, которое истинно в том и только том случае, если утверждение X ложно. Далее, если X'—отрицание некоего утверждения X—доказуемо в данной системе, то само утверждение X называется опровержимым в данной системе. Если предположить, что система правильна, то ни одно ложное утверждение в этой системе не будет доказуемо и ни одно истинное утверждение не будет в ней опровержимо.
Ранее мы убедились, что условия О и О г и Оз. влекут за собой существование некоего гёделева утверждения, или высказывания, О для множества Р, а также что такое утверждение О является истинным, но недоказуемым в данной системе (предполагая, конечно* что система правильна). Но поскольку в истинно, оно не может быть опровержимым в этой системе (опять же в предположении правильности системы). Значит, утверждение в в данной системе и не доказуемо, и не опровержимо. (Такое утверждение называется неразре~ шимым в данной системе.)
В своей монографии «Теория формальных систем» * (1960 г.) я рассматривал «двойственную» форму доказательства Гёделя, а именно: что будет, если вместо высказывания, утверждающего свою недоказуемость, построить высказывание, утверждающее свою опровер-жимость? Более строго эту проблему можно сформулировать так. Пусть Р—-множество гёделевых номеров опровержимых утверждений. Предположим, что X— гёделево утверждение для Л. Что можно сказать о свойствах утверждения X?
Высказанная здесь идея развивается нами в следующей задаче.
7. Рассмотрим теперь правильную систему, которая удовлетворяет условию Из, а вместо условий бь Иг потребуем выполнения следующего условия.
Условие О']. Множество 1? именуемо в данной системе. (Таким образом, мы предполагаем, что система правильна и удовлетворяет условиям и Оз.)
* Смальян Р. Теория формальных систем. Пер. с англ.— М.: Наука, 1981.
а. Показать, что существует такое утверждение, которое нельзя ни доказать, ни опровергнуть в данной системе*
б* Рассмотрим следующий частный случай: пусть нам дано, что Лю—это множество 1? и что для любого числа п множество Аз*н представляет собой множество таких чисел х, для которых число х*х принадлежит А п (здесь мы имеем частный случай условия О 3). Задача теперь состоит в том, чтобы найти утверждение, которое было бы и недоказуемым, и неопровержимым в данной системе, а также определить, является ли это утверждение истинным или ложным.
Примечания. 1, Геделев метод получения неразрешимого утверждения_ сводится к построению гёделева утверждения для множества Р—дополнения Р; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. «Двойственный» метод сводится к построению гёделева утверждения не для множества Р, а для множества Р; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым, (Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе.) Следует отметить, что те системы, которые рассматриваются в оригинальной работе Гёделя, удовлетворяют всем четырем условиям — 02, С3 и так что для
