law of excluded middle
   HOME

TheInfoList



OR:

In
logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science investigating h ...

logic
, the law of excluded middle (or the principle of excluded middle) states that for every
proposition In logic and linguistics, a proposition is the meaning of a declarative sentence (linguistics), sentence. In philosophy, "Meaning (philosophy), meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same me ...
, either this proposition or its
negation In logic, negation, also called the logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted ...

negation
is
true True most commonly refers to truth, the state of being in congruence with fact or reality. True may also refer to: Places * True, West Virginia, an unincorporated community in the United States * True, Wisconsin, a town in the United States * Tr ...
. It is one of the so-called three laws of thought, along with the law of noncontradiction, and the
law of identity In logic, the law of identity states that each thing is identical with itself. It is the first of the historical Law of thought#The three traditional laws, three laws of thought, along with the law of noncontradiction, and the law of excluded mid ...
. However, no system of logic is built on just these laws, and none of these laws provides
inference rules In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their Syntax (logic), syntax, and returns a conclusion (or multiple-conclusion logic, ...
, such as
modus ponens In propositional calculus, propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo wiktionary:ponens, ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a Deducti ...

modus ponens
or
De Morgan's laws In propositional calculus, propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both Validity (logic), valid rule of inference, rules of inference. They are na ...
. The law is also known as the law (or principle) of the excluded third, in
Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally a dialect spoken in the lower Tiber area (then known as Latium) around present-day Rome, but through ...

Latin
''principium tertii exclusi''. Another Latin designation for this law is ''tertium non datur'': "no third ossibilityis given". It is a tautology. The principle should not be confused with the semantical
principle of bivalence In logic, the semantic principle (or law) of bivalence states that every declarative sentence expressing a proposition (of a theory under inspection) has exactly one truth value, either Truth, true or false (logic), false. A logic satisfying thi ...
, 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.


History


Aristotle

The earliest known formulation is in Aristotle's discussion of the
principle of non-contradiction In logic, the law of non-contradiction (LNC) (also known as the law of contradiction, principle of non-contradiction (PNC), or the principle of contradiction) states that contradictory propositions cannot both be true in the same sense at the sa ...
, first proposed in '' On Interpretation,'' 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. He also states it as a principle in the ''
Metaphysics Metaphysics is the branch of philosophy that studies the fundamental nature of reality, the first principles of being, identity and change, space and time, causality, necessity, and possibility. It includes questions about the nature of conscio ...
'' book 3, saying that it is necessary in every case to affirm or deny, and that it is impossible that there should be anything between the two parts of a contradiction.
Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical Greece, Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatet ...

Aristotle
wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the facts themselves: 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


Bertrand Russell and ''Principia Mathematica''

The principle was stated as a
theorem In mathematics, a theorem is a statement (logic), statement that has been Mathematical proof, proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the th ...
of
propositional logic 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 (which can be true or false) and relations b ...
by Russell and Whitehead in ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'' as: \mathbf. \ \ \vdash . \ p \ \vee \thicksim p. So just what is "truth" and "falsehood"? At the opening ''PM'' quickly announces some definitions: 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": 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): 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 The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
,'' 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 ~''p'' ∨ ''p'' "This is the Law of excluded middle" (''PM'', p. 101). The proof of ✸2.1 is roughly as follows: "primitive idea" 1.08 defines ''p'' → ''q'' = ~''p'' ∨ ''q''. Substituting ''p'' for ''q'' in this rule yields ''p'' → ''p'' = ~''p'' ∨ ''p''. Since ''p'' → ''p'' is true (this is Theorem 2.08, which is proved separately), then ~''p'' ∨ ''p'' 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'' ∨ ~ (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.)


Reichenbach

It is correct, at least for bivalent logic—i.e. it can be seen with a
Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (m ...
—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 ::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 \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 Hermann Klaus Hugo Weyl, (; 9 November 1885 – 8 December 1955) was a German mathematician, theoretical physicist and philosopher. Although much of his working life was spent in Zürich, Switzerland, and then Princeton, New Jersey, he is assoc ...

Hermann Weyl
and L. E. J. Brouwer. Brouwer's philosophy, called
intuitionism In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fu ...
, started in earnest with
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a Germans, German mathematician who worked on number theory, abstract algebra, algebra and mathematical logic, logic. He criticized Georg Cantor's work on set theory, and was quoted b ...

Leopold Kronecker
in the late 1800s. Hilbert intensely disliked Kronecker's ideas: The debate had a profound effect on Hilbert. Reid indicates that Hilbert's second problem (one of
Hilbert's problems Hilbert's problems are 23 problems in mathematics published by German mathematician David Hilbert in 1900. They were all unsolved at the time, and several proved to be very influential for 20th-century mathematics. Hilbert presented ten of the pro ...
from the Second International Conference in Paris in 1900) evolved from this debate (italics in the original): ::In his second problem, ilberthad 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. The rancorous debate continued through the early 1900s into the 1920s; in 1927 Brouwer complained about "polemicizing against it ntuitionismin sneering tones" (Brouwer in van Heijenoort, p. 492). But the debate was fertile: it resulted in ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'' (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: 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 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 o ...
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 ichtigor 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) ''Kolmogorovs definition cites Hilbert's two axioms of negation
  1. ''A'' → (~''A'' → ''B'')
  2. (''A'' → ''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 xiom 5asserts 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 In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science ...
: :''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. We seek to prove that :there exist two
irrational number In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
s a and b such that a^b is rational. It is known that \sqrt is irrational (see proof). Consider the number :\sqrt^. Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and :a=\sqrt and b=\sqrt. But if \sqrt^ is irrational, then let :a=\sqrt^ and b=\sqrt. Then :a^b = \left(\sqrt^\right)^ = \sqrt^ = \sqrt^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: (Constructive proofs of the specific example above are not hard to produce; for example a=\sqrt and b=\log_2 9 are both easily shown to be irrational, and 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:
David Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...
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). Putative counterexamples to the law of excluded middle include the
liar paradox In philosophy and logic, the classical liar paradox or liar's paradox or antinomy of the liar is the statement of a liar that they are lying: for instance, declaring that "I am lying". If the liar is indeed lying, then the liar is telling the truth ...
or
Quine's paradox Quine's paradox is a paradox concerning truth values, stated by Willard Van Orman Quine. It is related to the liar paradox as a problem, and it purports to show that a sentence can be paradoxical even if it is not self-referring and does not use d ...
. Certain resolutions of these paradoxes, particularly
Graham Priest Graham Priest (born 1948) is Distinguished Professor of Philosophy at the CUNY , mottoeng = The education of free people is the hope of Mankind , budget = $3.6 billion , established = , t ...
'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. These two dichotomies only differ in logical systems that are not
complete Complete may refer to: Logic * Completeness (logic) * Complete theory, Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, ...
. The principle of negation as failure is used as a foundation for autoepistemic logic, and is widely used in
logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic prog ...
. 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 __NOTOC__ Arend Heyting (; 9 May 1898 – 9 July 1980) was a Dutch mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are conce ...
have also contested the usefulness of the law of excluded middle in the context of modern mathematics.


In mathematical logic

In modern
mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantiti ...
, 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", the statement "this statement is false", which is argued to itself be neither true nor false.
Arthur Prior Arthur Norman Prior (4 December 1914 – 6 October 1969), usually cited as A. N. Prior, was a New Zealand–born logician and philosopher. Prior (1957) founded tense logic, now also known as temporal logic, and made important contributions ...
has argued that The Paradox is not an example of a statement that cannot be true or 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 Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, ...
, 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 In mathematical logic Mathematical logic is the study of formal logic within mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are ...
: does the set contain, as one of its elements, itself? However, in the modern
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes suc ...
, 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 Curry's paradox is a paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self ...
.


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 Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history Social cycle theories are among the earliest social theories in sociology. Unlike the theory of social evolutionism, which views the evolution of society ...
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 value In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science in ...
s (and not a value that is not one of the ''n''). Other systems reject the law entirely.


See also

* : an account on the formalist-intuitionist divide around the Law of the excluded middle * ' * * * * Law of excluded middle is untrue in s such as and * * * s: a graphical syntax for propositional logic * : another way of turning intuition classical * : the application excluded middle to propositions * Non-affirming negation in the school of Buddhism, another system in which the law of excluded middle is untrue * Mathematical constructivism *
Constructive set theory Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objec ...


Footnotes


References

* Aquinas, Thomas, "
Summa Theologica The ''Summa Theologiae'' or ''Summa Theologica'' (), often referred to simply as the ''Summa'', is the best-known work of Thomas Aquinas (1225–1274), a scholasticism, scholastic theologian and Doctor of the Church. It is a compendium of all ...
", Fathers of the English Dominican Province (trans.), Daniel J. Sullivan (ed.), vols. 19–20 in
Robert Maynard Hutchins Robert Maynard Hutchins (January 17, 1899 – May 14, 1977) was an American educational philosopher. He was president (1929–1945) and chancellor (1945–1951) of the University of Chicago The University of Chicago (UChicago, Chicago, U of ...
(ed.), ''
Great Books of the Western World ''Great Books of the Western World'' is a series of books originally published in the United States The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country Continental Unit ...
'', Encyclopædia Britannica, Inc., Chicago, IL, 1952. Cited as GB 19–20. *
Aristotle Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical Greece, Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatet ...

Aristotle
, "
Metaphysics Metaphysics is the branch of philosophy that studies the fundamental nature of reality, the first principles of being, identity and change, space and time, causality, necessity, and possibility. It includes questions about the nature of conscio ...
", W.D. Ross (trans.), vol. 8 in
Robert Maynard Hutchins Robert Maynard Hutchins (January 17, 1899 – May 14, 1977) was an American educational philosopher. He was president (1929–1945) and chancellor (1945–1951) of the University of Chicago The University of Chicago (UChicago, Chicago, U of ...
(ed.), ''
Great Books of the Western World ''Great Books of the Western World'' is a series of books originally published in the United States The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country Continental Unit ...
'', 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, 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 Brouwer (also Brouwers and de Brouwer) is a Dutch and Flemish surname In some cultures, a surname, family name, or last name is the portion of one's personal name that indicates one's family, tribe or community. Practices vary by culture. The ...
, 1923, ''On the significance of the principle of excluded middle in mathematics, especially in function theory'' eprinted with commentary, p. 334, van Heijenoort* Andrei Nikolaevich
Kolmogorov Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
, 1925, ''On the principle of excluded middle'', eprinted with commentary, p. 414, van Heijenoort* Luitzen Egbertus Jan
Brouwer Brouwer (also Brouwers and de Brouwer) is a Dutch and Flemish surname In some cultures, a surname, family name, or last name is the portion of one's personal name that indicates one's family, tribe or community. Practices vary by culture. The ...
, 1927, ''On the domains of definitions of functions'', eprinted with commentary, p. 446, van HeijenoortAlthough not directly germane, in his (1923) Brouwer uses certain words defined in this paper. * Luitzen Egbertus Jan
Brouwer Brouwer (also Brouwers and de Brouwer) is a Dutch and Flemish surname In some cultures, a surname, family name, or last name is the portion of one's personal name that indicates one's family, tribe or community. Practices vary by culture. The ...
, 1927(2), ''Intuitionistic reflections on formalism'', eprinted 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, . * Kneale, W. and Kneale, M., ''The Development of Logic'', Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975. *
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathemat ...
and
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
, ''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 Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
, ''An Inquiry Into Meaning and Truth''. The William James Lectures for 1940 Delivered at Harvard University. *
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
, ''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 Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
, ''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 Hans Reichenbach (September 26, 1891 – April 9, 1953) was a leading Philosophy of science, philosopher of science, educator, and proponent of Logical positivism, logical empiricism. He was influential in the areas of science, education, and of ...
, ''Elements of Symbolic Logic'', Dover, New York, 1947, 1975. * Tom Mitchell, ''Machine Learning'', WCB McGraw-Hill, 1997. *
Constance Reid Constance Bowman Reid (January 3, 1918 – October 14, 2010) was the author of several biographies of mathematicians and popular books about mathematics. She received several awards for mathematical exposition. She was not a mathematician but ...
, ''Hilbert'', Copernicus: Springer-Verlag New York, Inc. 1996, first published 1969. Contains a wealth of biographical information, much derived from interviews. *
Bart Kosko Bart Andrew Kosko (born February 7, 1960) is a writer and professor of electrical engineering and law at the University of Southern California (USC). He is a researcher and popularizer of fuzzy logic, neural networks, and noise, and author of ...
, ''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 David Hume (; born David Home; 7 May 1711 New Style, NS (26 April 1711 Old Style, OS) – 25 August 1776)Maurice Cranston, Cranston, Maurice, and T. E. Jessop, Thomas Edmund Jessop. 2020
999 999 or triple nine most often refers to: * 999 (emergency telephone number) 999 is an official emergency telephone number in a number of countries which allows the caller to contact emergency services for urgent assistance. Countries and territ ...
avid Hume" ''Encyclopædia Britannica''. Retrieve ...
, ''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


External links


"Contradiction" entry
in the
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with scholarly peer review, peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by S ...
{{authority control Classical logic Articles containing proofs Theorems in propositional logic