Proof by contradiction

Proof by contradiction is similar to refutation by contradiction,[3][4] 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.[5] 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".

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.

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.

An early occurrence of proof by contradiction can be found in Euclid's Elements, Book 1, Proposition 6:[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.

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.[7]

Euclid's theorem states that there are infinitely many primes. In Euclid's Elements the theorem is stated in Book IX, Proposition 20:[8]

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}$

Let us take a second look at Euclid's theorem – Book IX, Proposition 20:[10]

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.

The classic proof that the square root of 2 is irrational is a refutation by contradiction.[11] 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 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, 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.