Принцесса или тигр?

Доказательство теоремы G представляет собой простое обобщение доказательства, которое уже известно читателю для системы Фергюссона. Обозначим через К множество таких чисел х, для которых элемент x*x не принадлежит множеству P. Поскольку множество P (согласно условию G₁) именуемо в данной системе, то же можно сказать и о его дополнении P̅ (согласно условию G₂), а следовательно, и о множестве P̅* (согласно условию G₃). Но множество P̅* совпадает с множеством К (поскольку P̅* — это множество таких чисел х, для которых х*x принадлежит P̅, или, другими словами, множество таких чисел х, для которых элемент x*x не принадлежит P). Таким образом, множество К допускает наименование в данной системе, откуда следует, что К = А_k по крайней мере для одного числа k. (Для системы Фергюссона одним из таких значений k было число 73, другим — число 75.) Таким образом, для любого числа x истинность утверждения x ∈ A_k равносильна утверждению, что число x*x не принадлежит P, а это в свою очередь означает, что утверждение x ∈ A_x недоказуемо (в данной системе). В частности, если мы возьмем в качестве x число k то истинность утверждения k ∈ A_k будет равносильна его недоказуемости в данной системе, что означает либо истинность, но недоказуемость этого утверждения, либо его ложность, но доказуемость в той же системе. Но последняя возможность исключена, поскольку мы предположили, что наша система является правильной; следовательно, указанное утверждение истинно, но недоказуемо в данной системе.

Обсуждение. В своей предыдущей книжке «Как же называется эта книга?» я рассматривал аналогичную ситуацию — остров, все жители которого делятся на рыцарей, которые всегда говорят только правду, и плутов, которые всегда лгут. При этом некоторых рыцарей мы называли признанными рыцарями, а некоторых плутов — отъявленными плутами. (Все рыцари высказывают истинные суждения, а признанные рыцари высказывают утверждения, которые не только истинны, но и доказуемы.) Далее, ни один из жителей острова не может сказать: «Я не рыцарь» — ведь рыцари никогда не лгут и, стало быть, рыцарь не станет говорить, будто он не рыцарь; плут же никогда не скажет о себе правдиво, что он не рыцарь. Именно поэтому ни один из обитателей острова никак не может заявить, что он не рыцарь. Вместе с тем некий островитянин вполне может сказать: «Я непризнанный рыцарь». Противоречия в таком заявлении нет, однако вот что интересно: сказавший это наверняка должен быть рыцарем, но непризнанным рыцарем. Дело в том, что плут никак не может сделать правдивого заявления, что он непризнанный рыцарь (поскольку он и в самом деле им не является); стало быть, говорящий должен быть рыцарем. Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает, — непризнанный рыцарь. (Точно так же высказывание k ∈ A_k выдающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе.)

Утверждения Гёделя и теорема Тарского

Рассмотрим теперь систему, удовлетворяющую условиям G₂; и G₃ (условие G₁ пока несущественно). Ранее мы определили P как множество гёделевых номеров всех утверждений, доказуемых в данной системе; пусть теперь Т будет множеством гёделевых номеров всех истинных утверждений в этой системе. В 1933 г. логик Альфред Тарский поставил вопрос: «Именуемо ли множество Т в данной системе или нет?» — и ответил на него. Ответ может быть получен на основе лишь условий G₂ и G₃. Однако, прежде чем говорить об этом, обратимся сначала к вопросу не меньшей важности — о системах, которые удовлетворяют по крайней мере условию G₃.

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

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

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

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

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

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