Q0 (математическая логика) - Q0 (mathematical logic)

Q₀ является Питер Эндрюс 'формулировка просто типизированное лямбда-исчисление, и обеспечивает основу для математики, сравнимую с логикой первого порядка плюс теорией множеств. логика высшего порядка и тесно связан с логикой Инструмент доказательства теорем HOL семья.

Системы доказательства теорем TPS и ETPS основаны на Q₀. В августе 2009 года TPS выиграла первое в истории соревнование среди систем доказательства теорем более высокого порядка.^[1]

Аксиомы Q₀

В системе всего пять аксиом, которые можно сформулировать так:

${ displaystyle (1)}$  ${ displaystyle g_ {oo} T land g_ {oo} F = forall x_ {o} centerdot g_ {oo} x_ {o}}$

${ displaystyle (2 ^ { alpha})}$  ${ displaystyle [x _ { alpha} = y _ { alpha}] supset centerdot , h_ {o alpha} x _ { alpha} = h_ {o alpha} y _ { alpha}}$

${ Displaystyle (3 ^ { альфа бета})}$  ${ displaystyle f _ { alpha beta} = g _ { alpha beta} = forall x _ { beta} centerdot f _ { alpha beta} x _ { beta} = g _ { alpha beta} x_ { beta}}$

${ displaystyle (4)}$  ${ displaystyle [ lambda mathbf {x _ { alpha}} mathbf {B} _ { beta}] mathbf {A} _ { alpha} = mathbf {S} _ {A _ { alpha}} ^ { mathbf {x} _ { alpha}} mathbf {B} _ { beta}}$

${ displaystyle (5)}$  ℩${ Displaystyle _ {я (oi)} [{ text {Q}} _ {oii} y_ {i}] = y_ {i} ,}$

(Аксиомы 2, 3 и 4 являются схемами аксиом - семейством подобных аксиом. Примеры аксиомы 2 и аксиомы 3 различаются только типами переменных и констант, но экземпляры аксиомы 4 могут иметь любое выражение, заменяющее А и B.)

Подписанный "о"является символом типа для логических значений и имеет нижний индекс"я"- символ типа для отдельных (не логических) значений. Последовательности этих значений представляют типы функций и могут включать круглые скобки для различения различных типов функций. Греческие буквы в нижнем индексе, такие как α и β, являются синтаксическими переменными для символов типов. Полужирные заглавные буквы, такие как А, B, и C - синтаксические переменные для WFF, а жирные строчные буквы, такие как Икс, у являются синтаксическими переменными для переменных.S указывает на синтаксическую замену во всех свободных случаях.

Единственными примитивными константами являются Q_{((oα) α)}, обозначая равенство членов каждого типа α, и ℩_{(я (ои))}, обозначающий оператор описания для индивидов, уникальный элемент набора, содержащий ровно одного индивида. Символы λ и скобки («[» и «]») являются синтаксисом языка. Все остальные символы являются сокращениями для терминов, содержащих их, включая кванторы ∀ и ∃.

В Аксиоме 4 Икс должен быть свободен для А в B, что означает, что подстановка не вызывает появления свободных переменных А стать связанным в результате замены.

Об аксиомах

• Аксиома 1 выражает идею, что Т и F являются единственными логическими значениями.
• Схемы аксиом 2^α и 3^αβ выражают фундаментальные свойства функций.
• Схема аксиом 4 определяет природу λ-обозначений.
• Аксиома 5 говорит, что оператор выбора является обратной функцией равенства для отдельных лиц. (Учитывая один аргумент, Q сопоставляет этого индивида с набором / предикатом, содержащим индивид. В Q₀, х = у это сокращение от Qxy, что является аббревиатурой от (Qx) y.)

В Эндрюс 2002 Аксиома 4 состоит из пяти частей, в которых рассматривается процесс замещения. Приведенная здесь аксиома обсуждается как альтернатива и доказывается в подразделах.

Вывод в Q₀

Q₀ имеет единственное правило вывода.

Линейка. Из C и А_α = B_α вывести результат замены одного вхождения А_α в C появлением B_αпри условии, что возникновение А_α в Cне (вхождение переменной) непосредственно предшествует λ.

Производное правило вывода Р' позволяет рассуждать на основе набора гипотез ЧАС.

Линейка'. Если ЧАС ⊦ А_α = B_α,и ЧАС ⊦ C, и D получается из Cзаменив одно вхождение А_α появлением B_α, тогдаЧАС ⊦ D, при условии, что:

• Возникновение А_α в C не является вхождением переменной, которой непосредственно предшествует λ, и
• нет свободной переменной в А_α = B_α и член ЧАС связан в C при замененном появлении А_α.

Примечание: ограничение на замену А_α кB_α в C гарантирует, что любая переменная свободна как в гипотезе, так и в А_α = B_αпо-прежнему ограничивается тем, чтобы иметь одно и то же значение в обоих после завершения замены.

Теорема вывода для Q₀ показывает, что доказательства из гипотез с использованием правила R′ могут быть преобразованы в доказательства без гипотез и с использованием правила R.

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

1. ∃x Px
2. Px ⊃ Qx

и тот факт, что A ⊃ B ≡ (A ≡ A ∧ B), мы можем продолжить, не удаляя квантор:

3. Px ≡ (Px ∧ Qx) создание экземпляра для A и B
4. ∃x (Px ∧ Qx) Правило R подставляет в строку 1 с помощью строки 3.

Примечания

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

• Эндрюс, Питер Б. (2002). Введение в математическую логику и теорию типов: к истине через доказательство (2-е изд.). Дордрехт, Нидерланды: Kluwer Academic Publishers. ISBN  1-4020-0763-9. Смотрите также [1]
• Церковь, Алонсо (1940). «Формулировка простой теории типов» (PDF). Журнал символической логики. 5: 56–58. Дои:10.2307/2266170.

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

• А описание Q₀ более подробно; часть статьи о Теория типов Чёрча в Стэнфордская энциклопедия философии.
• Обзор математической логики (включая различных преемников Q₀): Основы математики. Генеалогия и обзор DOI: 10.4444 / 100.111.