Misplaced Pages

In logic, 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. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as 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 as indirect proof, proof by assuming the opposite, and reductio ad impossibile.

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

1. The proposition to be proved is P.
2. We assume P to be false, i.e., we assume ¬P.
3. 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.
4. 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 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 the propositional formula ¬¬P ⇒ P, equivalently (¬P ⇒ ⊥) ⇒ P, which reads: "If assuming P to be false implies falsehood, then P is true."

In natural deduction the principle takes the form of the rule of inference

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

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

In sequent calculus the principle is expressed by the sequent

${\displaystyle \Gamma ,\lnot \lnot P\vdash P,\Delta }$

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

Justification

In classical logic the principle may be justified by the examination of the truth table 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, as follows. We assume ¬¬P and seek to prove P. By the law of excluded middle P either holds or it does not:

1. if P holds, then of course P holds.
2. if ¬P holds, then we derive falsehood by applying the law of noncontradiction to ¬P and ¬¬P, after which the principle of explosion 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 for negation:

${\displaystyle {\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 to refutation by contradiction, also known as proof of negation, which states that ¬P is proved as follows:

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

In contrast, proof by contradiction proceeds as follows:

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

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 ${\displaystyle P}$ and ${\displaystyle \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

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

Law of non-contradiction

The law of noncontradiction was first stated as a metaphysical principle by Aristotle. 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 of P and ¬P is true.

Proof by contradiction in intuitionistic logic

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (May 2024) (Learn how and when to remove this message)

In intuitionistic logic 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 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, then the condition is not acceptable, as it would allow us to solve the Halting problem. To see how, consider the statement H(M) stating "Turing machine 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 (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.

A proposition P which satisfies ${\displaystyle \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 ${\displaystyle 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 "${\displaystyle n}$ is prime" or "${\displaystyle a}$ divides ${\displaystyle b}$".

Examples of proofs by contradiction

Euclid's Elements

An early occurrence of proof by contradiction can be found in Euclid'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 by David Hilbert. His Nullstellensatz states:

If ${\displaystyle f_{1},\ldots ,f_{k}}$ are polynomials in n indeterminates with complex coefficients, which have no common complex zeros, then there are polynomials ${\displaystyle g_{1},\ldots ,g_{k}}$ such that ${\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}$

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

Infinitude of primes

Euclid's theorem states that there are infinitely many primes. In Euclid's Elements 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 ${\displaystyle n}$ there is a prime bigger than it, then we employ proof by contradiction, as follows.

Given any number ${\displaystyle n}$, we seek to prove that there is a prime larger than ${\displaystyle 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 ${\displaystyle n}$, and we may form the list ${\displaystyle p_{1},\ldots ,p_{k}}$ of them all. Let ${\displaystyle P=p_{1}\cdot \ldots \cdot p_{k}}$ be the product of all primes and ${\displaystyle Q=P+1}$. Because ${\displaystyle Q}$ is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say ${\displaystyle p_{i}}$. Now both ${\displaystyle P}$ and ${\displaystyle Q}$ are divisible by ${\displaystyle p_{i}}$, hence so is their difference ${\displaystyle 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 ${\displaystyle 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 at Euclid'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 case Euclid's proof applies refutation by contradiction at one step, as follows.

Given any finite list of prime numbers ${\displaystyle p_{1},\ldots ,p_{n}}$, it will be shown that at least one additional prime number not in this list exists. Let ${\displaystyle P=p_{1}\cdot p_{2}\cdots p_{n}}$ be the product of all the listed primes and ${\displaystyle p}$ a prime factor of ${\displaystyle P+1}$, possibly ${\displaystyle P+1}$ itself. We claim that ${\displaystyle p}$ is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then ${\displaystyle p}$ would divide both ${\displaystyle P}$ and ${\displaystyle P+1}$, therefore also their difference, which is ${\displaystyle 1}$. This gives a contradiction, since no prime number divides 1.

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 ∈ ${\displaystyle \mathbb {N} }$ . a/b = √2 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 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 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 ⁠q/2⁠ is even smaller than q and 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 Barrow 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 ${\displaystyle \rightarrow \!\leftarrow }$ or ${\displaystyle \Rightarrow \!\Leftarrow }$), struck-out arrows (${\displaystyle \nleftrightarrow }$), a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※), or ${\displaystyle \times \!\!\!\!\times }$.

Hardy's view

G. H. Hardy 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."

Automated theorem proving

In automated theorem proving the method of resolution is 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

References

1. Bishop, Errett 1967. Foundations of Constructive Analysis, New York: Academic Press. ISBN 4-87187-714-0
2. "Proof By Contradiction". www2.edc.org. Retrieved 12 June 2023.
3. "Reductio ad absurdum | logic". Encyclopedia Britannica. Retrieved 25 October 2019.
4. "Proof by contradiction". nLab. Retrieved 7 October 2022.
5. Richard Hammack, Book of Proof, 3rd edition, 2022, ISBN 978-0-9894721-2-8; see "Chapter 9: Disproof".
6. Bauer, Andrej (29 March 2010). "Proof of negation and proof by contradiction". Mathematics and Computation. Retrieved 26 October 2021.
7. "Euclid's Elements, Book 6, Proposition 1". Retrieved 2 October 2022.
8. Hilbert, David (1893). "Ueber die vollen Invariantensysteme". Mathematische Annalen. 42 (3): 313–373. doi:10.1007/BF01444162.
9. ^ "Euclid's Elements, Book 9, Proposition 20". Retrieved 2 October 2022.
10. Bauer, Andrej (2017). "Five stages of accepting constructive mathematics". Bulletin of the American Mathematical Society. 54 (3): 481–498. doi:10.1090/bull/1556.
11. Alfeld, Peter (16 August 1996). "Why is the square root of 2 irrational?". Understanding Mathematics, a study guide. Department of Mathematics, University of Utah. Retrieved 6 February 2013.
12. "Math Forum Discussions".
13. B. Davey and H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002; see "Notation Index", p. 286.
14. Gary Hardegree, Introduction to Modal Logic, Chapter 2, pg. II–2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf
15. The Comprehensive LaTeX Symbol List, pg. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf
16. G. H. Hardy, A Mathematician's Apology; Cambridge University Press, 1992. ISBN 9780521427067. PDF p.19 Archived 2021-02-16 at the Wayback Machine.
17. "Linear Resolution", From Logic to Logic Programming, The MIT Press, pp. 93–120, 1994, doi:10.7551/mitpress/3133.003.0007, ISBN 978-0-262-28847-7, retrieved 21 December 2023

Further reading and external links

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

v t e Mathematical logic
General	Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory
Theorems (list)  and paradoxes	Gödel's completeness and incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem, paradox and diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox
Logics	Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus
Set theory	Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps and cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Set theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive
Formal systems (list), language and syntax	Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of arithmetic: Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry: Euclidean: Elements Hilbert's Tarski's non-Euclidean Principia Mathematica
Proof theory	Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories
Model theory	Interpretation function of models Model equivalence finite saturated spectrum submodel Non-standard model of arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity
Computability theory	Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory
Related	Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask
Mathematics portal

• Mathematical proofs
• Methods of proof
• Theorems in propositional logic