# Law of excluded middle

Last updated

In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. [1] [2] It is one of the so-called three laws of thought, along with the law of noncontradiction, and the law of identity. However, no system of logic is built on just these laws, and none of these laws provides inference rules, such as modus ponens or De Morgan's laws.

## Contents

The law is also known as the law (or principle) of the excluded third, in Latin principium tertii exclusi. Another Latin designation for this law is tertium non datur: "no third [possibility] is given". It is a tautology.

The principle should not be confused with the semantical principle of bivalence, which states that every proposition is either true or false. The principle of bivalence always implies the law of excluded middle, while the converse is not always true. A commonly cited counterexample uses statements unprovable now, but provable in the future to show that the law of excluded middle may apply when the principle of bivalence fails. [3]

## History

### Aristotle

The earliest known formulation is in Aristotle's discussion of the principle of non-contradiction, first proposed in On Interpretation, [4] where he says that of two contradictory propositions (i.e. where one proposition is the negation of the other) one must be true, and the other false. [5] He also states it as a principle in the Metaphysics book 3, saying that it is necessary in every case to affirm or deny, [6] and that it is impossible that there should be anything between the two parts of a contradiction. [7]

Aristotle wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the facts themselves:

It is impossible, then, that "being a man" should mean precisely "not being a man", if "man" not only signifies something about one subject but also has one significance. … And it will not be possible to be and not to be the same thing, except in virtue of an ambiguity, just as if one whom we call "man", and others were to call "not-man"; but the point in question is not this, whether the same thing can at the same time be and not be a man in name, but whether it can be in fact. (Metaphysics 4.4, W.D. Ross (trans.), GBWW 8, 525–526).

Aristotle's assertion that "it will not be possible to be and not to be the same thing", which would be written in propositional logic as ~(P ∧ ~P), is a statement modern logicians could call the law of excluded middle (P ∨ ~P), as distribution of the negation of Aristotle's assertion makes them equivalent, regardless that the former claims that no statement is both true and false, while the latter requires that any statement is either true or false.

But Aristotle also writes, "since it is impossible that contradictories should be at the same time true of the same thing, obviously contraries also cannot belong at the same time to the same thing" (Book IV, CH 6, p. 531). He then proposes that "there cannot be an intermediate between contradictories, but of one subject we must either affirm or deny any one predicate" (Book IV, CH 7, p. 531). In the context of Aristotle's traditional logic, this is a remarkably precise statement of the law of excluded middle, P ∨ ~P.

Also in On Interpretation, Aristotle seems to deny the law of excluded middle in the case of future contingents, in his discussion on the sea battle.

### Leibniz

Its usual form, "Every judgment is either true or false" [footnote 9] …"(from Kolmogorov in van Heijenoort, p. 421) footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais , IV,2)" (ibid p 421)

### Bertrand Russell and Principia Mathematica

The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as:

${\displaystyle \mathbf {*2\cdot 11} .\ \ \vdash .\ p\ \vee \thicksim p}$. [8]

So just what is "truth" and "falsehood"? At the opening PM quickly announces some definitions:

Truth-values. The "truth-value" of a proposition is truth if it is true and falsehood if it is false* [*This phrase is due to Frege] … the truth-value of "p ∨ q" is truth if the truth-value of either p or q is truth, and is falsehood otherwise … that of "~ p" is the opposite of that of p …" (p. 7-8)

This is not much help. But later, in a much deeper discussion ("Definition and systematic ambiguity of Truth and Falsehood" Chapter II part III, p. 41 ff), PM defines truth and falsehood in terms of a relationship between the "a" and the "b" and the "percipient". For example "This 'a' is 'b'" (e.g. "This 'object a' is 'red'") really means "'object a' is a sense-datum" and "'red' is a sense-datum", and they "stand in relation" to one another and in relation to "I". Thus what we really mean is: "I perceive that 'This object a is red'" and this is an undeniable-by-3rd-party "truth".

PM further defines a distinction between a "sense-datum" and a "sensation":

That is, when we judge (say) "this is red", what occurs is a relation of three terms, the mind, and "this", and "red". On the other hand, when we perceive "the redness of this", there is a relation of two terms, namely the mind and the complex object "the redness of this" (pp. 43–44).

Russell reiterated his distinction between "sense-datum" and "sensation" in his book The Problems of Philosophy (1912), published at the same time as PM (1910–1913):

Let us give the name of "sense-data" to the things that are immediately known in sensation: such things as colours, sounds, smells, hardnesses, roughnesses, and so on. We shall give the name "sensation" to the experience of being immediately aware of these things … The colour itself is a sense-datum, not a sensation. (p. 12)

Russell further described his reasoning behind his definitions of "truth" and "falsehood" in the same book (Chapter XII, Truth and Falsehood).

#### Consequences of the law of excluded middle in Principia Mathematica

From the law of excluded middle, formula ✸2.1 in Principia Mathematica, Whitehead and Russell derive some of the most powerful tools in the logician's argumentation toolkit. (In Principia Mathematica, formulas and propositions are identified by a leading asterisk and two numbers, such as "✸2.1".)

✸2.1 ~pp "This is the Law of excluded middle" (PM, p. 101).

The proof of ✸2.1 is roughly as follows: "primitive idea" 1.08 defines pq = ~pq. Substituting p for q in this rule yields pp = ~pp. Since pp is true (this is Theorem 2.08, which is proved separately), then ~pp must be true.

✸2.11 p ∨ ~p (Permutation of the assertions is allowed by axiom 1.4)
✸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 (~pq) → (~qp) (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 (pq) → (~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 ) → (qp) (Another of the "Principles of transposition".)
✸2.18 (~pp) → 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.)

### Reichenbach

It is correct, at least for bivalent logic—i.e. it can be seen with a Karnaugh map—that this law removes "the middle" of the inclusive-or used in his law (3). And this is the point of Reichenbach's demonstration that some believe the exclusive-or should take the place of the inclusive-or.

About this issue (in admittedly very technical terms) Reichenbach observes:

The tertium non datur
29. (x)[f(x) ∨ ~f(x)]
is not exhaustive in its major terms and is therefore an inflated formula. This fact may perhaps explain why some people consider it unreasonable to write (29) with the inclusive-'or', and want to have it written with the sign of the exclusive-'or'
30. (x)[f(x) ⊕ ~f(x)], where the symbol "⊕" signifies exclusive-or [9]
in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)

In line (30) the "(x)" means "for all" or "for every", a form used by Russell and Reichenbach; today the symbolism is usually ${\displaystyle \forall }$x. Thus an example of the expression would look like this:

• (pig): (Flies(pig) ⊕ ~Flies(pig))
• (For all instances of "pig" seen and unseen): ("Pig does fly" or "Pig does not fly" but not both simultaneously)

### Formalists versus Intuitionists

From the late 1800s through the 1930s, a bitter, persistent debate raged between Hilbert and his followers versus Hermann Weyl and L. E. J. Brouwer. Brouwer's philosophy, called intuitionism, started in earnest with Leopold Kronecker in the late 1800s.

Hilbert intensely disliked Kronecker's ideas:

Kronecker insisted that there could be no existence without construction. For him, as for Paul Gordan [another elderly mathematician], Hilbert's proof of the finiteness of the basis of the invariant system was simply not mathematics. Hilbert, on the other hand, throughout his life was to insist that if one can prove that the attributes assigned to a concept will never lead to a contradiction, the mathematical existence of the concept is thereby established (Reid p. 34)

It was his [Kronecker's] contention that nothing could be said to have mathematical existence unless it could actually be constructed with a finite number of positive integers (Reid p. 26)

The debate had a profound effect on Hilbert. Reid indicates that Hilbert's second problem (one of Hilbert's problems from the Second International Conference in Paris in 1900) evolved from this debate (italics in the original):

In his second problem, [Hilbert] had asked for a mathematical proof of the consistency of the axioms of the arithmetic of real numbers.
To show the significance of this problem, he added the following observation:
"If contradictory attributes be assigned to a concept, I say that mathematically the concept does not exist" (Reid p. 71)

Thus, Hilbert was saying: "If p and ~p are both shown to be true, then p does not exist", and was thereby invoking the law of excluded middle cast into the form of the law of contradiction.

And finally constructivists … restricted mathematics to the study of concrete operations on finite or potentially (but not actually) infinite structures; completed infinite totalities … were rejected, as were indirect proof based on the Law of Excluded Middle. Most radical among the constructivists were the intuitionists, led by the erstwhile topologist L. E. J. Brouwer (Dawson p. 49)

The rancorous debate continued through the early 1900s into the 1920s; in 1927 Brouwer complained about "polemicizing against it [intuitionism] in sneering tones" (Brouwer in van Heijenoort, p. 492). But the debate was fertile: it resulted in Principia Mathematica (1910–1913), and that work gave a precise definition to the law of excluded middle, and all this provided an intellectual setting and the tools necessary for the mathematicians of the early 20th century:

Out of the rancor, and spawned in part by it, there arose several important logical developments; Zermelo's axiomatization of set theory (1908a), that was followed two years later by the first volume of Principia Mathematica, in which Russell and Whitehead showed how, via the theory of types: much of arithmetic could be developed by logicist means (Dawson p. 49)

Brouwer reduced the debate to the use of proofs designed from "negative" or "non-existence" versus "constructive" proof:

According to Brouwer, a statement that an object exists having a given property means that, and is only proved, when a method is known which in principle at least will enable such an object to be found or constructed …
Hilbert naturally disagreed.
"pure existence proofs have been the most important landmarks in the historical development of our science," he maintained. (Reid p. 155)
Brouwer refused to accept the logical principle of the excluded middle, His argument was the following:
"Suppose that A is the statement "There exists a member of the set S having the property P." If the set is finite, it is possible—in principle—to examine each member of S and determine whether there is a member of S with the property P or that every member of S lacks the property P." (this was missing a closing quote) For finite sets, therefore, Brouwer accepted the principle of the excluded middle as valid. He refused to accept it for infinite sets because if the set S is infinite, we cannot—even in principle—examine each member of the set. If, during the course of our examination, we find a member of the set with the property P, the first alternative is substantiated; but if we never find such a member, the second alternative is still not substantiated.
Since mathematical theorems are often proved by establishing that the negation would involve us in a contradiction, this third possibility which Brouwer suggested would throw into question many of the mathematical statements currently accepted.
"Taking the Principle of the Excluded Middle from the mathematician," Hilbert said, "is the same as … prohibiting the boxer the use of his fists."
"The possible loss did not seem to bother Weyl … Brouwer's program was the coming thing, he insisted to his friends in Zürich." (Reid, p. 149)}}

In his lecture in 1941 at Yale and the subsequent paper, Gödel proposed a solution: "that the negation of a universal proposition was to be understood as asserting the existence … of a counterexample" (Dawson, p. 157))

Gödel's approach to the law of excluded middle was to assert that objections against "the use of 'impredicative definitions'" had "carried more weight" than "the law of excluded middle and related theorems of the propositional calculus" (Dawson p. 156). He proposed his "system Σ … and he concluded by mentioning several applications of his interpretation. Among them were a proof of the consistency with intuitionistic logic of the principle ~ (∀A: (A ∨ ~A)) (despite the inconsistency of the assumption ∃ A: ~ (A ∨ ~A))" (Dawson, p. 157) (no closing parenthesis had been placed)

The debate seemed to weaken: mathematicians, logicians and engineers continue to use the law of excluded middle (and double negation) in their daily work.

### Intuitionist definitions of the law (principle) of excluded middle

The following highlights the deep mathematical and philosophic problem behind what it means to "know", and also helps elucidate what the "law" implies (i.e. what the law really means). Their difficulties with the law emerge: that they do not want to accept as true implications drawn from that which is unverifiable (untestable, unknowable) or from the impossible or the false. (All quotes are from van Heijenoort, italics added).

Brouwer offers his definition of "principle of excluded middle"; we see here also the issue of "testability":

On the basis of the testability just mentioned, there hold, for properties conceived within a specific finite main system, the "principle of excluded middle", that is, the principle that for every system every property is either correct [richtig] or impossible, and in particular the principle of the reciprocity of the complementary species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property. (335)[ citation needed ]

Kolmogorov's definition cites Hilbert's two axioms of negation

1. A → (~AB)
2. (AB) → { (~AB) → B}
Hilbert's first axiom of negation, "anything follows from the false", made its appearance only with the rise of symbolic logic, as did the first axiom of implication … while … the axiom under consideration [axiom 5] asserts something about the consequences of something impossible: we have to accept B if the true judgment A is regarded as false …
Hilbert's second axiom of negation expresses the principle of excluded middle. The principle is expressed here in the form in which is it used for derivations: if B follows from A as well as from ~A, then B is true. Its usual form, "every judgment is either true or false" is equivalent to that given above".
From the first interpretation of negation, that is, the interdiction from regarding the judgment as true, it is impossible to obtain the certitude that the principle of excluded middle is true … Brouwer showed that in the case of such transfinite judgments the principle of excluded middle cannot be considered obvious
footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais, IV,2). The formulation "A is either B or not-B" has nothing to do with the logic of judgments.
footnote 10: "Symbolically the second form is expressed thus
A ∨ ~A

where ∨ means "or". The equivalence of the two forms is easily proved (p. 421)

## 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. [10] We seek to prove that

there exist two irrational numbers ${\displaystyle a}$ and ${\displaystyle b}$ such that ${\displaystyle a^{b}}$ is rational.

It is known that ${\displaystyle {\sqrt {2}}}$ is irrational (see proof). Consider the number

${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$.

Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and

${\displaystyle a={\sqrt {2}}}$ and ${\displaystyle b={\sqrt {2}}}$.

But if ${\displaystyle {\sqrt {2}}^{\sqrt {2}}}$ is irrational, then let

${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ and ${\displaystyle b={\sqrt {2}}}$.

Then

${\displaystyle a^{b}=\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{\left({\sqrt {2}}\cdot {\sqrt {2}}\right)}={\sqrt {2}}^{2}=2}$,

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:

The proof is non-constructive because it doesn't give specific numbers ${\displaystyle a}$ and ${\displaystyle b}$ that satisfy the theorem but only two separate possibilities, one of which must work. (Actually ${\displaystyle a={\sqrt {2}}^{\sqrt {2}}}$ 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 ${\displaystyle a={\sqrt {2}}}$ and ${\displaystyle b=\log _{2}9}$ are both easily shown to be irrational, and ${\displaystyle a^{b}=3}$; 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. 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:

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. [11] (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). [12]

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.

## Criticisms

Many modern logic systems replace the law of excluded middle with the concept of negation as failure. Instead of a proposition's being either true or false, a proposition is either true or not able to be proved true. [13] These two dichotomies only differ in logical systems that are not complete. The principle of negation as failure is used as a foundation for autoepistemic logic, and is widely used in logic programming. In these systems, the programmer is free to assert the law of excluded middle as a true fact, but it is not built-in a priori into these systems.

Mathematicians such as L. E. J. Brouwer and Arend Heyting have also contested the usefulness of the law of excluded middle in the context of modern mathematics. [14]

### In mathematical logic

In modern mathematical logic, the excluded middle has been argued to result in possible self-contradiction. It is possible in logic to make well-constructed propositions that can be neither true nor false; a common example of this is the "Liar's paradox", [15] the statement "this statement is false", which is argued to itself be neither true nor false. The law of excluded middle still holds here as the negation of this statement "This statement is not false", can be assigned true. In set theory, such a self-referential paradox can be constructed by examining the set "the set of all sets that do not contain themselves". This set is unambiguously defined, but leads to a Russell's paradox: [16] [17] does the set contain, as one of its elements, itself? However, in the modern Zermelo–Fraenkel set theory, this type of contradiction is no longer admitted. Furthermore, paradoxes of self reference can be constructed without even invoking negation at all, as in Curry's paradox.[ citation needed ]

## Analogous laws

Some systems of logic have different but analogous laws. For some finite n-valued logics, there is an analogous law called the law of excluded n+1th. If negation is cyclic and "∨" is a "max operator", then the law can be expressed in the object language by (P ∨ ~P ∨ ~~P ∨ ... ∨ ~...~P), where "~...~" represents n−1 negation signs and "∨ ... ∨" n−1 disjunction signs. It is easy to check that the sentence must receive at least one of the n truth values (and not a value that is not one of the n).

Other systems reject the law entirely.[ specify ]

## Footnotes

1. "Laws of thought". Encyclopedia Britannica. Retrieved 20 March 2021.
2. "Realism - Metaphysical realism and objective truth". Encyclopedia Britannica. Retrieved 20 March 2021.
3. Tomassi, Paul (1999). Logic. Routledge. p. 124. ISBN   978-0-415-16696-6.
4. Geach p. 74
5. On Interpretation, c. 9
6. Metaphysics 2, 996b 26–30
7. Metaphysics 7, 1011b 26–27
8. Alfred North Whitehead, Bertrand Russell (1910), Principia Mathematica, Cambridge, p. 105
9. The original symbol as used by Reichenbach is an upside down V, nowadays used for AND. The AND for Reichenbach is the same as that used in Principia Mathematica – a "dot" cf p. 27 where he shows a truth table where he defines "a.b". Reichenbach defines the exclusive-or on p. 35 as "the negation of the equivalence". One sign used nowadays is a circle with a + in it, i.e. ⊕ (because in binary, a ⊕ b yields modulo-2 addition – addition without carry). Other signs are ≢ (not identical to), or ≠ (not equal to).
10. This well-known example of a non-constructive proof depending on the law of excluded middle can be found in many places, for example: Megill, Norman. Metamath: A Computer Language for Pure Mathematics. footnote on p. 17. and Davis 2000:220, footnote 2.
11. 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".
12. For more about the conflict between the intuitionists (e.g. Brouwer) and the formalists (Hilbert) see Foundations of mathematics and Intuitionism.
13. Clark, Keith (1978). Logic and Data Bases (PDF). Springer-Verlag. pp. 293–322 (Negation as a failure). doi:10.1007/978-1-4684-3384-5_11.
14. Detlefsen, Michael (January 1992). "Proof and Knowledge in Mathematics" by Michael Detlefsen. ISBN   9780415068055.
15. Graham Priest, "Paradoxical Truth", The New York Times, November 28, 2010.
16. Kevin C. Klement, "Russell's Paradox". Internet Encyclopedia of Philosophy .
17. Priest, Graham (1983). "The Logical Paradoxes and the Law of Excluded Middle". The Philosophical Quarterly. 33 (131): 160–165. doi:10.2307/2218742. JSTOR   2218742.

## Related Research Articles

In logic, a logical connective is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

In the philosophy of mathematics, intuitionism, or neointuitionism, is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality. That is, logic and mathematics are not considered analytic activities wherein deep properties of objective reality are revealed and applied, but are instead considered the application of internally consistent methods used to realize more complex mental constructs, regardless of their possible independent existence in an objective reality.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

In the philosophy of mathematics, constructivism asserts that it is necessary to find a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove the existence of a mathematical object without "finding" that object explicitly, by assuming its non-existence and then deriving a contradiction from that assumption. Such a proof by contradiction might be called non-constructive, and a constructivist might reject it. The constructive viewpoint involves a verificational interpretation of the existential quantifier, which is at odds with its classical interpretation.

In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known as indirect proof, proof by assuming the opposite, and reductio ad impossibile.

In mathematical logic, Russell's paradox is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains an unrestricted comprehension principle leads to contradictions. The paradox had already been discovered independently in 1899 by the German mathematician Ernst Zermelo. However, Zermelo did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other academics at the University of Göttingen. At the end of the 1890s, Georg Cantor – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction, which he told Hilbert and Richard Dedekind by letter.

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.

In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's law of noncontradiction states that "It is impossible that the same thing can at the same time both belong and not belong to the same object and in the same respect."

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics. In this latter sense, the distinction between foundations of mathematics and philosophy of mathematics turns out to be quite vague. Foundations of mathematics can be conceived as the study of the basic mathematical concepts and how they form hierarchies of more complex structures and concepts, especially the fundamentally important structures that form the language of mathematics also called metamathematical concepts, with an eye to the philosophical aspects and the unity of mathematics. The search for foundations of mathematics is a central question of the philosophy of mathematics; the abstract nature of mathematical objects presents special philosophical challenges.

In mathematics, a Heyting algebra is a bounded lattice equipped with a binary operation ab of implication such that ≤ b is equivalent to c ≤. From a logical standpoint, AB is by this definition the weakest proposition for which modus ponens, the inference rule AB, AB, is sound. Like Boolean algebras, Heyting algebras form a variety axiomatizable with finitely many equations. Heyting algebras were introduced by Arend Heyting (1930) to formalize intuitionistic logic.

In the philosophy of mathematics, logicism is a programme comprising one or more of the theses that — for some coherent meaning of 'logic' — mathematics is an extension of logic, some or all of mathematics is reducible to logic, or some or all of mathematics may be modelled in logic. Bertrand Russell and Alfred North Whitehead championed this programme, initiated by Gottlob Frege and subsequently developed by Richard Dedekind and Giuseppe Peano.

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof, which proves the existence of a particular kind of object without providing an example. For avoiding confusion with the stronger concept that follows, such a constructive proof is sometimes called an effective proof.

In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition A is logically equivalent to not (not-A), or by the formula A ≡ ~(~A) where the sign ≡ expresses logical equivalence and the sign ~ expresses negation.

In classical logic, intuitionistic logic and similar logical systems, the principle of explosion, or the principle of Pseudo-Scotus, is the law according to which any statement can be proven from a contradiction. That is, once a contradiction has been asserted, any proposition can be inferred from it; this is known as deductive explosion.

In the mathematical philosophy, the pre-intuitionists were a small but influential group who informally shared similar philosophies on the nature of mathematics. The term itself was used by L. E. J. Brouwer, who in his 1951 lectures at Cambridge described the differences between intuitionism and its predecessors:

Of a totally different orientation [from the "Old Formalist School" of Dedekind, Cantor, Peano, Zermelo, and Couturat, etc.] was the Pre-Intuitionist School, mainly led by Poincaré, Borel and Lebesgue. These thinkers seem to have maintained a modified observational standpoint for the introduction of natural numbers, for the principle of complete induction [...] For these, even for such theorems as were deduced by means of classical logic, they postulated an existence and exactness independent of language and logic and regarded its non-contradictority as certain, even without logical proof. For the continuum, however, they seem not to have sought an origin strictly extraneous to language and logic.

The laws of thought are fundamental axiomatic rules upon which rational discourse itself is often considered to be based. The formulation and clarification of such rules have a long tradition in the history of philosophy and logic. Generally they are taken as laws that guide and underlie everyone's thinking, thoughts, expressions, discussions, etc. However, such classical ideas are often questioned or rejected in more recent developments, such as intuitionistic logic, dialetheism and fuzzy logic.

The axiom of reducibility was introduced by Bertrand Russell in the early 20th century as part of his ramified theory of types. Russell devised and introduced the axiom in an attempt to manage the contradictions he had discovered in his analysis of set theory.

In a controversy over the foundations of mathematics, in twentieth-century mathematics, L. E. J. Brouwer, a proponent of the constructivist school of intuitionism, opposed David Hilbert, a proponent of formalism. The debate concerned fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics. Much of the controversy took place while both were involved with the prestigious Mathematische Annalen journal, with Hilbert as editor-in-chief and Brouwer as a member of its editorial board.

## References

• Aquinas, Thomas, "Summa Theologica", Fathers of the English Dominican Province (trans.), Daniel J. Sullivan (ed.), vols. 19–20 in Robert Maynard Hutchins (ed.), Great Books of the Western World , Encyclopædia Britannica, Inc., Chicago, IL, 1952. Cited as GB 19–20.
• Aristotle, "Metaphysics", W.D. Ross (trans.), vol. 8 in Robert Maynard Hutchins (ed.), Great Books of the Western World , Encyclopædia Britannica, Inc., Chicago, IL, 1952. Cited as GB 8. 1st published, W.D. Ross (trans.), The Works of Aristotle, Oxford University Press, Oxford, UK.
• Martin Davis 2000, Engines of Logic: Mathematicians and the Origin of the Computer, W. W. Norton & Company, NY, ISBN   0-393-32229-7 pbk.
• Dawson, J., Logical Dilemmas, The Life and Work of Kurt Gödel, A.K. Peters, Wellesley, MA, 1997.
• van Heijenoort, J., From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977.
• Luitzen Egbertus Jan Brouwer, 1923, On the significance of the principle of excluded middle in mathematics, especially in function theory [reprinted with commentary, p. 334, van Heijenoort]
• Andrei Nikolaevich Kolmogorov, 1925, On the principle of excluded middle, [reprinted with commentary, p. 414, van Heijenoort]
• Luitzen Egbertus Jan Brouwer, 1927, On the domains of definitions of functions,[reprinted with commentary, p. 446, van Heijenoort] Although not directly germane, in his (1923) Brouwer uses certain words defined in this paper.
• Luitzen Egbertus Jan Brouwer, 1927(2), Intuitionistic reflections on formalism,[reprinted with commentary, p. 490, van Heijenoort]
• Stephen C. Kleene 1952 original printing, 1971 6th printing with corrections, 10th printing 1991, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY, ISBN   0-7204-2103-9.
• Kneale, W. and Kneale, M., The Development of Logic, Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975.
• Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press 1962 (Second Edition of 1927, reprinted). Extremely difficult because of arcane symbolism, but a must-have for serious logicians.
• Bertrand Russell, An Inquiry Into Meaning and Truth. The William James Lectures for 1940 Delivered at Harvard University.
• Bertrand Russell, The Problems of Philosophy, With a New Introduction by John Perry, Oxford University Press, New York, 1997 edition (first published 1912). Very easy to read: Russell was a wonderful writer.
• Bertrand Russell, The Art of Philosophizing and Other Essays, Littlefield, Adams & Co., Totowa, NJ, 1974 edition (first published 1968). Includes a wonderful essay on "The Art of drawing Inferences".
• Hans Reichenbach, Elements of Symbolic Logic, Dover, New York, 1947, 1975.
• Tom Mitchell, Machine Learning, WCB McGraw-Hill, 1997.
• Constance Reid, Hilbert, Copernicus: Springer-Verlag New York, Inc. 1996, first published 1969. Contains a wealth of biographical information, much derived from interviews.
• Bart Kosko, Fuzzy Thinking: The New Science of Fuzzy Logic, Hyperion, New York, 1993. Fuzzy thinking at its finest. But a good introduction to the concepts.
• David Hume, An Inquiry Concerning Human Understanding, reprinted in Great Books of the Western World Encyclopædia Britannica, Volume 35, 1952, p. 449 ff. This work was published by Hume in 1758 as his rewrite of his "juvenile" Treatise of Human Nature: Being An attempt to introduce the experimental method of Reasoning into Moral Subjects Vol. I, Of The Understanding first published 1739, reprinted as: David Hume, A Treatise of Human Nature, Penguin Classics, 1985. Also see: David Applebaum, The Vision of Hume, Vega, London, 2001: a reprint of a portion of An Inquiry starts on p. 94 ff