Proof by contradiction

Inlogic,proof by contradictionis a form ofproofthat establishes thetruthor thevalidityof aproposition,by showing that assuming the proposition to be false leads to acontradiction. Although it is quite freely used in mathematical proofs, not everyschool of mathematical thoughtaccepts this kind ofnonconstructive proofas universally valid.

More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved. In this general sense, proof by contradiction is also known asindirect proof,proof by assuming the opposite,andreductio ad impossibile.

A mathematical proof employing proof by contradiction usually proceeds as follows:

1. The proposition to be proved isP.
2. We assumePto be false, i.e., we assume¬P.
3. It is then shown that¬Pimplies falsehood. This is typically accomplished by deriving two mutually contradictory assertions,Qand¬Q,and appealing to thelaw of noncontradiction.
4. Since assumingPto be false leads to a contradiction, it is concluded thatPis in fact true.

An important special case is theexistence proofby contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.

Formalization

The principle may be formally expressed as thepropositional formula¬¬P ⇒ P,equivalently(¬P ⇒ ⊥) ⇒ P,which reads: "If assumingPto be false implies falsehood, thenPis true. "

Innatural deductionthe principle takes the form of therule of inference

${\cfrac {\vdash \lnot \lnot P}{\vdash P}}$

which reads: "If$\lnot \lnot P$is proved, then$P$may be concluded. "

Insequent calculusthe principle is expressed by the sequent

$\Gamma,\lnot \lnot P\vdash P,\Delta$

which reads: "Hypotheses$\Gamma$and$\lnot \lnot P$entail the conclusion$P$or$\Delta$."

Justification

Inclassical logicthe principle may be justified by the examination of thetruth tableof the proposition¬¬P ⇒ P,which demonstrates it to be atautology:

p	¬p	¬¬p	¬¬p ⇒ p
T	F	T	T
F	T	F	T

Another way to justify the principle is to derive it from thelaw of the excluded middle,as follows. We assume¬¬Pand seek to proveP.By the law of excluded middlePeither holds or it does not:

1. ifPholds, then of coursePholds.
2. if¬Pholds, then we derive falsehood by applying thelaw of noncontradictionto¬Pand¬¬P,after which theprinciple of explosionallows us to concludeP.

In either case, we establishedP.It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.

Inclassical sequent calculus LKproof by contradiction is derivable from theinference rulesfor negation:

${\cfrac {{\cfrac {{\cfrac {\ }{\Gamma,P\vdash P,\Delta }}\;(I)}{\Gamma,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)$

Relationship with other proof techniques

Refutation by contradiction

Proof by contradiction is similar torefutation by contradiction,also known asproof of negation,which states that¬Pis proved as follows:

1. The proposition to be proved is¬P.
2. AssumeP.
3. Derive falsehood.
4. Conclude¬P.

In contrast, proof by contradiction proceeds as follows:

1. The proposition to be proved isP.
2. Assume¬P.
3. Derive falsehood.
4. ConcludeP.

Formally these are not the same, as refutation by contradiction applies only when the proposition to be proved is negated, whereas proof by contradiction may be applied to any proposition whatsoever.In classical logic, where$P$and$\neg \neg P$may be freely interchanged, the distinction is largely obscured. Thus in mathematical practice, both principles are referred to as "proof by contradiction".

Law of the excluded middle

Main article:Law of excluded middle

Proof by contradiction is equivalent to thelaw of the excluded middle,first formulated byAristotle,which states that either an assertion or its negation is true,P ∨ ¬P.

Law of non-contradiction

Thelaw of noncontradictionwas first stated as a metaphysical principle byAristotle.It posits that a proposition and its negation cannot both be true, or equivalently, that a proposition cannot be both true and false. Formally the law of non-contradiction is written as¬(P ∧ ¬P)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.

The laws of excluded middle and non-contradiction together mean that exactly one ofPand¬Pis true.

Proof by contradiction in intuitionistic logic

Inintuitionistic logicproof 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 interpretationof 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 meanalgorithm,then the condition is not acceptable, as it would allow us to solve theHalting problem.To see how, consider the statementH(M)stating "Turing machineMhalts or does not halt ". Its negation¬H(M)states that "Mneither halts nor does not halt ", which is false by thelaw of noncontradiction(which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machineMhalts, thereby violating the (intuitionistically valid) proof of non-solvability of theHalting problem.

A propositionPwhich satisfies$\lnot \lnot P\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\lor \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,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 sides are not equal, and derives a contradiction.

Hilbert's Nullstellensatz

An influential proof by contradiction was given byDavid Hilbert.His Nullstellensatzstates:

If$f_{1},\ldots,f_{k}$arepolynomialsinnindeterminates withcomplexcoefficients, which have no common complexzeros,then there are polynomials$g_{1},\ldots,g_{k}$such that$f_{1}g_{1}+\ldots +f_{k}g_{k}=1.$

Hilbert proved the statement by assuming that there are no such polynomials$g_{1},\ldots,g_{k}$and derived a contradiction.

Infinitude of primes

Euclid's theoremstates that there are infinitely many primes. InEuclid's Elementsthe 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 suchpexists (an application of proof by contradiction). Then all primes are smaller than or equal to$n$,and we may form the list$p_{1},\ldots,p_{k}$of them all. Let$P=p_{1}\cdot \ldots \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

The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).

Infinitude of primes

Let us take a second look atEuclid's theorem– 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 caseEuclid's proofapplies refutation by contradiction at one step, as follows.

Given any finite list of prime numbers$p_{1},\ldots,p_{n}$,it will be shown that at least one additional prime number not in this list exists. Let$P=p_{1}\cdot p_{2}\cdots p_{n}$be the product of all the listed primes and$p$aprime factorof$P+1$,possibly$P+1$itself. 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 both$P$and$P+1$,therefore also their difference, which is$1$.This gives a contradiction, since no prime number divides 1.

Irrationality of the square root of 2

The classicproof that the square root of 2 is irrationalis a refutation by contradiction. Indeed, we set out to prove the negation¬ ∃ a, b ∈$\mathbb {N}$.a/b =√2by assuming that there exist natural numbersaandbwhose ratio is the square root of two, and derive a contradiction.

Proof by infinite descent

Proof by infinite descentis 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 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 numberqand derive a contradiction by observing thatq/2is even smaller thanqand still positive.

Russell's paradox

Russell's paradox,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 Barrowand Baermann used the notation Q.E.A., for "quod est absurdum"(" which is absurd "), along the lines ofQ.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 ofopposing arrows(as$\rightarrow \!\leftarrow$or$\Rightarrow \!\Leftarrow$),struck-out arrows ($\nleftrightarrow$),a stylized form of hash (such as U+2A33: ⨳),or the "reference mark" (U+203B: ※),or$\times \!\!\!\!\times$.

Hardy's view

G. H. Hardydescribed proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than anychess gambit:a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game. "

Automated theorem proving

Inautomated theorem provingthe method ofresolutionis based on proof by contradiction. That is, in order to show that a given statement is entailed by given hypotheses, the automated prover assumes the hypotheses and the negation of the statement, and attempts to derive a contradiction.

See also

• Law of excluded middle
• Law of noncontradiction
• Proof by exhaustion
• Proof by infinite descent
• Modus tollens
• Reductio ad absurdum

Further reading and external links

• Franklin, James;Daoud, Albert (2011).Proof in Mathematics: An Introduction.chapter 6: Kew.ISBN978-0-646-54509-7.{{cite book}}:CS1 maint: location (link)
• Proof by Contradictionfrom Larry W. Cusick'sHow To Write Proofs
• Reductio ad AbsurdumInternet Encyclopedia of Philosophy; ISSN 2161-0002