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

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

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

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

∃ x Куб( x )

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

∃PP( б )

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

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

∃P ∀ x (Px ↔ (Куб( x ) ∨ Тет( x ))).

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

∀P (∀ x (Px ↔ (Куб( x ) ∨ Тет( x ))) → ¬ ∃ x (Px ∧ Додек( x ))).

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

∀P ((P y ∧ ∀ a ∀ b ((P b ∧ Родитель( a , b )) → P a )) → 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, как или даже как ∃SO. Фрагмент формул определяется двойственно, он называется универсальной логикой второго порядка. Более выразительные фрагменты определяются для любого k > 0 взаимной рекурсией: имеет вид , где — формула, и аналогично, имеет вид , где — формула. (См. аналитическую иерархию для аналогичного построения арифметики второго порядка .)${\displaystyle \Sigma _{0}^{1}}$${\displaystyle \Пи _{0}^{1}}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$${\displaystyle \фи}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \Пи _{1}^{1}}$${\displaystyle \Сигма _{k+1}^{1}}$${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$${\displaystyle \фи}$${\displaystyle \Пи _{k}^{1}}$${\displaystyle \Pi _{k+1}^{1}}$${\displaystyle \forall R_{0}\ldots \forall R_{m}\phi }$${\displaystyle \фи}$${\displaystyle \Сигма _{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) ([ (∃ w ) ( w ∈ A) ∧ (∃ z )(∀ u )( u ∈ A → u ≤ 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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В последние годы ^{[ когда? ]} логика второго порядка сделала что-то вроде восстановления, поддержанное интерпретацией Булосом квантификации второго порядка как множественной квантификации по той же области объектов, что и квантификация первого порядка (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 , то добавление оператора транзитивного замыкания к логике второго порядка не сделает ее более выразительной над конечными структурами.

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

• Эндрюс, Питер (2002). Введение в математическую логику и теорию типов: к истине через доказательство (2-е изд.). Kluwer Academic Publishers.
• Булос, Джордж (1984). «Быть ​​— значит быть значением переменной (или быть некоторыми значениями некоторых переменных)». Журнал философии . 81 (8): 430–50. doi :10.2307/2026308. JSTOR  2026308.. Перепечатано в Boolos, Logic, Logic and Logic , 1998.
• Хенкин, Л. (1950). «Полнота в теории типов». Журнал символической логики . 15 (2): 81–91. doi :10.2307/2266967. JSTOR  2266967. S2CID  36309665.
• Хинман, П. (2005). Основы математической логики . AK Peters. ISBN 1-56881-262-0.
• Патнэм, Хилари (1982). «Пирс-логик». Historia Mathematica . 9 (3): 290–301. doi : 10.1016/0315-0860(82)90123-9 .. Перепечатано в Putnam, Hilary (1990), Реализм с человеческим лицом , Harvard University Press , стр. 252–260.
• WV Quine (1970). Философия логики. Prentice Hall . ISBN 9780674665637.
• Россберг, М. (2004). "Логика первого порядка, логика второго порядка и полнота" (PDF) . В V. Hendricks; et al. (ред.). Пересмотр логики первого порядка . Берлин: Logos-Verlag.
• Шапиро, С. (2000) [1991].Основания без фундаментализма: аргумент в пользу логики второго порядка. Оксфорд: Clarendon Press. ISBN 0-19-825029-0.
• Вяэнянен, Дж. (2001). «Логика второго порядка и основы математики» (PDF) . Бюллетень символической логики . 7 (4): 504–520. CiteSeerX  10.1.1.25.5579 . doi :10.2307/2687796. JSTOR  2687796. S2CID  7465054.

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

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