Логика второго порядка - Second-order logic

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

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

Примеры

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

∃x Куб (x)

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

∃P P (б)

не является предложением логики первого порядка. Но это законное предложение логики второго порядка.^[2]

В результате логика второго порядка имеет гораздо большую «выразительную силу», чем FOL. Например, в FOL нет способа сказать, что a и b имеют какое-то общее свойство; но в логике второго порядка это будет выражено как

∃P (P (a) ∧ P (b)).

Предположим, мы хотим сказать, что a и b имеют одинаковую форму. Лучшее, что мы могли сделать в FOL, это примерно так:

(Куб (a) ∧ Куб (b)) ∨ (Tet (a) ∧ Tet (b)) ∨ (Dodec (a) ∧ Dodec (b))

Если единственными формами являются куб, тетраэдр и додекаэдр, то для a и b иметь одинаковую форму означает, что они либо оба куба, либо оба тетраэдра, либо оба додекаэдра. Но это предложение FOL, похоже, не означает совсем то же самое, что английское предложение, которое оно переводит - например, оно ничего не говорит о том факте, что это общая форма, которую имеют a и b.^[2]

В логике второго порядка, напротив, мы могли бы добавить предикат Shape, который истинен как раз для свойств, соответствующих предикатам Cube, Tet и Dodec. То есть,

Форма (Куб) ∧ Форма (Тет) ∧ Форма (Додек)

Итак, мы могли написать:

∃P (Форма (P) ∧ P (a) ∧ P (b))

И это произойдет именно тогда, когда a и b будут либо кубами, либо тетраэдрами, либо обоими додекаэдрами. Итак, в логике второго порядка мы можем выразить идею такая же форма с использованием идентификатора и предиката второго порядка Shape; мы можем обойтись без специального предиката SameShape.^[2]

Точно так же мы можем выразить утверждение, что ни один объект не имеет всех форм таким образом, чтобы выявить квантор в каждая форма:

¬∃x ∀P (Форма (P) → P (x))

В FOL блок называется одним из следующих: куб, тетраэдр или додекаэдр:^[3]^:258

¬∃x (Куб (x) ∧ Tet (x) ∧ Dodec (x))

Синтаксис и фрагменты

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

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

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

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

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

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

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

Семантика

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

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

В семантике Хенкина каждый вид переменных второго порядка имеет свой собственный домен для диапазона, который может быть надлежащим подмножеством всех наборов или функций этого типа. Леон Хенкин (1950) определили эту семантику и доказали, что Теорема Гёделя о полноте и теорема компактности, которые выполняются для логики первого порядка, переносятся на логику второго порядка с семантикой Хенкина. Это связано с тем, что семантика Хенкина почти идентична многосортной семантике первого порядка, где добавляются дополнительные виды переменных для имитации новых переменных логики второго порядка. Логика второго порядка с семантикой Хенкина не более выразительна, чем логика первого порядка. Семантика Хенкина обычно используется при изучении арифметика второго порядка.

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

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

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

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

→ (∃ Икс)(∀ у)([(∀ ш)(ш ∈ A → ш ≤ Икс)] ∧ [(∀ ты)(ты ∈ A → ты ≤ у)] → Икс ≤ у))

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

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

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

Дедуктивные системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение к вычислительной сложности

Выразительная сила различных форм логики второго порядка на конечных структурах тесно связана с теория сложности вычислений. Поле описательная сложность изучает вычислительные классы сложности может характеризоваться мощностью логики, необходимой для выражения в них языков (наборов конечных строк). Строка ш = ш₁···ш_п в конечном алфавите А может быть представлена конечной структурой с областью D = {1,...,п}, унарные предикаты п_а для каждого а ∈ Аудовлетворены этими показателями я такой, что ш_я = а, и дополнительные предикаты, которые служат для однозначной идентификации того, какой индекс является каким (обычно берется график функции-преемника на D или отношение порядка <, возможно, с другими арифметическими предикатами). И наоборот, таблица любой конечной структуры может быть закодирована конечной строкой.

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

РЕГ (набор обычные языки ) определима монадическими формулами второго порядка (теорема Бюхи, 1960)
НП есть множество языков, определяемых экзистенциальными формулами второго порядка (Теорема Феджина, 1974).
со-НП - это набор языков, определяемых универсальными формулами второго порядка.
PH - множество языков, определяемых формулами второго порядка.
PSPACE набор языков, определяемых формулами второго порядка с добавлением переходное закрытие оператор.
EXPTIME набор языков, определяемых формулами второго порядка с добавлением наименьшая фиксированная точка оператор.

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

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

Примечания

^ Шапиро (1991) и Хинман (2005) дают полные введения в предмет с полными определениями.
^ ^а ^б ^c ^d Конспект лекций профессора Марка Коэна https://faculty.washington.edu/smcohen/120/SecondOrder.pdf
^ Стэплтон, Г., Хоуз, Дж., & Ли, Дж. М., ред., Диаграммное представление и вывод: 5-я Международная конференция, Диаграммы 2008 (Берлин /Гейдельберг: Springer, 2008), п. 258.
^ Такая система используется без комментариев Хинманом (2005).
^ Это модели, первоначально изученные Хенкиным (1950).
^ Доказательство этого следствия состоит в том, что надежная, полная и эффективная система вывода для стандартной семантики может быть использована для получения рекурсивно перечислимый завершение Арифметика Пеано, которые, как показывает теорема Гёделя, существовать не могут.
^ Манзано, М., Модельная теория, пер. Руй Дж. Г. Б. де Кейруш (Оксфорд: Clarendon Press, 1999), п. xi.

дальнейшее чтение

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

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

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

[3] Стэплтон, Г., Хоуз, Дж., & Ли, Дж. М., ред., Диаграммное представление и вывод: 5-я Международная конференция, Диаграммы 2008 (Берлин /Гейдельберг: Springer, 2008), п. 258.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Математическая логика
Общий	Формальный язык Правило формирования Формальное доказательство Формальная семантика Правильная формула Набор Элемент Учебный класс Классическая логика Аксиома Правило вывода Связь Теорема Логическое следствие Теория типов Символ Синтаксис Теория
Системы	Формальная система Дедуктивная система Аксиоматическая система Системы гильбертового стиля Естественный вычет Последовательное исчисление
Традиционная логика	Предложение Вывод Аргумент Срок действия Силлогизм Площадь оппозиции Диаграмма Венна
Исчисление высказываний и Логическая логика	Логические функции Исчисление высказываний Пропозициональная формула Логические связки Таблицы истинности Многозначная логика
Логика предикатов	Первый заказ Квантификаторы Предикат Второго порядка Монадическое исчисление предикатов
Наивная теория множеств	Набор Пустой набор Элемент Перечисление Расширяемость Конечный набор Бесконечный набор Подмножество Набор мощности Счетный набор Бесчисленное множество Рекурсивный набор Домен Codomain Изображение карта Функция Связь Упорядоченная пара
Теория множеств	Основы математики Теория множеств Цермело – Френкеля Аксиома выбора Общая теория множеств Теория множеств Крипке – Платека Теория множеств фон Неймана – Бернейса – Гёделя. Теория множеств Морса – Келли Теория множеств Тарского – Гротендика
Теория моделей	Модель Интерпретация Нестандартная модель Теория конечных моделей Ценность правды Срок действия
Теория доказательств	Формальное доказательство Дедуктивная система Формальная система Теорема Логическое следствие Правило вывода Синтаксис
Вычислимость теория	Рекурсия Рекурсивный набор Рекурсивно перечислимый набор Проблема решения Тезис Черча – Тьюринга Вычислимая функция Примитивная рекурсивная функция