отсюда, в частности, следует, что если утверждение x Є Aу доказуемо в данной системе, то число х действительно является элементом множества Ау.
Пусть Р — это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом А (это множество всех чисел, не принадлежащих А). Наконец, через А* мы будем обозначать множество всех чисел х, для которых число x*х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия Gi, G2 и G3:
Условие G1. Множество Р допускает наименование в данной системе. Иначе говоря, существует по крайней мере одно число р, для которого Ар представляет собой множество гёделевых номеров доказуемых утверждений. (Для системы Фергюссона таким р было число 8.)
Условие G2. Дополнение любого множества, допускающего наименование в данной системе, также именуемо в этой системе. Иначе говоря, для любого числа х найдется такое число х, для которого множество А* является дополнением множества Ах. (Для системы Фергюссона таким х было число 3х.)
Условие G3. Для любого именуемого множества А множество А* также именуемо в данной системе. Иначе говоря, для любого числа x всегда найдется такое число х*, что множество А, — представляет собой, множество всех чисел n, для которых n*n принадлежит А, (Для системы Фергюссона таким х* было число 3x+1.)
Очевидно, что условия F1, F2 и Fз, характеризующие машину Фергюссона, представляют собой не более чем частные случаи условий G1, G2 и G3. Последние имеют большое значение потому, что они действительно выполняются для самых разнообразных математических систем, в том числе и для тех двух систем, которые рассмотрены в работе Гёделя. Другими словами, оказывается возможным расположить все допускающие наименование множества в виде бесконечной последовательности A1, A2…, An… и ввести для всех утверждений некоторую частную нумерацию Гёделя, причем так, что будут выполняться условия G 1, G2 и G3. В результате все то, что является доказуемым для систем, удовлетворяющих условиям G1, G2 и G3, будет применимо ко многим другим важным системам. Теперь мы можем сформулировать и доказать теорему Гёделя в общей форме.
Теорема G. Для любой правильной системы, удовлетворяющей условиям G1, G2 и G3, должно существовать утверждение, которое является истинным, но недоказуемым в данной системе.
Доказательство теоремы G представляет собой простое обобщение доказательства, которое уже известно читателю для системы Фергюссона. Обозначим через К множество таких чисел х, для которых элемент х*х не принадлежит множеству Р. Поскольку множество Р (согласно условию G1) именуемо в данной системе, то же можно сказать и о его дополнении Р (согласно условию G2), а следовательно, и о множестве Р* (согласно условию G3). Но множество Р* совпадает с множеством К (поскольку Р* — это множество таких чисел х, для которых х* х принадлежит Р, или, другими словами, множество таких чисел х, для которых элемент х*х не принадлежит Р). Таким образом, множество К допускает наименование в данной системе, откуда следует, что К = А* по крайней мере для одного числа k. (Для системы Фергюссона одним из таких чначений k было число 73, другим — число 75.) Таким образом, для любого числа х истинность утверждения x Є Ak равносильна утверждению, что число х*х не принадлежит Р, а это в свою очередь означает, что утверждение x Є Ax недоказуемо (в данной системе). В частности, если мы возьмем в качестве х число k то истинность утверждения k Є A* будет равносильна его недоказуемости в данной системе, что означает либо истинность, но недоказуемость этого утверждения, либо его ложность, но доказуемость в той же системе. Но последняя возможность исключена, поскольку мы предположили, что наша система является правильной; следовательно, указанное утверждение истинно, но недоказуемо в данной системе.
Обсуждение. В своей предыдущей книжке «Как же называется эта книга?» я рассматривал аналогичную ситуацию — остров, все жители которого делятся на рыцарей, которые всегда говорят только правду, и плутов, которые всегда лгут. При этом некоторых рыцарей мы называли признанными рыцарями, а некоторых плутов — отъявленными плутами. (Все рыцари высказывают истинные суждения, а признанные рыцари высказывают утверждения, которые не только истинны, но и доказуемы.) Далее, ни один из жителей острова не может сказать: «Я не рыцарь» — ведь рыцари никогда не лгут и, стало быть, рыцарь не станет говорить, будто он не рыцарь; плут же никогда не скажет о себе правдиво, что он не рыцарь. Именно поэтому ни один из обитателей острова никак не может заявить, что он не рыцарь. Вместе с тем некий островитянин вполне может сказать: «Я непризнанный рыцарь». Противоречия в таком заявлении нет, однако вот что интересно: сказавший это наверняка должен быть рыцарем, но непризнанным рыцарем. Дело в том, что плут никак не может сделать правдивого заявления, что он непризнанный рыцарь (поскольку он и в самом деле им не является); стало быть, говорящий должен быть рыцарем. Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает, — непризнанный рыцарь. (Точно так же высказывание k Є Ak выдающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе.)
Утверждения Гёделя и теорема Тарского
Рассмотрим теперь систему, удовлетворяющую условиям G2; и G3 (условие G1 пока несущественно). Ранее мы определили Р как множество гёделевых номеров всех утверждений, доказуемых в данной системе; пусть теперь Т будет множеством гёделевых номеров всех истинных утверждений в этой системе. В 1933 г. логик Альфред Тарский поставил вопрос: «Именуемо ли множество Т в данной системе или нет?» — и ответил на него. Ответ может быть получен на основе лишь условий G2 и G3. Однако, прежде чем говорить об этом, обратимся сначала к вопросу не меньшей важности— о системах, которые удовлетворяют по крайней мере условию G3.
Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для A, если либо X истинно и его гёделев номер принадлежит A, либо X ложно и его гёделев номер не принадлежит A. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит A: если это утверждение истинно, то его гёделев номер действительно принадлежит A; если же оно ложно, то его гёделев номер не принадлежит A.) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества Л, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для A.
При этом самым существенным для нас пунктом является следующая теорема.
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 53 54 55 56
Пусть Р — это набор гёделевых номеров всех доказуемых в данной системе утверждений. Пусть опять же для любого множества чисел А его дополнение обозначается символом А (это множество всех чисел, не принадлежащих А). Наконец, через А* мы будем обозначать множество всех чисел х, для которых число x*х принадлежит А. При этом нас будут интересовать системы, для которых выполняются следующие три условия Gi, G2 и G3:
Условие G1. Множество Р допускает наименование в данной системе. Иначе говоря, существует по крайней мере одно число р, для которого Ар представляет собой множество гёделевых номеров доказуемых утверждений. (Для системы Фергюссона таким р было число 8.)
Условие G2. Дополнение любого множества, допускающего наименование в данной системе, также именуемо в этой системе. Иначе говоря, для любого числа х найдется такое число х, для которого множество А* является дополнением множества Ах. (Для системы Фергюссона таким х было число 3х.)
Условие G3. Для любого именуемого множества А множество А* также именуемо в данной системе. Иначе говоря, для любого числа x всегда найдется такое число х*, что множество А, — представляет собой, множество всех чисел n, для которых n*n принадлежит А, (Для системы Фергюссона таким х* было число 3x+1.)
Очевидно, что условия F1, F2 и Fз, характеризующие машину Фергюссона, представляют собой не более чем частные случаи условий G1, G2 и G3. Последние имеют большое значение потому, что они действительно выполняются для самых разнообразных математических систем, в том числе и для тех двух систем, которые рассмотрены в работе Гёделя. Другими словами, оказывается возможным расположить все допускающие наименование множества в виде бесконечной последовательности A1, A2…, An… и ввести для всех утверждений некоторую частную нумерацию Гёделя, причем так, что будут выполняться условия G 1, G2 и G3. В результате все то, что является доказуемым для систем, удовлетворяющих условиям G1, G2 и G3, будет применимо ко многим другим важным системам. Теперь мы можем сформулировать и доказать теорему Гёделя в общей форме.
Теорема G. Для любой правильной системы, удовлетворяющей условиям G1, G2 и G3, должно существовать утверждение, которое является истинным, но недоказуемым в данной системе.
Доказательство теоремы G представляет собой простое обобщение доказательства, которое уже известно читателю для системы Фергюссона. Обозначим через К множество таких чисел х, для которых элемент х*х не принадлежит множеству Р. Поскольку множество Р (согласно условию G1) именуемо в данной системе, то же можно сказать и о его дополнении Р (согласно условию G2), а следовательно, и о множестве Р* (согласно условию G3). Но множество Р* совпадает с множеством К (поскольку Р* — это множество таких чисел х, для которых х* х принадлежит Р, или, другими словами, множество таких чисел х, для которых элемент х*х не принадлежит Р). Таким образом, множество К допускает наименование в данной системе, откуда следует, что К = А* по крайней мере для одного числа k. (Для системы Фергюссона одним из таких чначений k было число 73, другим — число 75.) Таким образом, для любого числа х истинность утверждения x Є Ak равносильна утверждению, что число х*х не принадлежит Р, а это в свою очередь означает, что утверждение x Є Ax недоказуемо (в данной системе). В частности, если мы возьмем в качестве х число k то истинность утверждения k Є A* будет равносильна его недоказуемости в данной системе, что означает либо истинность, но недоказуемость этого утверждения, либо его ложность, но доказуемость в той же системе. Но последняя возможность исключена, поскольку мы предположили, что наша система является правильной; следовательно, указанное утверждение истинно, но недоказуемо в данной системе.
Обсуждение. В своей предыдущей книжке «Как же называется эта книга?» я рассматривал аналогичную ситуацию — остров, все жители которого делятся на рыцарей, которые всегда говорят только правду, и плутов, которые всегда лгут. При этом некоторых рыцарей мы называли признанными рыцарями, а некоторых плутов — отъявленными плутами. (Все рыцари высказывают истинные суждения, а признанные рыцари высказывают утверждения, которые не только истинны, но и доказуемы.) Далее, ни один из жителей острова не может сказать: «Я не рыцарь» — ведь рыцари никогда не лгут и, стало быть, рыцарь не станет говорить, будто он не рыцарь; плут же никогда не скажет о себе правдиво, что он не рыцарь. Именно поэтому ни один из обитателей острова никак не может заявить, что он не рыцарь. Вместе с тем некий островитянин вполне может сказать: «Я непризнанный рыцарь». Противоречия в таком заявлении нет, однако вот что интересно: сказавший это наверняка должен быть рыцарем, но непризнанным рыцарем. Дело в том, что плут никак не может сделать правдивого заявления, что он непризнанный рыцарь (поскольку он и в самом деле им не является); стало быть, говорящий должен быть рыцарем. Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает, — непризнанный рыцарь. (Точно так же высказывание k Є Ak выдающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе.)
Утверждения Гёделя и теорема Тарского
Рассмотрим теперь систему, удовлетворяющую условиям G2; и G3 (условие G1 пока несущественно). Ранее мы определили Р как множество гёделевых номеров всех утверждений, доказуемых в данной системе; пусть теперь Т будет множеством гёделевых номеров всех истинных утверждений в этой системе. В 1933 г. логик Альфред Тарский поставил вопрос: «Именуемо ли множество Т в данной системе или нет?» — и ответил на него. Ответ может быть получен на основе лишь условий G2 и G3. Однако, прежде чем говорить об этом, обратимся сначала к вопросу не меньшей важности— о системах, которые удовлетворяют по крайней мере условию G3.
Для любого заданного утверждения X и любого множества положительных целых чисел А мы будем называть X гёделевым утверждением для A, если либо X истинно и его гёделев номер принадлежит A, либо X ложно и его гёделев номер не принадлежит A. (Подобное утверждение можно представлять себе как высказывание о том, что его собственный гёделев номер принадлежит A: если это утверждение истинно, то его гёделев номер действительно принадлежит A; если же оно ложно, то его гёделев номер не принадлежит A.) Далее, мы будем называть систему гёделевой в том случае, если для каждого множества Л, допускающего наименование в этой системе, существует хотя бы одно гёделево утверждение для A.
При этом самым существенным для нас пунктом является следующая теорема.
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 53 54 55 56