Editing Law of excluded middle (section)

== Examples ==
For example, if ''P'' is the proposition:

:''Socrates is mortal.''

then the law of excluded middle holds that the [[logical disjunction]]:

:''Either Socrates is mortal, or it is not the case that Socrates is mortal.''

is true by virtue of its form alone. That is, the "middle" position, that Socrates is neither mortal nor not-mortal, is excluded by logic, and therefore either the first possibility (''Socrates is mortal'') or its negation (''it is not the case that Socrates is mortal'') must be true.

An example of an argument that depends on the law of excluded middle follows.<ref>This well-known example of a non-constructive proof depending on  the law of excluded middle can be found in many places, for example: {{cite book |first=Norman |last=Megill |title=Metamath: A Computer Language for Pure Mathematics|at= footnote on p. 17 |url=http://us.metamath.org/index.html#book}} and Davis 2000:220, footnote 2.</ref> We seek to prove that

:there exist two [[irrational number]]s <math>a</math> and <math>b</math> such that <math>a^b</math> is rational.

It is known that <math>\sqrt{2}</math> is irrational (see [[Square root of 2#Proofs of irrationality|proof]]). Consider the number

:<math>\sqrt{2}^{\sqrt{2}}</math>.

Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and
:<math>a=\sqrt{2}</math> and <math>b=\sqrt{2}</math>.

But if <math>\sqrt{2}^{\sqrt{2}}</math> is irrational, then let

:<math>a=\sqrt{2}^{\sqrt{2}}</math> and <math>b=\sqrt{2}</math>.

Then

:<math>a^b = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\left(\sqrt{2}\cdot\sqrt{2}\right)} = \sqrt{2}^2 = 2</math>,

and 2 is certainly rational. This concludes the proof.

In the above argument, the assertion "this number is either rational or irrational" invokes the law of excluded middle. An [[intuitionist]], for example, would not accept this argument without further support for that statement. This might come in the form of a proof that the number in question is in fact irrational (or rational, as the case may be); or a finite algorithm that could determine whether the number is rational.

=== Non-constructive proofs over the infinite ===

The above proof is an example of a ''[[non-constructive]]'' proof disallowed by intuitionists:
{{quote|The proof is non-constructive because it doesn't give specific numbers <math>a</math> and <math>b</math> that satisfy the theorem but only two separate possibilities, one of which must work. (Actually <math>a=\sqrt{2}^{\sqrt{2}}</math> is irrational but there is no known easy proof of that fact.) (Davis 2000:220)}} (Constructive proofs of the specific example above are not hard to produce; for example <math>a=\sqrt{2}</math> and <math>b=\log_2 9</math> are both easily shown to be irrational, and <math>a^b=3</math>; a proof allowed by intuitionists).

By ''non-constructive'' Davis means that "a proof that there actually are mathematic entities satisfying certain conditions would not have to provide a method to exhibit explicitly the entities in question." (p.&nbsp;85). Such proofs presume the existence of a totality that is complete, a notion disallowed by intuitionists when extended to the ''infinite''—for them the infinite can never be completed:

{{quote|In classical mathematics there occur ''non-constructive'' or ''indirect'' existence proofs, which intuitionists do not accept. For example, to prove ''there exists an n such that P''(''n''), the classical mathematician may deduce a contradiction from the assumption for all ''n'', not ''P''(''n''). Under both the classical and the intuitionistic logic, by reductio ad absurdum this gives ''not for all n, not P''(''n''). The classical logic allows this result to be transformed into ''there exists an n such that P''(''n''), but not in general the intuitionistic … the classical meaning, that somewhere in the completed infinite totality of the natural numbers there occurs an ''n'' such that ''P''(''n''), is not available to him, since he does not conceive the natural numbers as a completed totality.<ref>In a comparative analysis (pp. 43–59) of the three "-isms" (and their foremost spokesmen)—Logicism (Russell and Whitehead), Intuitionism (Brouwer) and Formalism (Hilbert)—Kleene turns his thorough eye toward intuitionism, its "founder" Brouwer, and the intuitionists' complaints with respect to the law of excluded middle as applied to arguments over the "completed infinite".</ref> (Kleene 1952:49–50)}}

[[David Hilbert]] and [[Luitzen E. J. Brouwer]] both give examples of the law of excluded middle extended to the infinite. Hilbert's example: "the assertion that either there are only finitely many prime numbers or there are infinitely many" (quoted in Davis 2000:97); and Brouwer's: "Every mathematical species is either finite or infinite." (Brouwer 1923 in van Heijenoort 1967:336). In general, intuitionists allow the use of the law of excluded middle when it is confined to discourse over finite collections (sets), but not when it is used in discourse over infinite sets (e.g. the natural numbers). Thus intuitionists absolutely disallow the blanket assertion: "For all propositions ''P'' concerning infinite sets ''D'': ''P'' or ~''P''" (Kleene 1952:48).<ref>For more about the conflict between the intuitionists (e.g. Brouwer) and the formalists (Hilbert) see [[Foundations of mathematics]] and [[Intuitionism]].</ref>

Putative counterexamples to the law of excluded middle include the [[liar paradox]] or [[Quine's paradox]]. Certain resolutions of these paradoxes, particularly [[Graham Priest]]'s [[dialetheism]] as formalised in LP, have the law of excluded middle as a theorem, but resolve out the Liar as both true and false. In this way, the law of excluded middle is true, but because truth itself, and therefore disjunction, is not exclusive, it says next to nothing if one of the disjuncts is paradoxical, or both true and false.