Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
построения неразрешимых утверждений можно использовать как тот, так и другой метод.
2. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно так же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который заявляет,1 что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)
Решения
1. Предположим, система действительно удовлетворяет условию С3. Пусть в—любое множество, именуемое в данной системе. Тогда, согласно условию С3, множество 5* тоже именуемо в этой системе. Значит, существует такое число Ь, для которого Аь = 5*. Далее, число х принадлежит множеству 5* только в том случае, если число х*х принадлежит множеству 8.
183
Поэтому х принадлежит множеству Аь только в том случае, если х*х принадлежит 5. В частности, если в качестве х выбрать число Ъ, то это число принадлежит множеству Аь только в том случае, если число Ь*Ь принадлежит множеству 5. Кроме того, число Ъ принадлежит Аь в том и только том случае, если утверждение ЬЕ.Аь истинно. Поэтому утверждение ЬеАь истинно тогда и только тогда, когда Ь*Ь принадлежит множеству 5. Но число Ъ*Ъ есть гёделев номер утверждения Ье.Аь• Следовательно, мы имеем, что утверждение ЬЕ А ь будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству 5. Итак, если утверждение ЬЕАь истинно, то его гёделев номер принадлежит 5; если же это утверждение ложно, то его гёделев номер не принадлежит 5. Таким образом, утверждение ЬЕАь является гёделевым утверждением для 5.
2. В системе Фергюссона при любом заданном числе п множество Дз-я+1 представляет собой множество А * Поэтому множество А 301 — это есть множество А100. Воспользуемся теперь результатом предыдущей задачи, положив Ь равным 301. Тогда утверждение 301Е А301 будет гёделевым утверждением для множества А юо. Вообще для любого числа п, выбрав Ь=3*и+1, мы получим, что утверждение ЬЕ А ь является гёделевым для множества Ап в системе Фергюссона.
3. Да. Предположим, что данная система является гёделевой и что условия в! и в2 выполняются; предположим также, что система правильна. Согласно условию вь множество Р именуемо в этой системе; поэтому, согласно условию в 2, именуемо также и множество Р—дополнение Р. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит Р, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для Р—это ни больше ни меньше как утверждение, которое истинно в
184
том и только том случае, если оно недоказуемо в данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).
Итак, фактически суть доказательства Гёделя состоит^ построении гёделева утверждения для множества Р.
4. Очевидно, что всякое утверждение X является гёде-левым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. Следовательно, ни_одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х^_ гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.
Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.
5. Рассмотрим сначала произвольную систему, удовлетворяющую условию С3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи ^не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию С3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию Иг, то множество Т не именуемо в этой системе — потому что если бы это было так, то тогда, согласно условию О 2, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям в 2 и йз, множество Т не именуемо.
Окончательно: а) если выполняется условие С3, то множество Т не именуемо в данной системе; б) если
выполняются условия и2 и и3, то ни множество Т, ни его дополнение Т в этой системе не именуемы.
6. Как только теорема Т доказана, теорему С можно получить следующим образом.
Предположим, что мы имеем правильную систему, удовлетворяющую условиям О), О 2 и 03, Из условий в 2 и 03, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию в и множество Р допускает имя в данной системе. Поэтому раз Р допускает имя в рамках системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству Р, входит также и в множество Г, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством Р, в множестве Г должно существовать хотя бы одно число и, которое не принадлежит Р. Вместе с тем, поскольку это и принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X. Но поскольку это число п не принадлежит Р, то утверждение X должно быть недоказуемым в данной системе. Значит, утверждение X истинно, но недоказуемо в данной системе. Итак, теорема О действительно имеет место.
