Закон Пирса

Аксиома, используемая в логике и философии

В логике закон Пирса назван в честь философа и логика Чарльза Сандерса Пирса . Это было принято как аксиома в его первой аксиоматизации логики высказываний . Его можно рассматривать как закон исключенного третьего, записанный в форме, которая включает только один вид связки, а именно импликацию.

В исчислении высказываний закон Пирса гласит , что (( P → Q )→ P )→ P . Вкратце это означает, что P должно быть истинным, если существует предложение Q такое, что истинность P следует из истины «если P , то Q ».

Закон Пирса не выполняется ни в интуиционистской логике , ни в промежуточных логиках , и его нельзя вывести только из теоремы дедукции .

При изоморфизме Карри-Говарда закон Пирса является типом операторов продолжения , например call/cc в Scheme . ^[1]

История

Вот формулировка закона самим Пирсом:

Пятая икона необходима для принципа исключенного среднего и других связанных с ним пропозиций. Одна из простейших формул такого рода:

Вряд ли это аксиома. То, что это правда, проявляется в следующем. Оно может быть ложным только в том случае, если конечный консеквент x ложен, в то время как его антецедент ( x ⤙ y ) ⤙ x истинен. Если это правда, то либо ее консеквент x является истинным, хотя вся формула была бы истинной, либо ее антецедент x ⤙ y является ложным. Но в последнем случае антецедент x ⤙ y , то есть x , должен быть истинным. (Пирс, Сборник статей 3.384).

Пирс далее указывает на немедленное применение закона:

Из только что приведенной формулы сразу получаем:

где a используется в таком смысле, что ( x ⤙ y ) ⤙ a означает, что из ( x ⤙ y ) следует каждое предложение. При таком понимании формула утверждает принцип исключенного третьего, согласно которому из ложности отрицания x следует истинность x . (Пирс, Сборник статей 3.384).

Предупреждение : как объяснено в тексте, « а » здесь обозначает не пропозициональный атом, а что-то вроде квантифицированной пропозициональной формулы . Формула (( x → y ) → a ) → x не была бы тавтологией , если бы a интерпретировалось как атом. ${\displaystyle \forall p\,p}$

Отношения между принципами

В интуиционистской логике, если оно доказано или отвергнуто, или если оно доказано истинно, то действует закон Писа для двух предложений. Но особый случай закона, когда он отвергается, называемый Concecence mirabilis , эквивалентен исключенному третьему уже в рамках минимальной логики . Это также означает, что закон Писа влечет за собой классическую логику, а не интуиционистскую логику, как также показано ниже. Интуиционистски, даже ограничение не подразумевает закона для двух предложений. Постулирование истинности последнего приводит к промежуточной логике Сметанича . ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle \neg Q\to P}$

Полезно рассмотреть закон Пирса в эквивалентной форме . Действительно, из следует , и поэтому эквивалентно . Теперь этот случай напрямую показывает, как устранение двойного отрицания подразумевает последовательность чудес над минимальной логикой. ${\displaystyle ((P\to Q)\to (P\land Q))\to P}$ ${\displaystyle P\to Q}$ ${\displaystyle P\leftrightarrow (P\land Q)}$ ${\displaystyle (P\to Q)\to P}$ ${\displaystyle (P\to Q)\to (P\land Q)}$ ${\displaystyle Q=\bot }$ ${\displaystyle \neg \neg P\to P}$

В интуиционистской логике взрыв может быть использован для , и поэтому здесь специальный случай закона Consequence mirabilis также подразумевает устранение двойного отрицания. Поскольку двойное отрицание исключенного третьего всегда уже действительно, даже в минимальной логике, это также интуиционистски доказывает исключенное среднее. В другом направлении можно также интуитивно показать, что исключенное третье напрямую подразумевает закон Писа. С этой целью заметим, что, используя принцип взрыва , исключенная середина может быть выражена как . На словах это можно выразить так: «Каждое предложение либо содержит, либо подразумевает любое другое предложение». Теперь, чтобы доказать закон, заметим, что он выводится из простого введения импликации, с одной стороны, и modus ponens, с другой. Наконец, вместо рассмотрения . ${\displaystyle \bot \to (P\land \bot )}$ ${\displaystyle P\lor (P\to Q)}$ ${\displaystyle P}$ ${\displaystyle (P\lor R)\to ((R\to P)\to P)}$ ${\displaystyle R}$ ${\displaystyle P\to Q}$

Другое доказательство закона классической логики происходит путем двойного прохождения классически допустимого обратного дизъюнктивного силлогизма : Сначала обратите внимание на то, что подразумевается из , что интуиционистски эквивалентно . Теперь взрыв влечет за собой это , а использование исключенного среднего для влечет за собой, что эти два фактически эквивалентны. В совокупности это означает, что в классической логике эквивалентно . ${\displaystyle \neg \neg P}$ ${\displaystyle (\neg \neg P\land \neg Q)\lor P}$ ${\displaystyle \neg (\neg P\lor Q)\lor P}$ ${\displaystyle \neg A\lor B}$ ${\displaystyle A\to B}$ ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle (P\to Q)\to P}$

Использование закона Пирса с теоремой о дедукции

Закон Пирса позволяет усовершенствовать технику использования теоремы дедукции для доказательства теорем. Предположим, что вам дан набор посылок Γ и вы хотите вывести из них предложение Z. С помощью закона Пирса можно добавить (бесплатно) дополнительные помещения вида Z → P к Γ. Например, предположим, что нам даны P → Z и ( P → Q ) → Z , и мы хотим вывести Z , чтобы мы могли использовать теорему о дедукции и заключить, что ( P → Z ) → ((( P → Q ) → Z )→ Z ) — теорема. Тогда мы можем добавить еще одну посылку Z → Q. Отсюда и P → Z получаем P → Q. Затем мы применяем modus ponens с ( P → Q )→ Z в качестве основной предпосылки для получения Z. Применяя теорему дедукции, получаем, что ( Z → Q )→ Z следует из исходных посылок. Затем мы используем закон Пирса в форме (( Z → Q ) → Z ) → Z и modus ponens, чтобы вывести Z из исходных посылок. Тогда мы сможем завершить доказательство теоремы так, как планировали изначально.

Полнота импликативного исчисления высказываний

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

• П →( Q → П )
• ( P →( Q → R ))→(( P → Q )→( P → R ))
• (( P → Q )→ P )→ P
• из P и P → Q вывести Q

(где P , Q , R содержат только «→» в качестве связки) — это все тавтологии , в которых в качестве связки используется только «→».

Неудача неклассических моделей интуиционистской логики

Поскольку закон Пирса подразумевает закон исключенного третьего, он всегда должен ошибаться в неклассической интуиционистской логике. Простой явный контрпример — это многозначная логика Гёделя , которая представляет собой нечеткую логику , в которой значения истинности представляют собой действительные числа от 0 до 1, с материальной импликацией, определяемой следующим образом:

${\displaystyle {\begin{aligned}u\mathrel {\xrightarrow[{G}]{}} v&={\begin{cases}1,&{\text{if }}u\leq v\\v,&{\text{if }}u>v\end{cases}}\end{aligned}}}$

и где закон Пирса как формулу можно упростить до:

${\displaystyle {\begin{aligned}((u\mathrel {\xrightarrow[{G}]{}} v)\mathrel {\xrightarrow[{G}]{}} u)\mathrel {\xrightarrow[{G}]{}} u&={\begin{cases}1,&{\text{if }}u\leq v\\u,&{\text{if }}u>v\end{cases}}\end{aligned}}}$

где это всегда верно, было бы эквивалентно утверждению, что u > v подразумевает u = 1, что верно только в том случае, если 0 и 1 являются единственными разрешенными значениями. В то же время, однако, выражение никогда не может быть равно нижнему значению истинности логики, и его двойное отрицание всегда истинно.

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

• Библиография Чарльза Сандерса Пирса

Примечания

1. Тимоти Г. Гриффин, Понятие управления «Формулы как типы», 1990 — Гриффин определяет K на странице 3 как эквивалент вызова Scheme /cc, а затем обсуждает его тип, являющийся эквивалентом закона Пирса в конце раздела 5. страница 9.

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

• Пирс, К.С., «Об алгебре логики: вклад в философию обозначений», American Journal of Mathematics 7, 180–202 (1885). Перепечатано, Сборник статей Чарльза Сандерса Пирса 3.359–403 и Сочинения Чарльза С. Пирса: хронологическое издание 5, 162–190.
• Пирс, CS, Сборник статей Чарльза Сандерса Пирса , Vols. 1–6, Чарльз Хартшорн и Пол Вайс (ред.), Vols. 7–8, Артур В. Беркс (редактор), издательство Гарвардского университета, Кембридж, Массачусетс, 1931–1935, 1958.