Cтраница 2
Ягэ Вх & ( х)) эВж ( Лэ ( ж)) мы покажем аналогично недоказуемости Ilcj n lib ( после применения теоремы 22 с k 2 мы получим в строке 3: гэ. [16]
Пусть эта формула имеет геделевский номер г. Тогда Vb ] P ( r г Ь) выражает недоказуемость формулы 10 и, следовательно непротиворечивость системы. Выше мы видели, что из того, что система непротиворечива следует, что А ( р) недоказуема. Если доказательство этого факта формализуется в формальной арифметич. [17]
Но так как, с другой стороны, в своих рассуждениях о сумме счастья автор признает, что, несмотря на недоказуемость положений христианской религии, она все же имеет множество последователей, то, с тем большим основанием, некоторые лица могут довести себя до полного разорения во имя великой цели, поскольку, как утверждает автор, есть возможность достичь успеха. [18]
Система G3 предназначена для сокращения числа выборов посылок для данного заключения, когда мы пытаемся исчерпать возможность доказательства данной конечной секвенции, особенно когда мы пытаемся доказать недоказуемость данной конечной секвенции. Если же конечная секвенция доказуема, то применение системы G3a обычно позволяет сокращать секвенции, использованные в доказательстве. [19]
Геделев метод получения неразрешимого утверждения сводится к построению геделева утверждения для множества Р - дополнения Р; такое утверждение ( его можно рассматривать как высказывание, утверждающее собственную недоказуемость) должно быть истинным, но недоказуемым в данной системе. Двойственный метод сводится к построению геделева утверждения не для множества Р, а для множества R; такое утверждение ( его можно рассматривать как высказывание, утверждающее собственную опровержимость) должно быть ложным, но неопровержимым. Поскольку оно ложно, оно так же недоказуемо и, следовательно, неразрешимо в данной системе. Следует отметить, что те системы, которые рассматриваются в оригинальной работе Геделя, удовлетворяют всем четырем условиям - Glt GI, G3 и Gj, так что для построения неразрешимых утверждений можно использовать как тот, так и другой метод. [20]
В своей монографии Теория формальных систем ( 1960 г.) я рассматривал двойственную форму доказательства Геделя, а именно: что будет, если вместо высказывания, утверждающего свою недоказуемость, построить высказывание, утверждающее свою опровер-жимость. Более строго эту проблему можно сформулировать так. [21]
Быть может, наиболее известным результатом о невозможности в математике явилось открытие геометрии Лобачевского, центральный результат которой ] - невозможность, вывести аксиому параллельных из остальных аксиом геометрии Евклида, ее недоказуемость. [22]
При дальнейшем изучении окажется, что можно использовать эту возможность и с помощью канторовского диагонального метода ( § 2) построить замкнутую формулу А, которая с точки зрения лица, знающего эту нумерацию, выражает свою собственную недоказуемость. [23]
Для связи с предварительным эвристическим изложением заметим, что формулу Ар ( р) можно с точки зрения геделевской нумерации рассматривать как выражающую предложение, что Ар ( р) недоказуема, иными словами, это есть формула А, которая выражает свою собственную недоказуемость. [24]
В метаматематическом изложении исходные допущения эвристического рассуждения, что система не допускает доказательства формулы А или - i A, если эта формула ложна, должны быть заменены метаматематическими эквивалентами. Для недоказуемости формулы - i А в случае ее ложности нам потребуется более сильное условие, так называемая ш-непротиворечивость, к определению которой мы сейчас приступаем. [25]
Теорема 6.1 дает простой способ проверки того, доказуема ли данная формула а. Для доказательства недоказуемости формулы а в ff достаточно найти реализацию, в которой а не общезначима. [26]
К выводу о недоказуемости высказывания Р мы пришли, рассуждая от противного: иначе высказывание и его отрицание были бы доказуемы одновременно. Вывод о существовании неразрешимых для машин высказываний был получен в предположении, что машина не может доказывать противоречивые высказывания. [27]
Но раз он рыцарь, то, значит, должен говорить правду; стало быть, он рыцарь, но, как он сам утверждает - непризнанный рыцарь. Ak, утверждающее свою недоказуемость в данной системе, должно быть истинным, но недоказуемым в этой системе. [28]
Действительно, как отмечено выше ( с помощью следствия 1 из теоремы 37), имеет место обратное-формула доказуема, если она истинна при всех интерпретациях, при которых истинны все аксиомы. Значит, в силу известной недоказуемости формулы Ар ( /), невозможно, чтобы эта формула была истинной при всех интерпретациях, выполняющих аксиомы. Но ( как замечено выше, с помощью теоремы 21) если предикатные формулы с равенством, образующие счетный класс, совместно выполнимы, то формальная система, полученная путем присоединения их в виде аксиом к исчислению предикатов с равенством, ( просто) непротиворечива. Таким образом, если дан любой класс формул, удовлетворяющий условиям теоремы 44, то, присоединяя постулаты группы В и воспроизводя в полученной системе доказательство теоремы 28 ( или пользуясь частью III теоремы XIII § 60), мы получаем доказательство теоремы 44 в общем виде. [29]
В настоящей главе мы намереваемся исследовать два тесно связанных между собой вопроса о Z и других теориях: доказуема ли в Z непротиворечивость самой Z и истинно ли ( и, таким образом, доказуемо) или ложно ( и, таким образом, недоказуемо) некоторое предложение, которое можно рассматривать как предложение, утверждающее свою собственную доказуемость в Z. В отличие от вопроса доказуемо или нет предложение, выражающее свою собственную недоказуемость ( в Z), - любое такое предложение должно быть одновременно истинно и недоказуемо, если все, что доказуемо, истинно, - a priori кажется, что не существует легкого пути решить этот второй вопрос. [30]