In

PDF p.19

Proof by Contradiction

from Larry W. Cusick'

Reductio ad Absurdum

Internet Encyclopedia of Philosophy; ISSN 2161-0002 {{DEFAULTSORT:Proof By Contradiction Mathematical proofs Methods of proof Theorems in propositional logic

logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premi ...

and mathematics, proof by contradiction is a form of proof
Proof most often refers to:
* Proof (truth), argument or sufficient evidence for the truth of a proposition
* Alcohol proof, a measure of an alcoholic drink's strength
Proof may also refer to:
Mathematics and formal logic
* Formal proof, a co ...

that establishes the truth
Truth is the property of being in accord with fact or reality.Merriam-Webster's Online Dictionarytruth 2005 In everyday language, truth is typically ascribed to things that aim to represent reality or otherwise correspond to it, such as beliefs ...

or the validity of a proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...

, by showing that assuming the proposition to be false leads to a contradiction
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' ...

. Proof by contradiction is also known as indirect proof, proof by assuming the opposite, and ''reductio ad impossibile''. It is an example of the weaker logical refutation ''reductio ad absurdum
In logic, (Latin for "reduction to absurdity"), also known as (Latin for "argument to absurdity") or ''apagogical arguments'', is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to absu ...

''.
A mathematical proof employing proof by contradiction usually proceeds as follows:
#The proposition to be proved is ''P''.
#We assume ''P'' to be false, i.e., we assume ''¬P''.
#It is then shown that ''¬P'' implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions, ''Q'' and ''¬Q'', and appealing to the Law of noncontradiction
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 ...

.
#Since assuming ''P'' to be false leads to a contradiction, it is concluded that ''P'' is in fact true.
An important special case is the existence proof by contradiction: in order to demonstrate the existence of an object satisfying a given property, we assume that no such object exists and derive a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof
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 (also known as an existe ...

as universally valid.
Formalization

The principle may be formally expressed as thepropositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional fo ...

''¬¬P ⇒ P'', equivalently ''(¬P ⇒ ⊥) ⇒ P'', which reads: "If assuming ''P'' to be false implies falsehood, then ''P'' is true."
In natural deduction In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning. This contrasts with Hilbert-style systems, which instead use a ...

the principle takes the form of the rule of inference
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, and returns a conclusion (or conclusions). For example, the rule of in ...

: $\backslash cfrac$
which reads: "If $\backslash lnot\backslash lnot\; P$ is proved, then $P$ may be concluded."
In sequent calculus
In mathematical logic, sequent calculus is a style of formal logical argumentation in which every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology. Each conditional tautology i ...

the principle is expressed by the sequent
: $\backslash Gamma,\; \backslash lnot\backslash lnot\; P\; \backslash vdash\; P,\; \backslash Delta$
which reads: "Hypotheses $\backslash Gamma$ ''and'' $\backslash lnot\backslash lnot\; P$ entail the conclusion $P$ ''or'' $\backslash Delta$."
Justification

Inclassical logic
Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this class ...

the principle may be justified by the examination of the truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...

of the proposition ''¬¬P ⇒ P'', which demonstrates it to be a tautology:
Another way to justify the principle is to derive it from the Law of the excluded middle
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. It is one of the so-called three laws of thought, along with the law of noncontradi ...

, as follows. We assume ''¬¬P'' and seek to prove ''P''. By the law of excluded middle ''P'' either holds or it does not:
# if ''P'' holds, then of course ''P'' holds.
# if ''¬P'' holds, then we derive falsehood by applying the law of noncontradiction
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 ...

to ''¬P'' and ''¬¬P'', after which the principle of explosion
In classical logic, intuitionistic logic and similar logical systems, the principle of explosion (, 'from falsehood, anything ollows; or ), or the principle of Pseudo-Scotus, is the law according to which any statement can be proven from a c ...

allows us to conclude ''P''.
In either case, we established ''P''. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.
In classical sequent calculus LK proof by contradiction is derivable from the 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, and returns a conclusion (or conclusions). For example, the rule of in ...

for negation:
: $\backslash cfrac\; \backslash ;\; (L)$
Relationship with other proof techniques

Refutation by contradiction

Proof by contradiction is frequently confused with the similar-looking refutation by contradiction, a.k.a. proof of negation, which states that ''¬P'' is proved as follows: # The proposition to be proved is ''¬P''. # Assume ''P''. # Derive falsehood. # Conclude ''¬P''. In contrast, proof by contradiction proceeds as follows: # The proposition to be proved is ''P''. # Assume ''¬P''. # Derive falsehood. # Conclude ''P''. Refutation by contradiction applies only when the proposition to be proved is negated, whereas proof by contradiction may be applied to any proposition whatsoever. Confusingly, in mathematical practice, both proof by contradiction and refutation by contradiction are referred to as "proof by contradiction", as they proceed in a similar manner. However, they are not equivalent—unless we assume the law of excluded middle, in which case they become equivalent.Law of non-contradiction

Thelaw of noncontradiction
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 ...

was first formalized as a metaphysical principle by Aristotle
Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of ...

. It states that a proposition and its negation cannot both be true. Equivalently, it states that a proposition cannot be both true and false. Formally the law of non-contradiction is written as ''¬(Q ∧ ¬Q)'' and read as "it is not the case that a proposition is both true and false".
The law of non-contradiction neither follows nor is implied by the principle of Proof by contradiction.
Law of the excluded middle

Proof by contradiction is equivalent to thelaw of the excluded middle
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. It is one of the so-called three laws of thought, along with the law of noncontradi ...

, also first formulated by Aristotle, which states that either an assertion or its negation is true, ''P ∨ ¬P''.
Combined with the principle of noncontradiction, this means that exactly one of ''P'' and ''¬P'' is true.
Proof by contradiction in intuitionistic logic

Inintuitionistic 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 ...

proof by contradiction is not generally valid, although some particular instances can be derived. In contrast, proof of negation and principle of noncontradiction are both intuitionistically valid.
Brouwer–Heyting–Kolmogorov interpretation In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer and Arend Heyting, and independently by Andrey Kolmogorov. It is also sometimes called the re ...

of proof by contradiction gives the following intuitionistic validity condition:
:"If there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true."
If we take "method" to mean algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

, then the condition is not acceptable, as it would allow us to solve the Halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...

. To see how, consider the statement ''H(M)'' stating "Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algo ...

''M'' halts or does not halt". Its negation ''¬H(M)'' states that "''M'' neither halts nor does not halt", which is false by the law of noncontradiction
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 ...

(which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machine ''M'' halts, thereby violating the (intuitionistically valid) proof of non-solvability of the Halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...

.
A proposition ''P'' which satisfies $\backslash lnot\backslash lnot\; P\; \backslash Rightarrow\; P$ is known as a ''¬¬-stable proposition''. Thus in intuitionistic logic proof by contradiction is not universally valid, but can only be applied to the ¬¬-stable propositions. An instance of such a proposition is a decidable one, i.e., satisfying $P\; \backslash lor\; \backslash lnot\; P$. Indeed, the above proof that the law of excluded middle implies proof by contradiction can be repurposed to show that a decidable proposition is ¬¬-stable. A typical example of a decidable proposition is a statement that can be checked by direct computation, such as "$n$ is prime" or "$a$ divides $b$".
Examples of proofs by contradiction

Euclid's Elements

An early occurrence of proof by contradiction can be found inEuclid's Elements
The ''Elements'' ( grc, Στοιχεῖα ''Stoikheîa'') is a mathematical treatise consisting of 13 books attributed to the ancient Greek mathematician Euclid in Alexandria, Ptolemaic Egypt 300 BC. It is a collection of definitions, postul ...

, Book 1, Proposition 6:
: If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another.
The proof proceeds by assuming that the opposite angles are not equal, and derives a contradiction.
Hilbert's Nullstellensatz

An influential proof by contradiction was given byDavid 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 ...

. His
Nullstellensatz states:
: If $f\_1,\backslash ldots,f\_k$ are polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...

s in indeterminates with complex coefficients, which have no common complex zeros, then there are polynomials $g\_1,\backslash ldots,\; g\_k$ such that $f\_1g\_1+\backslash ldots\; +f\_kg\_k=1.$
Hilbert proved the statement by assuming that there are no such polynomials $g\_1,\; \backslash ldots,\; g\_k$ and derived a contradiction.
Infinitude of primes

Euclid's theorem
Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work '' Elements''. There are several proofs of the theorem.
Euclid's proof
Euclid off ...

states that there are infinitely many primes. In Euclid's Elements
The ''Elements'' ( grc, Στοιχεῖα ''Stoikheîa'') is a mathematical treatise consisting of 13 books attributed to the ancient Greek mathematician Euclid in Alexandria, Ptolemaic Egypt 300 BC. It is a collection of definitions, postul ...

the theorem is stated in Book IX, Proposition 20:
: Prime numbers are more than any assigned multitude of prime numbers.
Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction.
If we formally express Euclid's theorem as saying that for every natural number $n$ there is a prime bigger than it, then we employ proof by contradiction, as follows.
Given any number $n$, we seek to prove that there is a prime larger than $n$. Suppose to the contrary that no such ''p'' exists (an application of proof by contradiction). Then all primes are smaller than or equal to $n$, and we may form the list $p\_1,\; \backslash ldots,\; p\_k$ of them all. Let $P\; =\; p\_1\; \backslash cdot\; \backslash ldots\; \backslash cdot\; p\_k$ be the product of all primes and $Q\; =\; P\; +\; 1$. Because $Q$ is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say $p\_i$. Now both $P$ and $Q$ are divisible by $p\_i$, hence so is their difference $Q\; -\; P\; =\; 1$, but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than $n$
Examples of refutations by contradiction

Because proof by contradiction is frequently conflated with refutation by contradiction, the following are often erroneously claimed to be proofs by contradiction, but they really are refutations by contradiction (and therefore intuitionistically valid).Infinitude of primes

Let us take a second look atEuclid's theorem
Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work '' Elements''. There are several proofs of the theorem.
Euclid's proof
Euclid off ...

– Book IX, Proposition 20:
: Prime numbers are more than any assigned multitude of prime numbers.
We may read the statement as saying that for every finite list of primes, there is another prime not on that list,
which is arguably closer to and in the same spirit as Euclid's original formulation. In this case Euclid's proof applies refutation by contradiction at one step, as follows.
Consider any finite list of prime numbers $p\_1,\; \backslash ldots,\; p\_n$. It will be shown that at least one additional prime number not in this list exists. Let $P\; =\; p\_1\; \backslash cdot\; p\_2\; \backslash cdots\; p\_n$ be the product of all the prime numbers in the list and $Q\; =\; P\; +\; 1$. Then $Q$ is either prime or not:
* If $Q$ is prime, then $Q$ itself is a prime not in the list, as it is greater than all primes in the list.
* If $Q$ is not prime, then it has a prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...

$p$. We claim that $p$ is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then $p$ would divide $P$, and because it also divides $Q$ it divides their difference $Q\; -\; P\; =\; 1$. This gives a contradiction, since no prime number divides 1. Thus $p$ is a prime number not in the list.
Irrationality of the square root of 2

The classic proof that the square root of 2 is irrational is a refutation by contradiction. Indeed, we set out to prove the negation ''¬ ∃ a, b ∈ $\backslash mathbb$ . a/b = '' by assuming that there exist natural numbers ''a'' and ''b'' whose ratio is the square root of two, and derive a contradiction.Proof by infinite descent

Proof by infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold fo ...

is a method of proof whereby a smallest object with desired property is shown not to exist as follows:
* Assume that there is a smallest object with the desired property.
* Demonstrate that an even smaller object with the desired property exists, thereby deriving a contradiction.
Such a proof is not a proof by contradiction but once again a refutation by contradiction. A typical example is the proof of the proposition "there is no smallest positive rational number": assume there is a smallest positive rational number ''q'' and derive a contradiction by observing that is even smaller than ''q'' and still positive.
Russell's paradox

Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) 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 a ...

, stated set-theoretically as "there is no set whose elements are precisely those sets that do not contain themselves", is a negated statement whose usual proof is a refutation by contradiction.
Notation

Proofs by contradiction sometimes end with the word "Contradiction!".Isaac Barrow
Isaac Barrow (October 1630 – 4 May 1677) was an English Christian theologian and mathematician who is generally given credit for his early role in the development of infinitesimal calculus; in particular, for proof of the fundamental theorem ...

and Baermann used the notation Q.E.A., for "''quod est absurdum''" ("which is absurd"), along the lines of Q.E.D., but this notation is rarely used today. A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley. Others sometimes used include a pair of opposing arrows (as $\backslash rightarrow\backslash !\backslash leftarrow$ or $\backslash Rightarrow\backslash !\backslash Leftarrow$), struck-out arrows ($\backslash nleftrightarrow$), a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※), or $\backslash times\backslash !\backslash !\backslash !\backslash !\backslash times$.The Comprehensive LaTeX Symbol List, pg. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
Hardy's view

G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...

described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...

, ''A Mathematician's Apology
''A Mathematician's Apology'' is a 1940 essay by British mathematician G. H. Hardy, which offers a defence of the pursuit of mathematics. Central to Hardy's " apology" — in the sense of a formal justification or defence (as in Plato's '' A ...

; Cambridge University Press, 1992. . PDF p.19

See also

*Law of excluded middle
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. It is one of the so-called three laws of thought, along with the law of noncontrad ...

*Law of noncontradiction
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 ...

* Proof by exhaustion
*Proof by infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold fo ...

*Modus tollens
In propositional logic, ''modus tollens'' () (MT), also known as ''modus tollendo tollens'' (Latin for "method of removing by taking away") and denying the consequent, is a deductive argument form and a rule of inference. ''Modus tollens'' ...

References

Further reading and external links

*Proof by Contradiction

from Larry W. Cusick'

Reductio ad Absurdum

Internet Encyclopedia of Philosophy; ISSN 2161-0002 {{DEFAULTSORT:Proof By Contradiction Mathematical proofs Methods of proof Theorems in propositional logic