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

2. В системе Фергюссона при любом заданном числе n множество A 3· n +1представляет собой множество A n *. Поэтому множество A 301— это есть множество A 100*. Воспользуемся теперь результатом предыдущей задачи, положив b равным 301. Тогда утверждение 301 ∈ A 301будет гёделевым утверждением для множества A 100. Вообще для любого числа n , выбрав b = 3· n +1, мы получим, что утверждение b ∈ A b , является гёделевым для множества A n в системе Фергюссона.

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

Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества P̅ .

4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества T, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. Следовательно, ни одно утверждение не может оказаться гёделевым для T̅ , потому что не может существовать ни истинного утверждения X, гёделев номер которого принадлежал бы множеству T̅ , ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству T̅ .

Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для A̅ , но никак не для обоих множеств сразу.

5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G 3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества T̅ . Следовательно, если система удовлетворяет условию G 3, то множество T̅ не допускает имени в этой системе. Если система удовлетворяет к тому же условию G 3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G 3, допускало бы имя и его дополнение T̅ , что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G 2и G 3, множество Т не именуемо.

Окончательно: а) если выполняется условие G 3, то множество T̅ не именуемо в данной системе; б) если выполняются условия G 1и G 3, то ни множество Т, ни его дополнение T̅ в этой системе не именуемы.

6. Как только теорема Т доказана, теорему G можно получить следующим образом.

Предположим, что мы имеем правильную систему, удовлетворяющую условиям G 1; G 2и G 3— Из условий G 2и G 3, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию G 1, множество P допускает имя в данной системе. Поэтому раз P допускает имя в рамка системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству P, входит также и в множество Т, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством P, в множестве Т должно существовать хотя бы одно число n , которое не принадлежит P. Вместе с тем, поскольку это n принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X. Но поскольку это число n не принадлежит P, то утверждение X должно быть недоказуемым в данной системе. Значит, утверждение X истинно, но недоказуемо в данной системе. Итак, теорема G действительно имеет место.

7. Пусть теперь нам даны условия G' 1и G 3.

а. Согласно условию G' 1, множество R именуемо в данной системе. Тогда, согласно условию G 3, множество R * также допускает имя в рамках этой системы. Следовательно, существует такое число h, при котором A h = R *. Далее, по определению множества R * число x принадлежит R * в том и только том случае, если число x*x принадлежит множеству R . Поэтому для любого x это x принадлежит A h в том и только том случае, если число x*x входит в множество R . В частности, если к качестве x выбрать h, то число h будет принадлежать, A h в том и только том случае, если число h*h входит в R. Далее, h принадлежит A h в том и только том случае, если утверждение h ∈ A h , истинно. С другой стороны, поскольку число h*h есть гёделев номер утверждения h ∈ A h , то h*h входит в R в том и только в том случае, если утверждение h ∈ A h опровержимо. Значит, утверждение h ∈ A h истинно в том и только в том случае, если оно опровержимо. Отсюда следует, что данное утверждение либо истинно и опровержимо, либо ложно и неопровержимо. Однако оно не может быть истинным и опровержимым, поскольку наша система правильна по условию задачи; следовательно, оно должно быть ложным и неопровержимым. Наконец, раз это утверждение ложно, оно не может быть и доказуемым (опять же потому, что система правильна). Таким образом, утверждение h ∈ A h , недоказуемо и неопровержимо (и, кроме того, оно ложно).

б. Пусть нам дано, что множество A 10— это R и что A 5· n при любом числе n совпадает с множеством A n *. Значит, A 50есть множество R *. Тогда, согласно решению «а», если принять h = 50, то утверждение 50 ∈ A 50будет недоказуемым и неопровержимым. Кроме того, это утверждение будет ложным.

Рассмотрим теперь доказательство Гёделя с несколько иной точки зрения, которая позволяет увидеть основную идею особенно ярко.

Возьмем четыре символа P, N, А, ‒ и рассмотрим всевозможные комбинации этих символов. Произвольную комбинацию указанных символов мы будем называть выражением. Например, выражением является комбинация P‒‒NA‒P; точно так же выражением будет комбинация ‒PN‒‒А‒P‒. Некоторым выражениям мы будем приписывать определенный смысл — такие выражения в дальнейшем будут называться утверждениями .