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

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

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

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

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

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

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

Двойственная форма доказательства Гёделя

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

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

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

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

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

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

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

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

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

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

Решения