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

Форма логики, позволяющая количественно оценивать предикаты

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

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

Примеры

Граффити в Нойкёльне (Берлин), изображающее простейшее предложение второго порядка, допускающее нетривиальные модели, «∃𝜑𝜑».

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

∃ х Куб( х )

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

∃ПП( б )

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

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

∃P ∀ x (Px ↔ (Куб( x ) ∨ Tet( x ))).

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

∀P (∀ x (Px ↔ (Cube( x ) ∨ Tet( x ))) → ¬ ∃ x (Px ∧ Dodec( x ))).

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

∀P ((P y ∧ ∀ a ∀ b ((P b ∧ Parent(a, b)) → Pa ) ) → 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, например, (,+)) может интерпретировать истинную арифметику второго порядка . ${\displaystyle \mathbb {N} }$

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

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

Семантика

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

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

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

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

Йоуко Вяэнянен (2001) утверждал, что различие между семантикой Хенкина и полной семантикой для логики второго порядка аналогично различию между доказуемостью в ZFC и истинностью в V , поскольку первая подчиняется теоретико-модельным свойствам, таким как теорема Ловенхайма-Скулема и компактность, а последняя обладает явлениями категоричности. Например, «мы не можем осмысленно спрашивать, является ли то, что определено в, реальным . Но если мы реформируем внутри , то мы можем отметить, что реформализованное ... имеет счетные модели и, следовательно, не может быть категоричным». ${\displaystyle V}$ ${\displaystyle \mathrm {ZFC} }$ ${\displaystyle V}$ ${\displaystyle \mathrm {ZFC} }$ ${\displaystyle \mathrm {ZFC} }$ ${\displaystyle \mathrm {ZFC} }$

Выразительная сила

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

(∀ A) ([ (∃ ш ) ( ш € А) ∧ (∃ z )(∀ ты )( ты € А → ты ≤ z ) ]

→ (∃ x )(∀ y )([(∀ w )( w ∈ A → w ≤ x )] ∧ [(∀ u )( u ∈ A → u ⩽ y )] → x ⩽ y ) )

Эта формула является прямой формализацией утверждения «всякое непустое ограниченное множество A имеет наименьшую верхнюю границу ». Можно показать, что любое упорядоченное поле , удовлетворяющее этому свойству, изоморфно полю действительных чисел. С другой стороны, множество предложений первого порядка, действительных в действительных числах, имеет сколь угодно большие модели в силу теоремы о компактности. Таким образом, свойство наименьшей верхней границы не может быть выражено каким-либо набором предложений в логике первого порядка. (Фактически, каждое вещественно-замкнутое поле удовлетворяет тем же предложениям первого порядка в сигнатуре, что и действительные числа.) ${\displaystyle \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 , то добавление оператора транзитивного замыкания к логике второго порядка не сделает ее более выразительной для конечных структур.

Смотрите также

• Философский портал

• Логика первого порядка
• Логика высшего порядка
• Число Левенхайма
• Омега язык
• Пропозициональная логика второго порядка
• Монадическая логика второго порядка

Примечания

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

Рекомендации

• Эндрюс, Питер (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 г.).