Логика высшего порядка - Higher-order logic

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

Термин «логика высшего порядка», сокращенно HOL, обычно используется для обозначения логика простых предикатов высшего порядка. Здесь "простой" означает, что основной теория типов это теория простых типов, также называемый простая теория типов (видеть Теория типов ). Леон Чвистек и Фрэнк П. Рэмси предложил это как упрощение сложной и неуклюжей разветвленная теория типов указано в Principia Mathematica к Альфред Норт Уайтхед и Бертран Рассел. Простые типы в настоящее время иногда также означает исключение полиморфный и зависимый типы.[1]

Объем количественной оценки

"Упорядоченная логика" перенаправляется сюда. Для несвязанного члена в линейной логике см. Некоммутативная логика.

Логика первого порядка определяет количественно только переменные, которые варьируются от отдельных лиц; логика второго порядка, кроме того, также дает количественную оценку по множествам; логика третьего порядка также количественно определяет наборы наборов и так далее.

Логика высшего порядка это объединение первого, второго, третьего,…, плогика-го порядка; т.е. логика более высокого порядка допускает количественную оценку множеств, которые вложены произвольно глубоко.

Семантика

Есть две возможные семантики для логики более высокого порядка.

в стандарт или же полная семантика, кванторы для объектов более высокого типа варьируются все возможные объекты этого типа. Например, квантификатор по группам людей варьируется по всей powerset множества лиц. Таким образом, в стандартной семантике после определения набора индивидов этого достаточно, чтобы указать все кванторы. HOL со стандартной семантикой более выразителен, чем логика первого порядка. Например, HOL допускает категоричный аксиоматизации натуральных и действительных чисел, которые невозможны с логикой первого порядка. Однако в результате Курт Гёдель, HOL со стандартной семантикой не допускает эффективного, надежного и полный исчисление доказательств.[2] Теоретико-модельные свойства HOL со стандартной семантикой также более сложны, чем свойства логики первого порядка. Например, Число Левенхайма из логика второго порядка уже больше первого измеримый кардинал, если такой кардинал существует.[3] Число Левенгейма логики первого порядка, напротив, равно ℵ0, наименьший бесконечный кардинал.

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

Примеры и свойства

Логика более высокого порядка включает ответвления Церковь с Простая теория типов[4] и различные формы интуиционистская теория типов. Жерар Юэ показал, что унифицируемость является неразрешимый в теоретический тип аромат логики третьего порядка,[5][6][7] то есть не может быть никакого алгоритма, чтобы решить, имеет ли решение произвольное уравнение между членами третьего порядка (не говоря уже о произвольных членах более высокого порядка).

С точностью до определенного понятия изоморфизма операция powerset определима в логике второго порядка. Используя это наблюдение, Яакко Хинтикка В 1955 году было установлено, что логика второго порядка может моделировать логику более высокого порядка в том смысле, что для каждой формулы логики более высокого порядка можно найти равноправный формула для него в логике второго порядка.[8]

Термин «логика более высокого порядка» предполагается в некотором контексте для обозначения классический логика высшего порядка. Тем не мение, модальный логика высшего порядка также была изучена. По мнению некоторых логиков, Онтологическое доказательство Гёделя лучше всего изучать (с технической точки зрения) в таком контексте.[9]

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

Примечания

  1. ^ Джейкобс, 1999, глава 5
  2. ^ Шапиро 1991, стр. 87.
  3. ^ Менахем Магидор и Йоуко Вяэнянен. "О числах Левенхайма-Сколема-Тарского для расширений логики первого порядка ", Отчет № 15 (2009/2010) Института Миттаг-Леффлера.
  4. ^ Церковь Алонсо, Формулировка простой теории типов, Журнал символической логики 5 (2): 56–68 (1940)
  5. ^ Юэ, Жерар П. (1973). «Неразрешимость объединения в логике третьего порядка». Информация и контроль. 22 (3): 257–267. Дои:10.1016 / с0019-9958 (73) 90301-х.
  6. ^ Юэ, Жерар (сентябрь 1976 г.). Resolution d'Equations dans des Langages d'Ordre 1,2, ... ω (Доктор философии) (на французском языке). Парижский университет VII.
  7. ^ Юэ, Жерар (2002). «Объединение высшего порядка 30 лет спустя» (PDF). In Carreño, V .; Muñoz, C .; Тахар, С. (ред.). Материалы 15-й Международной конференции TPHOL. LNCS. 2410. Springer. С. 3–12.
  8. ^ запись на HOL
  9. ^ Примерка, Мелвин (2002). Типы, Таблицы и Бог Гёделя. Springer Science & Business Media. п. 139. ISBN  978-1-4020-0604-3. Аргумент Гёделя является модальным и, по крайней мере, второстепенным, поскольку в его определении Бога есть явная количественная оценка свойств. [...] [AG96] показал, что можно рассматривать часть аргумента не как второстепенную, а как третью.

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

  • Эндрюс, Питер Б. (2002). Введение в математическую логику и теорию типов: к истине через доказательство, 2-е изд., Kluwer Academic Publishers, ISBN  1-4020-0763-9
  • Стюарт Шапиро, 1991, "Основы без фундаментализма: аргументы в пользу логики второго порядка". Oxford University Press., ISBN  0-19-825029-0
  • Стюарт Шапиро, 2001, "Классическая логика II: логика высшего порядка", в Лу Гобле, изд., Руководство Блэквелла по философской логике. Блэквелл, ISBN  0-631-20693-0
  • Ламбек, Дж. и Скотт, П. Дж., 1986. Введение в высший порядок Категориальная логика, Издательство Кембриджского университета, ISBN  0-521-35653-9
  • Джейкобс, Барт (1999). Категориальная логика и теория типов. Исследования по логике и основам математики 141. Северная Голландия, Эльзевир. ISBN  0-444-50170-3.
  • Бенцмюллер, Кристоф; Миллер, Дейл (2014). «Автоматизация логики высшего порядка». В Габбае, Дов М .; Siekmann, Jörg H .; Вудс, Джон (ред.). Справочник по истории логики, том 9: Вычислительная логика. Эльзевир. ISBN  978-0-08-093067-1.

внешняя ссылка