basic constructions:
strong axioms
further
In logic, the principle of excluded middle states that every truth value is either true or false (Aristotle, MP1011b24). (This is sometimes called the ‘axiom’ or ‘law’ of excluded middle, either to emphasise that it is or is not optional; ‘principle’ is a relatively neutral term.) One of the many meanings of classical logic is to emphasise that this principle holds in the logic; in contrast, it fails in intuitionistic logic.
The principle of excluded middle (hereafter, PEM), as a statement about truth values themselves, is accepted by nearly all mathematicians (classical mathematics); those who doubt or deny it are a distinct minority, the constructivists. However, when one internalises mathematics in categories other than the category of sets, there is no doubt that excluded middle often fails internally. See the examples listed at internal logic. (Those categories in which excluded middle holds are called Boolean; in general, the adjective ‘Boolean’ is often used to indicate the applicability of PEM.)
Although the term ‘excluded middle’ (sometimes even excluded third) suggests that the principle does not apply in many-valued logics, that is not the point; many-valued logics are many-valued externally but may still be two-valued internally. In the language of categorial logic, whether a category has exactly two subterminal objects is in general independent of whether it is Boolean; instead, the category is Boolean iff the statement that it has exactly two subterminal objects holds in its internal logic (which is in general independent of whether that statement is true).
In fact, intuitionistic logic proves that there is no truth value that is neither true nor false; in this sense, the possibility of a ‘middle’ or ‘third’ truth value is still ‘excluded’. But since the relevant de Morgan law fails in intuitionistic logic, we may not conclude that every truth value is either true or false, which is the actual PEM.
Excluded middle can be seen as a very weak form of the axiom of choice (a slightly more controversial principle, doubted or denied by a slightly larger minority, and true internally in even fewer categories). In fact, the following are equivalent. (this is the Diaconescu-Goodman-Myhill theorem due to Diaconescu 75, see also McLarty 96, theorem 19.7, )
(Here, a set $A$ is finite or finitely-indexed (respectively) if, for some natural number $n$, there is a bijection or surjection (respectively) $\{0, \ldots, n - 1\} \to A$.)
The proof is as follows. If $p$ is a truth value, then divide $\{0,1\}$ by the equivalence relation where $0 \equiv 1$ iff $p$ holds. Then we have a surjection $2\to A$, whose domain is $2$ (and in particular, finite), and whose codomain $A$ is finitely-indexed. But this surjection splits iff $p$ is true or false, so if either $2$ is choice or $2$-indexed sets are projective, then PEM holds.
On the other hand, if PEM holds, then we can show by induction that if $A$ and $B$ are choice, so is $A\sqcup B$ (add details). Thus, all finite sets are choice. Now if $n\to A$ is a surjection, exhibiting $A$ as finitely indexed, it has a section $A\to n$. Since a finite set is always projective, and any retract of a projective object is projective, this shows that $A$ is projective.
In particular, the axiom of choice implies PEM. This argument, due originally to Diaconescu, can be internalized in any topos. However, other weak versions of choice such as countable choice (any surjection to a countable set (which for this purpose is any set isomorphic to the set of natural numbers) has a section), dependent choice, or even COSHEP do not imply PEM. In fact, it is often claimed that axiom of choice is true in constructive mathematics (by the BHK or Brouwer-Heyting-Kolmogorov interpretation of predicate logic), leading to much argument about exactly what that means.
While PEM is not valid in constructive mathematics, its double negation
is valid. One way to see this is to note that $\neg (A\vee B) = \neg A \wedge \neg B$ is one of de Morgan's laws that is constructively valid, and $\neg (\neg A \wedge \neg\neg A)$ is easy to prove (it is an instance of the law of non-contradiction?).
However, a more direct argument makes the structure of the proof more clear. When beta-reduced, the proof term? is $\lambda x. x(inr(\lambda a. x(inl(a))))$. This means that we first assume $\neg (A\vee \neg A)$ for a contradiction, for which it suffices (by assumption) to prove $A\vee \neg A$. We prove that by proving $\neg A$, which we prove by assuming $A$ for a contradiction. But now we can reach a contradiction by invoking (again) our assumption of $\neg (A\vee \neg A)$ and proving $A\vee \neg A$ this time using our new assumption of $A$. In other words, we start out claiming that $\neg A$, but whenever that “bluff gets called” by someone supplying an $A$ and asking us to yield a contradiction, we retroactively change our minds and claim that $A$ instead, using the $A$ that we were just given as evidence.
In particular, this shows how the double negation modality can be regarded computationally as a sort of continuation-passing transform.
However, there is another meaning of “double negated PEM” that is not valid. The above argument shows that
But a stronger statement is
This is related to the above valid statement by a double-negation shift; and in fact, the truth of $\neg\neg \forall A, (A \vee \neg A)$ is equivalent to the principle of double-negation shift. In particular, it is not constructively provable.
Relation to the axiom of choice (Diaconescu-Goodman-Myhill theorem):
Radu Diaconescu, Axiom of choice and complementation, Proceedings of the American Mathematical Society 51:176-178 (1975) (doi:10.1090/S0002-9939-1975-0373893-X)
N. D. Goodman J. Myhill, Choice Implies Excluded Middle, Zeitschrift fuer Mathematische Logik und Grundlagen der Mathematik 24:461 (1978)
Discussion in toposes is for instance in
Last revised on June 6, 2019 at 13:11:08. See the history of this page for a list of all contributions to it.