Что можно сказать о свойствах утверждения X?
Высказанная здесь идея развивается нами в следующей задаче.
7. Рассмотрим теперь правильную систему, которая удовлетворяет условию G3, а вместо условий G1 G2 потребуем выполнения следующего условия.
Условие G1. Множество R именуемо в данной системе. (Таким образом, мы предполагаем, что система правильна и удовлетворяет условиям G1 и G3.)
а. Показать, что существует такое утверждение, которое нельзя ни доказать, ни опровергнуть в данной системе.
б. Рассмотрим следующий частный случай: пусть нам дано, что а10 — это множество R и что для любого числа n множество А5n представляет собой множество (таких чисел х, для которых число х*х принадлежит Аn (здесь мы имеем частный случай условия G3). Задача теперь состоит в том, чтобы найти утверждение, которое было бы и недоказуемым, и неопровержимым и данной системе, а также определить, является ли это утверждение истинным или ложным.
Примечания.
1. Гёлелев метод получения неразрешимого утверждения сводится к построению гёделева утверждения для множества Р — дополнения R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. Двойственный метод сводится к построению гёделева утверждения не для множества Р, а для множества R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым. (Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе.) Следует отметить, что те системы, которые рассматриваются в оригинальной работе Гёделя, удовлетворяют всем четырем условиям — G1, G2, G3 и G1, так что для построения неразрешимых утверждений можно использовать как тот, как и другой метод.
2. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который шявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)
Решения
1. Предположим, система действительно удовлетворяет условию G3. Пусть S—любое множество, именуемое в данной системе. Тогда, согласно условию G3, множество S* тоже именуемо в этой системе. Значит, существует такое число b, для которого Аb = 8*. Далее, число х принадлежит множеству S* только в том случае, если число х*х принадлежит множеству S.
Поэтому х принадлежит множеству Аb только в том случае, если х*х принадлежит S. В частности, если в качестве х выбрать число b, то это число принадлежит; множеству Ab, только в том случае, если число b* принадлежит множеству S. Кроме того, число b принадлежит Ab в том и только том случае, если утверждение b Є Аb истинно. Поэтому утверждение b Є Аb истинно тогда и только тогда, когда b*b принадлежит множеству S. Но число b*b есть гёделев номер утверждения b Є Ab. Следовательно, мы имеем, что утверждение b Є Ab будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству S. Итак, если утверждение b Є A истинно, то его гёделев номер принадлежит S; если ж это утверждение ложно, то его гёделев номер принадлежит S. Таким образом, утверждение b Є A является гёделевым утверждением для S.
2. В системе Фергюссона при любом заданном числе n множество а3n+i представляет собой множество An*. Поэтому множество A301 — это есть множество A Воспользуемся теперь результатом предыдущей задачи, положив b равным 301. Тогда утверждение 301 Є А301 будет гёделевым утверждением для множества Аb. Вообще для любого числа n, выбрав d = 3n+1, мы получим, что утверждение b Є Ab, является гёделевым для множества Ab в системе Фергюссона.
3. Да. Предположим, что данная система является гёделевой и что условия G1 и G2 выполняются; предположим также, что система правильна. Согласно условию G1, множество R именуемо в этой системе; поэтому, согласно условию G1, именуемо также и множество Р — дополнение R. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит R, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для R — это ни больше ни меньше как утверждение, которое истинно в том и только том случае, если оно недоказуемо в (данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).
Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества Р.
4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. (cследовательно, ни одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х, гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.
Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.
5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию G3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию G3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G3, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G2 и G3, множество Т не именуемо.
Окончательно:
а) если выполняется условие G 3, то множество Т не именуемо в данной системе;
б) если выполняются условия G1 и G3, то ни множество Т, ни его дополнение Т в этой системе не именуемы.
6. Как только теорема Т доказана, теорему G можно получить следующим образом.
Предположим, что мы имеем правильную систему, удовлетворяющую условиям G1; G2 и G3 — Из условий G2 и G3, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию G1, множество Р допускает имя в данной системе. Поэтому раз Р допускает имя в рамка системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству Р, входит также и в множество Т, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством Р, в множестве Т должно существовать хотя бы одно число n, которое не принадлежит Р. Вместе с тем, поскольку это n принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Высказанная здесь идея развивается нами в следующей задаче.
7. Рассмотрим теперь правильную систему, которая удовлетворяет условию G3, а вместо условий G1 G2 потребуем выполнения следующего условия.
Условие G1. Множество R именуемо в данной системе. (Таким образом, мы предполагаем, что система правильна и удовлетворяет условиям G1 и G3.)
а. Показать, что существует такое утверждение, которое нельзя ни доказать, ни опровергнуть в данной системе.
б. Рассмотрим следующий частный случай: пусть нам дано, что а10 — это множество R и что для любого числа n множество А5n представляет собой множество (таких чисел х, для которых число х*х принадлежит Аn (здесь мы имеем частный случай условия G3). Задача теперь состоит в том, чтобы найти утверждение, которое было бы и недоказуемым, и неопровержимым и данной системе, а также определить, является ли это утверждение истинным или ложным.
Примечания.
1. Гёлелев метод получения неразрешимого утверждения сводится к построению гёделева утверждения для множества Р — дополнения R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. Двойственный метод сводится к построению гёделева утверждения не для множества Р, а для множества R; такое утверждение (его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым. (Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе.) Следует отметить, что те системы, которые рассматриваются в оригинальной работе Гёделя, удовлетворяют всем четырем условиям — G1, G2, G3 и G1, так что для построения неразрешимых утверждений можно использовать как тот, как и другой метод.
2. Высказывание, которое утверждает собственную недоказуемость, можно сравнить со словами того обитателя острова рыцарей и плутов, который заявляет, будто он непризнанный рыцарь, точно гак же высказывание, утверждающее свою собственную опровержимость, можно уподобить словам такого обитателя острова, который шявляет, что он отъявленный плут; этот человек и в самом деле мошенник, но неотъявленный. (Предоставляю читателю возможность доказать это самому.)
Решения
1. Предположим, система действительно удовлетворяет условию G3. Пусть S—любое множество, именуемое в данной системе. Тогда, согласно условию G3, множество S* тоже именуемо в этой системе. Значит, существует такое число b, для которого Аb = 8*. Далее, число х принадлежит множеству S* только в том случае, если число х*х принадлежит множеству S.
Поэтому х принадлежит множеству Аb только в том случае, если х*х принадлежит S. В частности, если в качестве х выбрать число b, то это число принадлежит; множеству Ab, только в том случае, если число b* принадлежит множеству S. Кроме того, число b принадлежит Ab в том и только том случае, если утверждение b Є Аb истинно. Поэтому утверждение b Є Аb истинно тогда и только тогда, когда b*b принадлежит множеству S. Но число b*b есть гёделев номер утверждения b Є Ab. Следовательно, мы имеем, что утверждение b Є Ab будет истинным тогда и только тогда, когда гёделев номер этого утверждения принадлежит множеству S. Итак, если утверждение b Є A истинно, то его гёделев номер принадлежит S; если ж это утверждение ложно, то его гёделев номер принадлежит S. Таким образом, утверждение b Є A является гёделевым утверждением для S.
2. В системе Фергюссона при любом заданном числе n множество а3n+i представляет собой множество An*. Поэтому множество A301 — это есть множество A Воспользуемся теперь результатом предыдущей задачи, положив b равным 301. Тогда утверждение 301 Є А301 будет гёделевым утверждением для множества Аb. Вообще для любого числа n, выбрав d = 3n+1, мы получим, что утверждение b Є Ab, является гёделевым для множества Ab в системе Фергюссона.
3. Да. Предположим, что данная система является гёделевой и что условия G1 и G2 выполняются; предположим также, что система правильна. Согласно условию G1, множество R именуемо в этой системе; поэтому, согласно условию G1, именуемо также и множество Р — дополнение R. Тогда, поскольку исходная система гёделева, то существует гёделево утверждение X для Р. Это означает, что X истинно в том и только том случае, если гёделев номер утверждения X принадлежит Р. Однако если гёделев номер утверждения X принадлежит Р, то тем самым он не принадлежит R, а это значит, что утверждение X недоказуемо. Таким образом, гёделево утверждение для R — это ни больше ни меньше как утверждение, которое истинно в том и только том случае, если оно недоказуемо в (данной системе, а такое утверждение (как мы уже видели) как раз и должно быть истинным, но недоказуемым в этой системе (если система правильна).
Итак, фактически суть доказательства Гёделя состоит в построении гёделева утверждения для множества Р.
4. Очевидно, что всякое утверждение X является гёделевым утверждением для множества Т, потому что если X истинно, то его гёделев номер принадлежит Т, а если оно ложно, то его гёделев номер не принадлежит Т. (cследовательно, ни одно утверждение не может оказаться гёделевым для Т, потому что не может существовать ни истинного утверждения Х, гёделев номер которого принадлежал бы множеству Т, ни ложного утверждения X, гёделев номер которого не принадлежал бы множеству Т.
Читателю будет поучительно убедиться, что для любого множества чисел А и для любого утверждения X это X может являться гёделевым утверждением либо для А, либо для А, но никак не для обоих множеств сразу.
5. Рассмотрим сначала произвольную систему, удовлетворяющую условию G3. В соответствии с решением задачи 1 для любого множества, именуемого в рамках данной системы, существует гёделево утверждение. Кроме того, согласно решению задачи 4 не существует гёделева утверждения для множества Т. Следовательно, если система удовлетворяет условию G3, то множество Т не допускает имени в этой системе. Если система удовлетворяет к тому же условию G3, то множество Т не именуемо в этой системе — потому что ли бы это было так, то тогда, согласно условию G3, допускало бы имя и его дополнение Т, что на самом деле не имеет места. Это доказывает, что в системе, удовлетворяющей условиям G2 и G3, множество Т не именуемо.
Окончательно:
а) если выполняется условие G 3, то множество Т не именуемо в данной системе;
б) если выполняются условия G1 и G3, то ни множество Т, ни его дополнение Т в этой системе не именуемы.
6. Как только теорема Т доказана, теорему G можно получить следующим образом.
Предположим, что мы имеем правильную систему, удовлетворяющую условиям G1; G2 и G3 — Из условий G2 и G3, согласно теореме Т, следует, что множество Т не допускает имени в данной системе. Но, согласно условию G1, множество Р допускает имя в данной системе. Поэтому раз Р допускает имя в рамка системы, а Т нет, то, значит, это должны быть разные множества. Однако каждое число, принадлежащее множеству Р, входит также и в множество Т, поскольку нам дано, что система является правильной в том смысле, что каждое доказуемое утверждение в ней истинно. Стало быть, поскольку множество Т не совпадает с множеством Р, в множестве Т должно существовать хотя бы одно число n, которое не принадлежит Р. Вместе с тем, поскольку это n принадлежит Т, оно должно быть гёделевым номером некоего истинного утверждения X.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52