Cтраница 1
Логика второго порядка является тогда, как вытекает из следствий 18.2 и 18.3 и упр. Более того, предположим, что предложениям второго порядка некоторым разумным образом приписаны геделевы номера. Тогда множество геделевых номеров общезначимых предложений второго порядка не является ( даже) определимым в арифметике. В самом деле, предположим, что V ( y) определяет это множество. [1]
Речь идет о стандартной или настоящей логике второго порядка. В нестандартной логике второго порядка, которую мы не рассматриваем вовсе, определение интерпретации иное: вводятся отдельные области для функциональных и предикатных переменных. Помимо этой главы мы рассматриваем предложения и формулы второго порядка лишь в первой половине гл. [2]
Покажите, что множество геделевых номеров предложений логики второго порядка, эквивалентных предложениям первого порядка, неопределимо в арифметике второго порядка. [3]
В начале главы мы подчеркивали, что в логике второго порядка не изменяются ни определение языка, ни определение ик-терпретации. Языком по-прежнему называется счетное множество нелогических символов, а под интерпретацией мы понимаем то же самое, что понимали все время ( ср. Изменения претерпевают понятия формулы и предложения: большее число выражений теперь считается формулами и предложениями. И описание условий, приводимое в гл. [4]
Мы можем теперь заметить, что теорема Ле венгейма - Сколема в логике второго порядка места не имеет: предложение - - Ах En истинно в любой интерпретации, область которой бесконечна и несчетна ( такие интерпретации существуют, поэтому - Ах En выполнимо. [5]
Этот результат иногда формулируется уводящим до некоторой степени от сути дела образом: логика второго порядка неполна. Несколько менее вводящая в заблуждение формулировка того же рода такова: никакая непротиворечивая формализация логики второго порядка не является полной. Это не логика неполна, неполны предлагаемые нами формализации. [6]
Осталось доказать справедливость ( 2), т.е. показать, что теорема компактности не имеет места для логики второго порядка. [7]
Этот вопрос для произвольной модели 21 чрезвычайно труден, так как из ответа на него вытекают решения некоторых проблем логики второго порядка, которыми мы еще не располагаем. Если вопрос ставится для всего класса моделей 21 языка X, как, например, в теореме Бета и в некоторых наших последующих теоремах этого раздела, то можно получить очень элегантные ответы. [8]
Речь идет о стандартной или настоящей логике второго порядка. В нестандартной логике второго порядка, которую мы не рассматриваем вовсе, определение интерпретации иное: вводятся отдельные области для функциональных и предикатных переменных. Помимо этой главы мы рассматриваем предложения и формулы второго порядка лишь в первой половине гл. [9]
Существует счетное невыполнимое множество предложений, каждое конечное подмножество которого выполнимо; одно из предложений этого множества является предложением второго порядка. Таким образом, теорема о компактности не имеет места в логике второго порядка. [10]
Этот результат иногда формулируется уводящим до некоторой степени от сути дела образом: логика второго порядка неполна. Несколько менее вводящая в заблуждение формулировка того же рода такова: никакая непротиворечивая формализация логики второго порядка не является полной. Это не логика неполна, неполны предлагаемые нами формализации. [11]
Уже сам термин NP-свойство приводит к альтернативному определению: свойство является NP-своисговсш тогда и только тогда, когда оно может быть распознано недетерминированной машиной Тьюринга за полиномиальное время. Другой красивый способ определить эти свойства следующий: это в точности такие свойства конечных графов, которые можно выразить формулами логики второго порядка, содержащими одну свободную переменную второго порядка ( смежность) и произвольное число связанных переменных второго порядка, на которые действуют только кванторы существования. [12]
Построение теории моделей первого порядка служит предпосылкой для развития теорий моделей других типов и таких ее приложений, как нестандартный анализ. В настоящее время развиваются также теории моделей логики с бесконечными формулами, логики с дополнительными кванторами, многозначной логики, многосортной логики, интуиционистской логики, модальной логики, логики второго порядка. [13]
Мы покажем теперь, что ни один из этих результатов не останется верным, если некоторым специальным образом расширить понятие предложения языка и соответственно изменить условия, при выполнении которых предложение считается истинным в интерпретации. Изучение условий, при которых предложения первого и второго порядков истинны, происходит в рамках так называемой логики второго порядка. [14]
Построение теории моделей первого порядка служит предпосылкой для развития теорий моделей других типов и таких ее приложений, как нестандартный анализ. В настоящее время развиваются также теории моделей логики с бесконечными формулами, логики с дополнительными кванторами, многозначной логики, многосортной логики, интуиционистской логики, модальной логики, логики второго порядка. Теория моделей логики второго порядка в значительной мере лежит вне сферы действия современных методов, но потенциально очень важна. [15]