Логика предикатного функтора - Predicate functor logic

В математическая логика, логика функтора предиката (ПФЛ) - один из нескольких способов выразить логика первого порядка (также известный как логика предикатов ) чисто алгебраическими средствами, т. е. без количественные переменные. PFL использует небольшое количество алгебраических устройств, называемых предикатные функторы (или же модификаторы предикатов)^[1] которые действуют на условиях уступки. PFL - это в основном изобретение логик и философ Уиллард Куайн.

Мотивация

Источником этого раздела, а также большей части этой статьи является Quine (1976). Куайн предложил PFL как способ алгебраизации логика первого порядка аналогично тому, как Булева алгебра алгебраизирует логика высказываний. Он разработал PFL, чтобы обладать выразительной силой логика первого порядка с личность. Следовательно метаматематика PFL - это в точности логики первого порядка без интерпретируемых предикатных букв: обе логики звук, полный, и неразрешимый. Большинство работ Куайна по логике и математике, опубликованных за последние 30 лет его жизни, так или иначе затрагивали PFL.^{[нужна цитата ]}

Куайн взял «функтор» из сочинений своего друга. Рудольф Карнап, первым применившим его в философия и математическая логика, и определил его следующим образом:

"Слово функтор, грамматический по важности, но логичный по среде обитания ... - это знак, который присоединяется к одному или нескольким выражениям данного грамматического вида (ов), чтобы произвести выражение данного грамматического типа »(Quine 1982: 129)

Другие способы алгебраизации, кроме PFL логика первого порядка включают:

• Цилиндрическая алгебра к Альфред Тарский и его американские ученики. Упрощенная цилиндрическая алгебра, предложенная Бернейсом (1959), привела Куайна к написанию статьи, в которой впервые используется фраза «предикатный функтор»;
• В полиадическая алгебра из Пол Халмос. В силу своих экономичных примитивов и аксиом эта алгебра больше всего напоминает PFL;
• Алгебра отношений алгебраизирует фрагмент логика первого порядка состоящий из формул, не имеющих атомарной формулы, лежащих в области более чем трех кванторы. Однако этого фрагмента достаточно для Арифметика Пеано и аксиоматическая теория множеств ZFC; следовательно, алгебра отношений, в отличие от PFL, является неполный. Большая часть работ по алгебре отношений примерно с 1920 года принадлежит Тарскому и его американским ученикам. Сила алгебры отношений не проявилась до тех пор, пока не вышла монография Tarski and Givant (1987), опубликованная после трех важных статей, касающихся PFL, а именно: Bacon (1985), Kuhn (1983) и Quine (1976);
• Комбинаторная логика опирается на комбинаторы, функции высшего порядка чей домен является другим комбинатором или функцией, и чья классифицировать еще один комбинатор. Следовательно комбинаторная логика выходит за рамки логики первого порядка, обладая выразительной силой теория множеств, что делает комбинаторную логику уязвимой для парадоксы. С другой стороны, функтор предиката просто отображает предикаты (также называемые термины ) в предикаты.

PFL, пожалуй, самый простой из этих формализмов, но также тот, о котором написано меньше всего.

Куайн всю жизнь увлекался комбинаторная логика о чем свидетельствует его введение к переводу в Ван Хейенорте (1967) статьи русского логика Моисей Шёнфинкель основание комбинаторной логики. Когда Куайн всерьез начал работать над PFL в 1959 году, комбинаторная логика обычно считалась неудачной по следующим причинам:

• До того как Дана Скотт начал писать на теория моделей комбинаторной логики в конце 1960-х, почти только Хаскелл Карри, его ученики и Роберт Фейс в Бельгии работали по этой логике;
• Удовлетворительные аксиоматические формулировки комбинаторной логики появлялись медленно. В 1930-х годах некоторые формулировки комбинаторной логики оказались непоследовательный. Карри также обнаружил Карри парадокс, свойственные комбинаторной логике;
• В лямбда-исчисление, с такой же выразительной силой, как комбинаторная логика, рассматривался как высший формализм.

Формализация Куна

ПФЛ синтаксис, примитивы и аксиомы, описанные в этом разделе, в основном Стивен Кун s (1983). В семантика из функторов принадлежат Куайну (1982). Остальная часть этой статьи включает некоторую терминологию из Бэкона (1985).

Синтаксис

An атомарный термин латинская буква верхнего регистра, я и S исключение, за которым следует числовой надстрочный индекс назвал его степень, или конкатенированными переменными нижнего регистра, вместе известными как список аргументов. Степень термина передает ту же информацию, что и количество переменных, следующих за предикатной буквой. Атомарный член степени 0 обозначает Логическая переменная или значение истины. Степень я всегда равно 2 и поэтому не указывается.

"Комбинаторные" (слово Куайна) предикатные функторы, монадические и свойственные PFL, являются Инв., inv, ∃, +, и п. Термин является либо атомарным, либо построен по следующему рекурсивному правилу. Если τ - терм, то Инв.τ, invτ, ∃τ, +τ, и пτ - члены. Функтор с надстрочным индексом п, п а натуральное число > 1, обозначает п последовательные применения (итерации) этого функтора.

Формула - это либо термин, либо определяется рекурсивным правилом: если α и β являются формулами, то αβ и ~ (α) также являются формулами. Следовательно, «~» - еще один монадический функтор, а конкатенация - единственный диадический предикатный функтор. Куайн назвал эти функторы «алетическими». Естественная интерпретация "~" отрицание; это конкатенация - это любое соединительный что в сочетании с отрицанием образует функционально полный набор связок. Предпочтительный функционально полный комплект Куайна был соединение и отрицание. Таким образом, сцепленные термины считаются соединенными. Обозначение + Бэкона (1985); все остальные обозначения принадлежат Куайну (1976; 1982). Алетиновая часть PFL идентична Схема логических терминов Куайна (1982).

Как хорошо известно, два алетических функтора можно заменить одним диадическим функтором со следующим синтаксис и семантика: если α и β - формулы, то (αβ) - формула, семантика которой «не (α и / или β)» (см. NAND и НИ ).

Аксиомы и семантика

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

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

Семантика Куайна (1982) для каждого функтора предиката формулируется ниже в терминах абстракция (обозначение построителя множеств), за которым следует либо соответствующая аксиома из Kuhn (1983), либо определение из Quine (1976). Обозначение ${displaystyle {x_ {1} ... x_ {n}: Fx_ {1} ... x_ {n}}}$ обозначает набор n-кортежи удовлетворяющий атомарной формуле ${displaystyle Fx_ {1} ... x_ {n}.}$

• Личность, я, определяется как:

${displaystyle IFx_ {1} x_ {2} ... x_ {n} leftrightarrow Fx_ {1} x_ {1} ... x_ {n} leftrightarrow Fx_ {2} x_ {2} ... x_ {n}. }$

Идентичность рефлексивный (Ixx), симметричный (Икси→Iyx), переходный ( (Икси∧Ииз) → Ixz) и подчиняется свойству подстановки:

${displaystyle (Fx_ {1} ... x_ {n} land Ix_ {1} y) ightarrow Fyx_ {2} ... x_ {n}.}$

• Прокладка, +, добавляет переменную слева от любого списка аргументов.

${displaystyle + F ^ {n} = _ {def} {x_ {0} x_ {1} ... x_ {n}: F ^ {n} x_ {1} ... x_ {n}}.}$

${displaystyle + Fx_ {1} ... x_ {n} leftrightarrow Fx_ {2} ... x_ {n}.}$

• Обрезка, ∃, стирает крайнюю левую переменную в любом списке аргументов.

${displaystyle exists F ^ {n} = _ {def} {x_ {2} ... x_ {n}: exists x_ {1} F ^ {n} x_ {1} ... x_ {n}}.}$

${displaystyle Fx_ {1} ... x_ {n} ightarrow существует Fx_ {2} ... x_ {n}.}$

Обрезка включает два полезных определенных функтора:

• Отражение, S:

${displaystyle SF ^ {n} = _ {def} {x_ {2} ... x_ {n}: F ^ {n} x_ {2} x_ {2} ... x_ {n}}.}$

${displaystyle SF ^ {n} leftrightarrow существует ЕСЛИ ^ {n}.}$

S обобщает понятие рефлексивности на все члены любой конечной степени выше 2. N.B: S не следует путать с примитивный комбинатор S комбинаторной логики.

• Декартово произведение, ${displaystyle imes}$;

${displaystyle F ^ {m} imes G ^ {n} leftrightarrow F ^ {m} существует ^ {m} G ^ {n}.}$

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

${displaystyle F ^ {m} x_ {1} ... x_ {m} G ^ {n} x_ {1} ... x_ {n} leftrightarrow (F ^ {m} imes G ^ {n}) x_ { 1} ... x_ {m} x_ {1} ... x_ {n}.}$

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

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

• Основная инверсия, Инв., вращает переменные в списке аргументов вправо, так что последняя переменная становится первой.

${displaystyle InvF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {n} x_ {1} ... x_ {n-1}}.}$

${displaystyle InvFx_ {1} ... x_ {n} leftrightarrow Fx_ {n} x_ {1} ... x_ {n-1}.}$

• Незначительная инверсия, inv, меняет местами первые две переменные в списке аргументов.

${displaystyle invF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {2} x_ {1} ... x_ {n}}.}$

${displaystyle invFx_ {1} ... x_ {n} leftrightarrow Fx_ {2} x_ {1} ... x_ {n}.}$

• Перестановка, п, поворачивает переменные со второй по последнюю в списке аргументов влево, так что вторая переменная становится последней.

${displaystyle pF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {1} x_ {3} ... x_ {n} x_ {2}} .}$

${displaystyle pFx_ {1} ... x_ {n} leftrightarrow InvinvFx_ {1} x_ {3} ... x_ {n} x_ {2}.}$

Учитывая список аргументов, состоящий из п переменные, п неявно относится к последним п−1 переменная, такая как велосипедная цепь, где каждая переменная составляет звено в цепи. Одно приложение п продвигает цепь на одно звено. k последовательные применения п к F^п перемещает k+1 переменная ко второй позиции аргумента в F.

Когда п=2, Инв. и inv просто обмен Икс₁ и Икс₂. Когда п= 1, они не действуют. Следовательно п не действует, когда п < 3.

Кун (1983) берет Основная инверсия и Незначительная инверсия как примитивный. Обозначение п в Куне соответствует inv; у него нет аналога Перестановка и, следовательно, не имеет для этого никаких аксиом. Если, следуя Куайну (1976), п считается примитивным, Инв. и inv можно определить как нетривиальные комбинации +, ∃, и повторял п.

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

Выражение	Степень
${displaystyle p; Инв; inv; lnot; Я}$	без изменений
${Displaystyle + F ^ {п-1}; существует F ^ {n + 1}; SF ^ {n + 1}}$	п
${displaystyle alpha ^ {m} eta ^ {n}; F ^ {m} imes G ^ {n}}$	Максимум(м, п)

Правила

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

• Modus ponens;
• Пусть α и β - формулы ПФЛ, в которых ${displaystyle x_ {1}}$ не появляются. Тогда если ${displaystyle (alpha land Fx_ {1} ... x_ {n}) ightarrow eta}$ является теоремой ПФЛ, то ${displaystyle (существует альфа-земля Fx_ {2} ... x_ {n}) ightarrow eta}$ также является теоремой ПФЛ.

Некоторые полезные результаты

Вместо аксиоматизации PFL Куайн (1976) предложил следующие гипотезы в качестве возможных аксиом.

• ${displaystyle существует I}$

п-1 последовательных итераций п восстанавливает статус-кво анте:

• ${displaystyle F ^ {n} leftrightarrow p ^ {n-1} F ^ {n}}$

+ и ∃ уничтожают друг друга:

Отрицание распространяется на +, ∃, и п:

+ и п распределяет по соединению:

Идентичность имеет интересный смысл:

• ${displaystyle IF ^ {n} ightarrow p ^ {n-2} существует p + F ^ {n}}$

Куайн также предположил правило: если ${displaystyle alpha}$ является теоремой PFL, то и ${displaystyle palpha,}$ ${displaystyle + alpha,}$ и ${displaystyle lnot существует lnot alpha}$.

Работа Бэкона

Бэкон (1985) берет условный, отрицание, Личность, Прокладка, и Основной и Незначительная инверсия как примитив, и Обрезка как определено. Используя терминологию и обозначения, несколько отличающиеся от приведенных выше, Бэкон (1985) излагает две формулировки PFL:

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

Бэкон также:

• Обсуждает связь PFL с термин логика из Sommers (1982), и утверждает, что переработка PFL с использованием синтаксиса, предложенного в приложении Локвуда к Sommers, должна сделать PFL более легким для «чтения, использования и обучения»;
• Касается теоретико-групповой структура Инв. и inv;
• Упоминает, что сентенциальная логика, монадическая логика предикатов, то модальная логика S5, и булева логика (не) перестановки связи, являются фрагментами PFL.

От логики первого порядка к PFL

Следующее алгоритм адаптировано из Quine (1976: 300-2). Учитывая закрытая формула из логика первого порядка, сначала сделайте следующее:

• Прикрепите числовой индекс к каждой букве сказуемого, указав ее степень;
• Перевести все универсальные кванторы в экзистенциальные кванторы и отрицание;
• Переформулируйте все атомарные формулы формы Икс=у в качестве Икси.

Теперь примените следующий алгоритм к предыдущему результату:

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

2. Распределите экзистенциальные кванторы по дизъюнктам в матрице, используя правило перехода (Куайн 1982: 119):

${displaystyle существует x [alpha (x) lor gamma (x)] leftrightarrow (существует xalpha (x) lor exists xgamma (x)).}$

3. Заменить союз на Декартово произведение, ссылаясь на факт:

${displaystyle (F ^ {m} land G ^ {n}) leftrightarrow (F ^ {m} imes G ^ {n}) leftrightarrow (F ^ {m} существует ^ {m} G ^ {n}); m < п.}$

4. Объедините списки аргументов всех элементарных терминов и переместите объединенный список в крайний правый угол подформулы.

5. Использовать Инв. и inv чтобы переместить все экземпляры количественной переменной (назовите ее у) слева от списка аргументов.

6. Вызвать S столько раз, сколько требуется, чтобы устранить все, кроме последнего экземпляра у. Устранять у добавив к подформуле один экземпляр ∃.

7. Повторяйте (1) - (6), пока все количественные переменные не будут исключены. Устраните любые дизъюнкции, попадающие в область действия квантификатора, применив эквивалентность:

${displaystyle (alpha lor eta lor ...) leftrightarrow lnot (lnot alpha land lnot eta land ...).}$

Обратный перевод от PFL к логике первого порядка обсуждается в Quine (1976: 302-4).

Канонический основа математики является аксиоматическая теория множеств, с фоновой логикой, состоящей из логика первого порядка с личность, с вселенная дискурса состоящий полностью из наборов. Есть сингл сказуемое письмо степени 2, интерпретируемой как принадлежность к множеству. PFL перевод канонической аксиоматическая теория множеств ZFC не сложно, так как нет ZFC аксиома требует более 6 количественных переменных.^[2]

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

• Алгебраическая логика

Сноски

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

• Бэкон, Джон, 1985, "Полнота логики предикатов-функторов", Журнал символической логики 50: 903–26.
• Пол Бернейс, 1959, "Uber eine naturliche Erweiterung des Relationenkalkuls" в Heyting, A., ed., Конструктивность в математике. Северная Голландия: 1–14.
• Кун, Стивен Т., 1983, "Аксиоматизация логики функторов предикатов," Журнал формальной логики Нотр-Дам 24: 233–41.
• Уиллард Куайн, 1976, "Алгебраическая логика и функторы предикатов" в Пути парадокса и другие эссе, доп. ред. Harvard Univ. Пресс: 283–307.
• Уиллард Куайн, 1982. Методы логики, 4-е изд. Harvard Univ. Нажмите. Гл. 45.
• Соммерс, Фред, 1982. Логика естественного языка. Oxford Univ. Нажмите.
• Альфред Тарский и Гивант, Стивен, 1987. Формализация теории множеств без переменных. AMS.
• Жан Ван Хейенорт, 1967. От Фреге до Гёделя: Справочник по математической логике. Harvard Univ. Нажмите.

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

• Введение в логику предикатов-функторов (загрузка в один клик, файл PS) Матса Даллёфа (факультет лингвистики Упсальского университета)