Введение
Теорема логики
В логике закон исключённого третьего, или принцип исключённого третьего, утверждает, что для любого высказывания либо само это высказывание, либо его отрицание истинно. Это один из трёх законов мышления, наряду с законом непротиворечия и законом тождества; однако ни одна система логики не основывается исключительно на этих законах, и ни один из них не предоставляет правила вывода, такие как modus ponens или законы Де Моргана. Закон также известен как закон / принцип исключённой середины, на латыни – principium tertii exclusi. Другое латинское обозначение этого закона – tertium non datur, или «третьего [варианта] не дано». В классической логике закон является тавтологией. Этот принцип не следует путать с семантическим принципом бивалентности, который утверждает, что каждое высказывание либо истинно, либо ложно. Принцип бивалентности всегда подразумевает закон исключённого третьего, но обратное не всегда верно. Часто приводимый контрпример использует утверждения, которые сейчас недоказуемы, но могут быть доказаны в будущем, чтобы показать, что закон исключённого третьего может выполняться, когда принцип бивалентности не соблюдается.
Последствия закона исключенного середины в Principia Mathematica
Из закона исключённого третьего, формулы ✸2.1 в Principia Mathematica, Уайтхед и Рассел выводят некоторые из самых мощных инструментов в арсенале логических аргументов. (В Principia Mathematica формулы и предложения идентифицируются начальной звездочкой и двумя числами, например, "✸2.1".) ✸2.1 ~p ∨ p "Это закон исключённого третьего" (PM, с. 101). Доказательство ✸2.1 выглядит примерно следующим образом: "первичная идея" 1.08 определяет p → q = ~p ∨ q. Подставляя p вместо q в этом правиле, получаем p → p = ~p ∨ p. Поскольку p → p истинно (это теорема 2.08, доказанная отдельно), то ~p ∨ p должно быть истинным. ✸2.11 p ∨ ~p (Перестановка утверждений разрешена аксиомой 1.4)
✸2.12 p → ~(~p) (Принцип двойного отрицания, часть 1: если "эта роза красная" истинно, то неверно, что "эта роза не красная".) ✸2.13 p ∨ ~{~(~p)} (Лемма, используемая вместе с 2.12 для вывода 2.14)
✸2.14 ~(~p) → p (Принцип двойного отрицания, часть 2)
✸2.15 (~p → q) → (~q → p) (Один из четырёх "Принципов транспозиции". Схож с 1.03, 1.16 и 1.17. Здесь потребовалось очень длинное доказательство.) ✸2.16 (p → q) → (~q → ~p) (Если истинно, что "Если эта роза красная, то эта свинья летает", то истинно, что "Если эта свинья не летает, то эта роза не красная".) ✸2.17 (~p → ~q) → (q → p) (Ещё один из "Принципов транспозиции".) ✸2.18 (~p → p) → p (Называется "Дополнением к reductio ad absurdum. Утверждается, что предложение, вытекающее из гипотезы о его собственной ложности, истинно" (PM, с. 103–104).) Большинство этих теорем — в частности, ✸2.1, ✸2.11 и ✸2.14 — отвергаются интуиционизмом. Эти инструменты переформулированы в другую форму, которую Колмогоров цитирует как "четыре аксиомы импликации Гильберта" и "две аксиомы отрицания Гильберта" (Колмогоров в ван Хейеноорте, с. 335). Предложения ✸2.12 и ✸2.14, "двойное отрицание":
В интуиционистских трудах Л. Э. Дж. Брауэра упоминается то, что он называет "принципом взаимности множественных видов, то есть принципом, согласно которому для каждой системы истинность свойства следует из невозможности его ложности" (Брауэр, ibid, с. 335). Этот принцип обычно называют "принципом двойного отрицания" (PM, с. 101–102). Из закона исключённого третьего (✸2.1 и ✸2.11) PM непосредственно выводит принцип ✸2.12. Подставляя ~p вместо p в 2.11, получаем ~p ∨ ~(~p), и по определению импликации (т. е. 1.01 p → q = ~p ∨ q) то ~p ∨ ~(~p) = p → ~(~p). QED (Вывод 2.14 немного сложнее.)
✸2.12 p → ~(~p) (Principle of double negation, part 1: if "this rose is red" is true then it's not true that this rose is not red' is true".) ✸2.13 p ∨ ~{~(~p)} (Lemma together with 2.12 used to derive 2.14)
✸2.14 ~(~p) → p (Principle of double negation, part 2)
✸2.15 (~p → q) → (~q → p) (One of the four "Principles of transposition". Similar to 1.03, 1.16 and 1.17. A very long demonstration was required here.) ✸2.16 (p → q) → (~q → ~p) (If it's true that "If this rose is red then this pig flies" then it's true that "If this pig doesn't fly then this rose isn't red.") ✸2.17 ( ~p → ~q ) → (q → p) (Another of the "Principles of transposition".) ✸2.18 (~p → p) → p (Called "The complement of reductio ad absurdum. It states that a proposition which follows from the hypothesis of its own falsehood is true" (PM, pp. 103–104).) Most of these theorems—in particular ✸2.1, ✸2.11, and ✸2.14—are rejected by intuitionism. These tools are recast into another form that Kolmogorov cites as "Hilbert's four axioms of implication" and "Hilbert's two axioms of negation" (Kolmogorov in van Heijenoort, p. 335). Propositions ✸2.12 and ✸2.14, "double negation":
The intuitionist writings of L. E. J. Brouwer refer to what he calls "the principle of the reciprocity of the multiple species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property" (Brouwer, ibid, p. 335). This principle is commonly called "the principle of double negation" (PM, pp. 101–102). From the law of excluded middle (✸2.1 and ✸2.11), PM derives principle ✸2.12 immediately. We substitute ~p for p in 2.11 to yield ~p ∨ ~(~p), and by the definition of implication (i. e. 1.01 p → q = ~p ∨ q) then ~p ∨ ~(~p)= p → ~(~p). QED (The derivation of 2.14 is a bit more involved.)