Cтраница 2
При любом фиксированном целом положительном для того, чтобы предикатная формула Е была доказуемой ( или выводимой из k - тождественных формул Г) в исчислении предикатов, необходимо, чтобы Е была k - тождественной. [16]
Если для данного k столбец значений таблицы для какой-нибудь предикатной формулы, рассматриваемой как функция от некоторой системы свободных переменных и предикатных букв, охватывающей все свободные переменные и предикатные буквы данной формулы, содержит одни только t, мы будем говорить, что эта формула является k - тождественной, или всегда - истинной ( иначе общезначимой) в области из k предметов. Если этот столбец значений содержит хоть одно t, то формула называется выполнимой в области из k предметов. [17]
Отметим еще, что если для обозначения формул в предикатной формуле пользоваться кодами из 5, то есть возможность определить порядок применения формул по адресу. Если предикатная функция Р тождественно равна 1, то в соответствующей предикатной формуле второй индекс опускается. [18]
В терминах теоретико-множественной интерпретации полнота исчисления предикатов должна означать, что каждая предикатная формула, всегда-истинная в любой непустой области, доказуема. Эта интерпретация нефинитна, в отличие от соответствующей интерпретации для исчисления высказываний § § 28, 29), и поэтому проблема полноты для исчисления предикатов не относится к метаматематике. Эти замечания наводят на мысль, что в рассматриваемом случае положение не так просто, как в исчислении высказываний, где мы рассматривали вопрос о полноте и о проблеме разрешимости. Мы вернемся к этим проблемам в одной из дальнейших глав об исчислении предикатов, где будут изложены некоторые результаты частью метаматематического, а частью теоретико-множественного характера ( гл. [19]
Поставим теперь следующую задачу: указать способ, которой позволил бы для любой предикатной формулы установить в конечное число шагов, является эта формула тождественно истинной или нет. [20]
ГЕДЕЛЯ ТЕОРЕМА О ПОЛНОТЕ - утверждение о полноте классического предикатов исчисления: еслн предикатная формула истинна в любой интерпретации, то она выводима в исчислении предикатов. [21]
ГЕДЕЛЯ ТЕОРЕМА О ПОЛНОТЕ - утверждение о полноте классического исчисления предикатов: всякая предикатная формула, истинная на всех моделях, выводима ( по формальным правилам классич. А, невыводимой в Генцена формальной системе без сечения. Имеются также доказательства, основанные на расширениях систем формул до максимальных, а также доказательства, использующие ал-гебраич. Теорема вместе с доказательством обобщается на исчисление с равенством. Геделовское доказательство дает для непротиворечивого множества формул модель, элементами к-рой являются термы. Такие модели составляют исходный пункт во многих исследованиях по метаматематике теории множеств. Другое приложение моделей из термов - теорема Левенхей - м а - С к о л е м а: если счетное множество формул имеет какую-то модель, то оно имеет счетную модель. A) выводима в формальной арифметике; здесь Рг ( А) - арифметич. [22]
Если ввести обозначение - для определения переходов от одной формулы к другой и при этом предикатные формулы. [23]
Затем, рассуждая как при доказательстве теоремы 20, мы можем доказать, что каждая доказуемая предикатная формула всегда-истинна в любой непустой предметной области. Но в случае бесконечной области это рассуждение уже перестает быть финитным. Нефинитный шаг появляется, например, при рассмотрении схемы аксиом 10, где мы различаем два случая, смотря по тому, все ли значения некоторой функции суть t или среди них имеются также f, где теперь появляется бесконечно много значений, подлежащих рассмотрению. Действительно, само понятие всегда-истинности, для случая бесконечной области и формулы, содержащей предикатную букву с п0 приданными переменными, нефинитно. В самом деле, оно требует, чтобы значение некоторой функции было t для всех логических функций от переменных, взятых в качестве значения этой предикатной буквы, а класс таких логических функций несчетен, и его можно представить себе ( следуя обычному пониманию) только в терминах завершенной бесконечности. [24]
Мы определим предикатную формулу с k индивидуумами, или, короче, предикатную k - формулу, пользуясь определением предикатной формулы ( § 31), но с той разницей, что теперь в пункте 1 определения в качестве термов наравне с переменными рассматриваются цифры от 1 до ft; исчисление предикатов с этим понятием формулы мы назовем исчислением предикатов с k индивидуумами, или, короче, k - исчислением предикатов. [25]
Теорема вытекает из двух лемм, соответствующих леммам для теоремы 9, но относящихся теперь к списку постулатов исчисления предикатов, предикатным формулам и fe - тождественности. [26]
Понятия - тождественности и - равенства ( § 36), а также выполнимости и тождественности в данной непустой области, распространяются на предикатные формулы с равенством путем соглашения, состоящего в том, что а 6 принимает в качестве значения t ( f), когда а и b принимают одинаковые ( различные) значения из соответствующей области. [27]
Примером ( р) служит решение проблемы разрешимости, найденное Ле-венгеймом [1915] ( упрощено Сколемом [1919]), а затем независимо Беманом [1922], для случая предикатных формул, содержащих только предикатные буквы с 0 или 1 аргументом. [28]
Следовательно, если бы имелась разрешающая процедура для доказуемости в чистом исчислении предикатов, то имелась бы такая процедура и для доказуемости в S2, состоящая в нахождении предикатной формулы F: э В, соответствующей данной формуле Е из Sa, и в последующем применении разрешающей процедуры для исчисления предикатов к формуле F: D В. Но по теореме 33, если S2 просто непротиворечива, то разрешающей процедуры для доказуемости в S2 не существует. Это рассуждение применимо и к исчислению предикатов с равенством, так как, по теореме 41 ( Ь), доказуемость в системе Робинсона равносильна доказуемости в системе, состоящей из исчисления предикатов с равенством и семью отдельными аксиомами. [29]
Пользуясь теоремами 21 и 37 ( см. теорему 39 § 73), эти результаты можно перенести на случай, когда употребляется как логическое понятие, а аксиомы выражаются посредством предикатных формул с равенством. [30]