Рэймонд Смаллиан - Принцесса или тигр?

Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для A, если либо X истинно и его гёделев номер принадлежит A, либо X ложно и его гёделев номер не принадлежит A. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит A: если это утверждение истинно, то его гёделев номер действительно принадлежит A; если же оно ложно, то его гёделев номер не принадлежит A. ) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества A, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для A.

При этом самым существенным для нас пунктом является следующая теорема.

Теорема С. Если система удовлетворяет условию G 3, то эта система является гёделевой.

1. Докажите теорему С.

2. В качестве частного случая рассмотрите систему Фергюссона. Найдите гёделево утверждение для множества A 100.

3. Предположим, что некоторая система является гёделевой (даже если она и не удовлетворяет условию G 3). Если эта система правильна и удовлетворяет условиям G 1, и G 2, то обязательно ли она содержит утверждение, которое является истинным, но недоказуемым в данной системе?

4. Пусть Т — множество гёделевых номеров всех истинных утверждений. Существует ли гёделево утверждение для Т ? Существует ли гёделево утверждение для множества T̅ , то есть дополнения Т ?

Вот теперь мы наконец можем ответить и на вопрос, поставленный Тарским. В самой общей форме теорема Тарского формулируется следующим образом:

Теорема Т. Для любой заданной системы, удовлетворяющей условиям G 2 и G 3, множество Т гёделевых номеров истинных утверждений не именуемо в данной системе.

Примечание.Иногда слово «именуемо» заменяется словом «определимо», в результате чего теорему Т формулируют так: для достаточно богатой системы истинность в ее рамках не определима в пой системе.

5. Докажите теорему Т.

6. Следует отметить, что, доказав теорему Т, мы сразу и в качестве непосредственного следствия получаем теорему G. Может ли читатель сообразить, как это сделать?

Те системы, которые, как доказал Гёдель, являются неполными, обладают также следующим свойством: с каждым утверждением X связано утверждение X', о называется отрицанием X, которое истинно в том только том случае, если утверждение X ложно. Далее, если X' — отрицание некоего утверждения X — доказуемо в данной системе, то само утверждение X называется опровержимым в данной системе. Если предположить, что система правильна, то ни одно ложно, утверждение в этой системе не будет доказуемо и ни одно истинное утверждение не будет в ней опровержимо.

Ранее мы убедились, что условия G 1, G 2и G 3влекут за собой существование некоего гёделева утверждения, или высказывания, G для множества, также что такое утверждение G является истинным, не. недоказуемым в данной системе (предполагая, конечно, что система правильна). Но поскольку G истинно, оно не может быть опровержимым в этой системе (опять, же в предположении правильности системы). Значит утверждение G в данной системе и не доказуемо, и неопровержимо. (Такое утверждение называется неразрешимым в данной системе.)

В своей монографии «Теория формальных систем» [10] Смальян Р. Теория формальных систем. Пер. с англ. — М.: Наука, 1981. (1960 г.) я рассматривал «двойственную» форму доказательства Гёделя, а именно: что будет, если вместо высказывания, утверждающего свою недоказуемость, построить высказывание, утверждающее свою опровержимость? Более строго эту проблему можно сформулировать так. Пусть R — множество гёделевых номеров опровержимых утверждений. Предположим, что X — гёделево утверждение для R. Что можно сказать о свойствах утверждения X ?

Высказанная здесь идея развивается нами в следующей задаче.

7. Рассмотрим теперь правильную систему, которая удовлетворяет условию G 3, а вместо условий G 1, G 2потребуем выполнения следующего условия.

Условие G' 1.Множество R именуемо в данной системе. (Таким образом, мы предполагаем, что система правильна и удовлетворяет условиям G 1и G 3.)

а. Показать, что существует такое утверждение, которое нельзя ни доказать, ни опровергнуть в данной системе.

б. Рассмотрим следующий частный случай: пусть нам дано, что A 10— это множество R и что для любого числа n множество A 5* n представляет собой множество (таких чисел х, для которых число x*x принадлежит А n (здесь мы имеем частный случай условия G 3). Задача теперь состоит в том, чтобы найти утверждение, которое было бы и недоказуемым, и неопровержимым и данной системе, а также определить, является ли это утверждение истинным или ложным.

Примечания.1. Гёделев метод получения неразрешимого утверждения сводится к построению гёделева утверждения для множества P̅ — дополнения P ; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. Двойственный метод сводится к построению гёделева утверждения не для множества P̅ , а для множества R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым. (Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе.) Следует отметить, что те системы, которые рассматриваются в оригинальной работе Гёделя, удовлетворяют всем четырем условиям — G 1, G 2, G 3и G 1, так что для построения неразрешимых утверждений можно использовать как тот, как и другой метод.

2. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который заявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)

1. Предположим, система действительно удовлетворяет условию G 3. Пусть S — любое множество, именуемое в данной системе. Тогда, согласно условию G 3, множество S * тоже именуемо в этой системе. Значит, существует такое число b, для которого А b = S *. Далее, число x принадлежит множеству S * только в том случае, если число x*x принадлежит множеству S . Поэтому x принадлежит множеству A b только в том случае, если x*x принадлежит S. В частности, если в качестве x выбрать число b, то это число принадлежит; множеству A b , только в том случае, если число b*b принадлежит множеству S. Кроме того, число b принадлежит A b в том и только том случае, если утверждение b ∈ A b истинно. Поэтому утверждение b ∈ A b истинно тогда и только тогда, когда b*b принадлежит множеству S. Но число b*b есть гёделев номер утверждения b ∈ A b . Следовательно, мы имеем, что утверждение b ∈ A b будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству S. Итак, если утверждение b ∈ A b истинно, то его гёделев номер принадлежит S; если ж это утверждение ложно, то его гёделев номер принадлежит S. Таким образом, утверждение b ∈ A b является гёделевым утверждением для S.