Логика второго порядка

В логике и математике логика второго порядка является расширением логики первого порядка , которая сама является расширением логики высказываний . ^[1] Логика второго порядка, в свою очередь, расширяется логикой высшего порядка и теорией типов .

Логика первого порядка дает количественную оценку только переменным, которые варьируются в пределах индивидуумов (элементы области дискурса ); логика второго порядка, кроме того, количественно оценивает отношения . Например, предложение второго порядка $\forall P\,\forall x(Px\lor \neg Px)$ говорит, что для каждой формулы P и каждого отдельного x либо Px истинно, либо нет ( Px ) истинно (это закон исключенного третьего ). Логика второго порядка также включает количественную оценку множеств , функций и других переменных (см. раздел ниже ). Логика как первого, так и второго порядка использует идею области дискурса (часто называемой просто «областью» или «вселенной»). Домен представляет собой набор, в котором отдельные элементы могут быть оценены количественно.

Примеры [ править ]

Логика первого порядка может оценивать индивидов, но не свойства. То есть мы можем взять атомарное предложение , такое как Cube( b ), и получить квантифицированное предложение, заменив имя переменной и присоединив квантор: ^[2]

\exists х Куб(х)

Однако мы не можем сделать то же самое с предикатом. То есть следующее выражение:

\existsПП(б)

не является предложением логики первого порядка, но это законное предложение логики второго порядка. Здесь P — переменная-предикат и семантически представляет собой набор индивидов. ^[2]

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

\existsP \forall x (Px \leftrightarrow (Куб(x) \lor Tet(x))).

Затем мы можем утверждать свойства этого набора. Например, следующее говорит о том, что множество всех кубов и тетраэдров не содержит додекаэдров:

\forallP (\forall x (Px \leftrightarrow (Cube(x) \lor Tet(x))) \to \neg \exists x (Px \land Dodec(x))).

Количественная оценка второго порядка особенно полезна, поскольку она дает возможность выразить достижимости свойства . Например, если Parent( x , y ) обозначает, что является родителем y , то логика первого порядка не может выразить свойство, что x является предком y x . В логике второго порядка мы можем выразить это, сказав, что каждое множество людей, содержащее y и замкнутое по отношению Parent, содержит x :

\forallP ((P y \land \forall a \forall b ((P b \land Parent(a, b)) \to Pa)) \to P x).

Примечательно, что, хотя у нас есть переменные для предикатов в логике второго порядка, у нас нет переменных для свойств предикатов. Мы не можем, например, сказать, что существует свойство Shape( P ), которое верно для предикатов P Cube, Tet и Dodec. Для этого потребуется логика третьего порядка . ^[3]

Синтаксис и фрагменты [ править ]

Синтаксис логики второго порядка определяет, какие выражения являются правильно составленными формулами . В дополнение к синтаксису логики первого порядка , логика второго порядка включает множество новых видов (иногда называемых типами ) переменных. Это:

Своего рода переменные, которые варьируются в зависимости от множества людей. Если S — переменная такого типа, а t — член первого порядка, то выражение t ∈ S (также пишется как S ( t ) или St для сохранения круглых скобок) является атомарной формулой . Наборы индивидуумов также можно рассматривать как унарные отношения в области.
Для каждого натурального числа k существует своего рода переменная, которая распространяется на все k -арные отношения между индивидами. Если R является такой k -арной переменной отношения и t ₁ ,..., t _k являются членами первого порядка, то выражение R ( t ₁ ,..., t _k ) является атомарной формулой.
Для каждого натурального числа k существует своего рода переменные, которые охватывают все функции, принимающие k элементов области определения и возвращающие один элемент области определения. Если f является такой k -арной функциональной переменной и t ₁ ,..., t _k являются членами первого порядка, то выражение f ( t ₁ ,..., t _k ) является термином первого порядка.

Каждая из только что определенных переменных может быть универсальна и/или экзистенциально определена количественно для построения формул. Таким образом, существует множество видов кванторов, по два для каждого вида переменных. Предложение в логике второго порядка, как и в логике первого порядка, представляет собой правильно построенную формулу без свободных переменных (любого рода).

В приведенном выше определении можно отказаться от введения функциональных переменных (и некоторые авторы это делают), поскольку n -арная функциональная переменная может быть представлена переменной отношения арности n +1 и соответствующей формулой уникальности " результат" в аргументе n +1 отношения. (Шапиро 2000, стр. 63)

Монадическая логика второго порядка (MSO) — это ограничение логики второго порядка, в котором допускается только количественная оценка унарных отношений (т. е. множеств). Таким образом, количественная оценка функций из-за эквивалентности описанным выше отношениям также не допускается. Логику второго порядка без этих ограничений иногда называют полной логикой второго порядка, чтобы отличить ее от монадической версии. Монадическая логика второго порядка особенно используется в контексте теоремы Курселя , алгоритмической мета-теоремы в теории графов . Теория MSO полного бесконечного двоичного дерева ( S2S ) разрешима. Напротив, полная логика второго порядка для любого бесконечного множества (или логика MSO, например ( $\mathbb {N}$ ,+)) может интерпретировать истинную арифметику второго порядка .

Как и в логике первого порядка, логика второго порядка может включать в себя нелогические символы определенного языка второго порядка. Однако они ограничены тем, что все образуемые ими термины должны быть либо терминами первого порядка (которые могут быть заменены на переменную первого порядка), либо терминами второго порядка (которые могут быть заменены на переменную второго порядка соответствующий сорт).

Говорят, что формула в логике второго порядка имеет формулу первого порядка (и иногда обозначается $\Sigma _{0}^{1}$ или $\Pi _{0}^{1}$ ), если его кванторы (которые могут быть универсальными или экзистенциальными) распространяются только на переменные первого порядка, хотя у него могут быть свободные переменные второго порядка. А $\Sigma _{1}^{1}$ Формула (экзистенциального второго порядка) - это формула, дополнительно имеющая некоторые кванторы существования над переменными второго порядка, т.е. $\exists R_{0}\ldots \exists R_{m}\phi$ , где $\phi$ является формулой первого порядка. Фрагмент логики второго порядка, состоящий только из экзистенциальных формул второго порядка, называется экзистенциальной логикой второго порядка и сокращенно ЭСО, т.е. $\Sigma _{1}^{1}$ или даже как ∃SO. Фрагмент $\Pi _{1}^{1}$ формулы определяется двойственно, ее называют универсальной логикой второго порядка. Более выразительные фрагменты определяются для любого k > 0 путем взаимной рекурсии: $\Sigma _{k+1}^{1}$ имеет форму $\exists R_{0}\ldots \exists R_{m}\phi$ , где $\phi$ это $\Pi _{k}^{1}$ формула и тому подобное, $\Pi _{k+1}^{1}$ имеет форму $\forall R_{0}\ldots \forall R_{m}\phi$ , где $\phi$ это $\Sigma _{k}^{1}$ формула. (См. в аналитической иерархии аналогичную конструкцию арифметики второго порядка .)

Семантика [ править ]

Семантика логики второго порядка устанавливает значение каждого предложения. В отличие от логики первого порядка, которая имеет только одну стандартную семантику, для логики второго порядка обычно используются две разные семантики: стандартная семантика и семантика Хенкина . В каждой из этих семантик интерпретации кванторов первого порядка и логических связок такие же, как и в логике первого порядка. В двух типах семантики различаются только диапазоны кванторов над переменными второго порядка (Väänänen 2001) .

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

Леон Хенкин (1950) определил альтернативный вид семантики для теорий второго и высшего порядка, в котором значение областей высшего порядка частично определяется явной аксиоматизацией, опирающейся на теорию типов , свойств множеств. или функции простираются выше. Семантика Хенкина — это своего рода многосортная семантика первого порядка, в которой существует класс моделей аксиом, а не семантика, привязанная только к стандартной модели, как в стандартной семантике. Модель в семантике Хенкина предоставит набор множеств или набор функций в качестве интерпретации доменов более высокого порядка, которые могут быть подмножеством всех множеств или функций такого рода. В своей аксиоматизации Хенкин доказал, что теорема Гёделя о полноте и теорема о компактности , которые справедливы для логики первого порядка, переносятся на логику второго порядка с семантикой Хенкина. Поскольку теоремы Скулема-Лёвенхайма справедливы и для семантики Хенкина, теорема Линдстрема подразумевает, что модели Хенкина являются просто замаскированными моделями первого порядка. . ^[4]

Для таких теорий, как арифметика второго порядка, существование нестандартных интерпретаций областей высшего порядка является не просто недостатком конкретной аксиоматизации, выведенной из теории типов, которую использовал Хенкин, но и необходимым следствием теоремы Гёделя о неполноте : аксиом Хенкина. не могут быть дополнены дальше, чтобы гарантировать, что стандартная интерпретация является единственно возможной моделью. Семантика Хенкина обычно используется при изучении арифметики второго порядка .

Йоуко Вяэнянен ( 2001 ) утверждал, что выбор между моделями Хенкина и полными моделями для логики второго порядка аналогичен выбору между ZFC и V в качестве основы для теории множеств: «Как и в случае с логикой второго порядка, мы на самом деле не можем выбирать, будем ли мы аксиоматизировать математику, используя V или ZFC. Результат один и тот же в обоих случаях, поскольку ZFC на данный момент является лучшей попыткой использовать V в качестве аксиоматизации математики».

Выразительная сила [ править ]

Логика второго порядка более выразительна, чем логика первого порядка. Например, если область определения представляет собой набор всех действительных чисел , можно утверждать в логике первого порядка существование аддитивного обратного к каждому действительному числу, записывая ∀ x ∃ y ( x + y = 0), но нужно второе- логика порядка для утверждения свойства наименьшей верхней границы для наборов действительных чисел, которое гласит, что каждый ограниченный, непустой набор действительных чисел имеет верхнюю грань . Если домен представляет собой набор всех действительных чисел, следующее предложение второго порядка (разбитое на две строки) выражает свойство наименьшей верхней границы:

(\forall А) ([html.skin-theme-clientpref-night .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}} (\exists ш) (ш \in А) \land (\exists z)(\forall ты)(ты \in А \to ты \leq z)]

\to (\exists x)(\forall y)([(\forall w)(w \in A \to w \leq x)] \land [(\forall u)(u \in A \to u ⩽ y)] \to x ⩽ y))

Эта формула представляет собой прямую формализацию «каждого непустой , ограниченное множество A имеет наименьшую верхнюю границу . Можно показать, что любое упорядоченное поле , удовлетворяющее этому свойству, изоморфно полю действительных чисел. С другой стороны, множество предложений первого порядка, действительных в действительных числах, имеет сколь угодно большие модели из-за Теорема о компактности. Таким образом, свойство наименьшей верхней границы не может быть выражено каким-либо набором предложений в логике первого порядка (на самом деле, каждое вещественно-замкнутое поле удовлетворяет одним и тем же предложениям первого порядка в сигнатуре. $\langle +,\cdot ,\leq \rangle$ как реальные цифры.)

В логике второго порядка можно написать формальные предложения, в которых говорится: «Область измерения конечна » или «Область имеет счетную мощность ». Чтобы сказать, что область определения конечна, используйте предложение, в котором говорится, что каждая сюръективная функция из области определения в себя инъективна . Чтобы сказать, что область имеет счетную мощность, используйте предложение, в котором говорится, что существует биекция между любыми двумя бесконечными подмножествами области. следует Из теоремы о компактности и восходящей теоремы Левенгейма–Скулема , что в логике первого порядка невозможно охарактеризовать конечность или счетность соответственно.

Определенные фрагменты логики второго порядка, такие как ESO, также более выразительны, чем логика первого порядка, хотя они строго менее выразительны, чем полная логика второго порядка. ESO также пользуется эквивалентностью перевода с некоторыми расширениями логики первого порядка, которые допускают нелинейное упорядочение зависимостей кванторов, например, логика первого порядка, расширенная с помощью кванторов Хенкина , Хинтикки и Санду дружественная к независимости логика Вяэнянена и логика зависимостей .

Дедуктивные системы [ править ]

Дедуктивная система логики — это набор правил вывода и логических аксиом, которые определяют, какие последовательности формул представляют собой действительные доказательства. Для логики второго порядка можно использовать несколько дедуктивных систем, хотя ни одна из них не может быть полной для стандартной семантики (см. Ниже). Каждая из этих систем надежна , а это означает, что любое предложение, которое они могут использовать для доказательства, логически обосновано в соответствующей семантике.

Самая слабая дедуктивная система, которую можно использовать, состоит из стандартной дедуктивной системы для логики первого порядка (например, естественной дедукции ), дополненной правилами замены для терминов второго порядка. ^[5] Эта дедуктивная система обычно используется при изучении арифметики второго порядка .

Дедуктивные системы, рассмотренные Шапиро (1991) и Хенкиным (1950), добавляют к расширенной дедуктивной схеме первого порядка как аксиомы понимания, так и аксиомы выбора. Эти аксиомы верны для стандартной семантики второго порядка. Они подходят для семантики Хенкина, ограниченной моделями Хенкина, удовлетворяющими аксиомам понимания и выбора. ^[6]

Несводимость к логике первого порядка [ править ]

Можно попытаться свести теорию действительных чисел второго порядка с полной семантикой второго порядка к теории первого порядка следующим образом. Сначала расширите домен от набора всех действительных чисел до домена с двумя сортировками, при этом второй сорт будет содержать все наборы действительных чисел. Добавьте в язык новый бинарный предикат: отношение принадлежности. Затем предложения, которые были вторым порядком, становятся первыми, а кванторы, которые раньше были вторым порядком, вместо этого располагаются в пределах второго порядка. Это сокращение можно попытаться осуществить в односортной теории, добавив унарные предикаты, которые сообщают, является ли элемент числом или набором, и приняв в качестве области определения объединение набора действительных чисел и степенного набора действительных чисел.

Но обратите внимание, что было заявлено, что домен включает в себя все наборы действительных чисел. Это требование не может быть сведено к предложению первого порядка, как показывает теорема Левенхайма – Скулема . Из этой теоремы следует, что существует некоторое счетное бесконечное подмножество действительных чисел, члены которого мы будем называть внутренними числами , и некоторая счетная бесконечная совокупность множеств внутренних чисел, члены которого мы будем называть «внутренними множествами», такие, что область определения, состоящая из внутренние числа и внутренние множества удовлетворяют точно тем же предложениям первого порядка, которым удовлетворяет область действительных чисел и наборы действительных чисел. В частности, он удовлетворяет своего рода аксиоме наименьшей верхней границы, которая, по сути, гласит:

Каждое непустое внутреннее множество, имеющее внутреннюю верхнюю границу, имеет наименьшую внутреннюю верхнюю границу.

Счетность набора всех внутренних чисел (в сочетании с тем фактом, что они образуют плотно упорядоченный набор) означает, что этот набор не удовлетворяет полной аксиоме наименьшей верхней границы. Счетность множества всех внутренних множеств подразумевает, что оно не является множеством всех подмножеств множества всех внутренних чисел (поскольку из теоремы Кантора следует, что множество всех подмножеств счетного бесконечного множества является несчетным бесконечным множеством). Эта конструкция тесно связана с парадоксом Скулема .

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

Есть и более крайние примеры, показывающие, что логика второго порядка со стандартной семантикой более выразительна, чем логика первого порядка. Существует конечная теория второго порядка, единственной моделью которой являются действительные числа, если верна гипотеза континуума , и которая не имеет модели, если гипотеза континуума не верна (см. Шапиро 2000, стр. 105). Эта теория состоит из конечной теории, характеризующей действительные числа как полное архимедово упорядоченное поле, а также аксиомы, утверждающей, что область определения имеет первую несчетную мощность. Этот пример показывает, что вопрос о том, является ли предложение в логике второго порядка непротиворечивым, чрезвычайно тонок.

Дополнительные ограничения логики второго порядка описаны в следующем разделе.

Металогические результаты

Следствием теоремы Гёделя о неполноте является то, что не существует дедуктивной системы (то есть понятия доказуемости ) для формул второго порядка, которая одновременно удовлетворяет этим трем желаемым атрибутам: ^[7]

( Разумность ) Каждое доказуемое предложение второго порядка является универсально действительным, т. е. истинным во всех областях в соответствии со стандартной семантикой.
( Полнота ) Любая универсально действующая формула второго порядка при стандартной семантике доказуема.
( Эффективность ) Существует алгоритм проверки доказательств , который может правильно решить, является ли данная последовательность символов доказательством или нет.

Это следствие иногда выражают, говоря, что логика второго порядка не допускает полной теории доказательства . В этом отношении логика второго порядка со стандартной семантикой отличается от логики первого порядка; Куайн (1970, стр. 90–91 ) указал на отсутствие полной системы доказательств как на причину считать логику второго порядка не логикой , собственно говоря.

Как упоминалось выше, Хенкин доказал, что стандартная дедуктивная система для логики первого порядка является надежной, полной и эффективной для логики второго порядка с семантикой Хенкина , а дедуктивная система с принципами понимания и выбора является надежной, полной и эффективной для Хенкина. семантики с использованием только моделей, удовлетворяющих этим принципам.

и Теорема о компактности теорема Левенхайма – Скулема не справедливы для полных моделей логики второго порядка. Однако они справедливы для моделей Henkin. ^[8]^{: xi}

спорная ценность История и

Логика предикатов была представлена математическому сообществу К.С. Пирсом , который ввёл термин « логика второго порядка» и чьи обозначения наиболее похожи на современную форму (Putnam 1982). Однако сегодня большинство изучающих логику более знакомы с работами Фреге , который опубликовал свою работу за несколько лет до Пирса, но чьи работы оставались менее известными до тех пор, пока Бертран Рассел и Альфред Норт Уайтхед не прославили их. Фреге использовал разные переменные, чтобы отличить количественную оценку объектов от количественной оценки свойств и множеств; но он не считал себя занимающимся двумя разными видами логики. После открытия парадокса Рассела стало понятно, что с его системой что-то не так. В конце концов логики обнаружили, что ограничение логики Фреге различными способами — до того, что сейчас называется логикой первого порядка — устранило эту проблему: множества и свойства не могут быть определены количественно только с помощью логики первого порядка. К этому времени восходит ныне стандартная иерархия логических порядков.

Было обнаружено, что теорию множеств можно сформулировать как аксиоматизированную систему в аппарате логики первого порядка (ценой нескольких видов полноты , но не так плохо, как парадокс Рассела), и это было сделано (см. множество Цермело–Френкеля). теория ), поскольку множества жизненно важны для математики . Арифметика , мереология и множество других мощных логических теорий могли быть сформулированы аксиоматически, не обращаясь к какому-либо логическому аппарату, кроме количественной оценки первого порядка, и это, наряду с Гёделя и Скулема приверженностью логике первого порядка, привело к общей теории. снижение работы во втором (или любом более высоком) порядке логики. ^{[ нужна цитата ]}

Это неприятие активно продвигалось некоторыми логиками, в первую очередь У. В. Куайном . Куайн выдвинул точку зрения ^{[ нужна цитата ]}что в предложениях языка предикатов, таких как Fx , « x » следует рассматривать как переменную или имя, обозначающее объект, и, следовательно, его можно оценить количественно, как в «Для всех вещей бывает так, что...». но букву « F » следует рассматривать как сокращение неполного предложения, а не как имя объекта (даже абстрактного объекта, такого как свойство). Например, это может означать «... это собака». Но нет смысла думать, что мы можем дать количественную оценку чему-то подобному. (Такая позиция вполне согласуется с собственными рассуждениями Фреге о различении понятия и объекта ). Таким образом, использовать предикат в качестве переменной — значит занять место имени, которое должны занимать только отдельные переменные. Это рассуждение было отвергнуто Джорджем Булосом . ^{[ нужна цитата ]}

В последние годы ^{[ когда? ]}логика второго порядка в некотором роде восстановилась, чему способствовала интерпретация Булосом квантификации второго порядка как множественной квантификации той же области объектов, что и квантификация первого порядка (Boolos 1984). Булос, кроме того, указывает на заявленную непервую упорядочиваемость таких предложений, как «Некоторые критики восхищаются только друг другом» и «Некоторые из людей Фианкетто вошли на склад без сопровождения кого-либо еще», что, по его мнению, может быть выражено только с помощью предложений второго порядка. количественная оценка. Однако обобщенная квантификация и частично упорядоченная (или ветвящаяся) квантификация могут быть достаточны и для выражения определенного класса предложений, предположительно не упорядочиваемых в первом порядке, и они не апеллируют к квантификации второго порядка.

Связь сложностью с вычислительной

Выразительная сила различных форм логики второго порядка на конечных структурах тесно связана с теорией сложности вычислений . Область исследований описательной сложности вычислительной сложности которой , классы можно охарактеризовать мощностью логики, необходимой для выражения в них языков (наборов конечных строк). Строка w = w ₁ ··· w _n в конечном алфавите A может быть представлена конечной структурой с областью определения D = {1,..., n }, унарными предикатами P _a для каждого a ∈ A , которым удовлетворяют те индексы i такие, что w _i = a , и дополнительные предикаты, которые служат для однозначной идентификации того, какой индекс какой (обычно берется график функции-преемника на D или отношение порядка <, возможно, с другими арифметическими предикатами). И наоборот, таблицы Кэли любой конечной структуры (по конечной сигнатуре ) могут быть закодированы конечной строкой.

Это отождествление приводит к следующим характеристикам вариантов логики второго порядка над конечными структурами:

REG ( регулярные языки ) — это набор языков, определяемых монадическими формулами второго порядка ( теорема Бючи-Эльгота-Трахтенброта , 1960 г.).
NP — это набор языков, определяемых экзистенциальными формулами второго порядка ( теорема Феджина , 1974).
co-NP — это множество языков, определяемых универсальными формулами второго порядка.
PH — множество языков, определяемых формулами второго порядка.
PSPACE — это набор языков, определяемых формулами второго порядка с добавленным оператором транзитивного замыкания .
EXPTIME — это набор языков, определяемых формулами второго порядка с добавленным оператором наименьшей фиксированной точки .

Отношения между этими классами напрямую влияют на относительную выразительность логики над конечными структурами; например, если PH = PSPACE , то добавление оператора транзитивного замыкания к логике второго порядка не сделает ее более выразительной для конечных структур.

См. также [ править ]

Примечания [ править ]

^ Шапиро (1991) и Хинман (2005) дают полное введение в предмет с полными определениями.
^ Перейти обратно: ^а ^б Конспекты лекций профессора Марка Коэна https://faculty.washington.edu/smcohen/120/SecondOrder.pdf
^ Вяэнянен, Йоуко (2021), «Логика второго и высшего порядка» , в Залте, Эдвард Н. (редактор), Стэнфордская энциклопедия философии (изд. осенью 2021 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено в 2022 г. -05-03
^ * Мендельсон, Эллиот (2009). Введение в математическую логику (твердый переплет). Дискретная математика и ее приложения (5-е изд.). Бока-Ратон: Чепмен и Холл/CRC. п. 387. ИСБН 978-1-58488-876-5 .
^ Такая система используется без комментариев Хинманом (2005).
^ Это модели, первоначально изученные Хенкиным (1950).
^ Доказательством этого следствия является то, что надежная, полная и эффективная система вывода для стандартной семантики может использоваться для создания рекурсивно перечислимого завершения арифметики Пеано , которая, как показывает теорема Гёделя, не может существовать.
^ Мансано, М. , Теория моделей , пер. Руи Дж.Г.Б. де Кейроз ( Оксфорд : Clarendon Press , 1999), стр. хи .

Ссылки [ править ]

Эндрюс, Питер (2002). Введение в математическую логику и теорию типов: к истине через доказательство (2-е изд.). Академическое издательство Клувер.
Булос, Джордж (1984). «Быть — значит быть значением переменной (или быть некоторыми значениями некоторых переменных)». Журнал философии . 81 (8): 430–50. дои : 10.2307/2026308 . JSTOR 2026308 . . Перепечатано в Boolos, Logic, Logic and Logic , 1998.
Хенкин, Л. (1950). «Полнота в теории типов». Журнал символической логики . 15 (2): 81–91. дои : 10.2307/2266967 . JSTOR 2266967 . S2CID 36309665 .
Хинман, П. (2005). Основы математической логики . АК Петерс. ISBN 1-56881-262-0 .
Патнэм, Хилари (1982). «Пирс-логик» . История Математики . 9 (3): 290–301. дои : 10.1016/0315-0860(82)90123-9 . . Перепечатано в Патнэме, Хилари (1990), Реализм с человеческим лицом , издательство Гарвардского университета , стр. 252–260 .
В. В. Куайн (1970). Философия логики . Прентис Холл . ISBN 9780674665637 .
Россберг, М. (2004). «Логика первого порядка, логика второго порядка и полнота» (PDF) . В В. Хендриксе; и другие. (ред.). Еще раз о логике первого порядка . Берлин: Логос-Верлаг.
Шапиро, С. (2000) [1991]. Основания без фундаментализма: аргументы в пользу логики второго порядка . Оксфорд: Кларендон Пресс. ISBN 0-19-825029-0 .
Вяэнянен, Дж. (2001). «Логика второго порядка и основы математики» (PDF) . Бюллетень символической логики . 7 (4): 504–520. CiteSeerX 10.1.1.25.5579 . дои : 10.2307/2687796 . JSTOR 2687796 . S2CID 7465054 .

Дальнейшее чтение [ править ]

Градель, Эрих; Колайтис, Фокион Г.; Либкин Леонид ; Мартин, Маркс; Спенсер, Джоэл ; Варди, Моисей Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 978-3-540-00428-8 . Збл 1133.03001 .

Вяэнянен, Йоуко. Эдвард Н. Залта (ред.). Логика второго и высшего порядка . Стэнфордская энциклопедия философии (выпуск осенью 2021 г.).

[1] Шапиро (1991) и Хинман (2005) дают полное введение в предмет с полными определениями.

[mcohen-2] Перейти обратно: ^а ^б Конспекты лекций профессора Марка Коэна https://faculty.washington.edu/smcohen/120/SecondOrder.pdf

[3] Вяэнянен, Йоуко (2021), «Логика второго и высшего порядка» , в Залте, Эдвард Н. (редактор), Стэнфордская энциклопедия философии (изд. осенью 2021 г.), Лаборатория метафизических исследований, Стэнфордский университет , получено в 2022 г. -05-03

[4] * Мендельсон, Эллиот (2009). Введение в математическую логику (твердый переплет). Дискретная математика и ее приложения (5-е изд.). Бока-Ратон: Чепмен и Холл/CRC. п. 387. ИСБН 978-1-58488-876-5 .

[5] Такая система используется без комментариев Хинманом (2005).

[6] Это модели, первоначально изученные Хенкиным (1950).

[7] Доказательством этого следствия является то, что надежная, полная и эффективная система вывода для стандартной семантики может использоваться для создания рекурсивно перечислимого завершения арифметики Пеано , которая, как показывает теорема Гёделя, не может существовать.

[8] Мансано, М. , Теория моделей , пер. Руи Дж.Г.Б. де Кейроз ( Оксфорд : Clarendon Press , 1999), стр. хи .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]