Reductio ad absurdum

Say we wish to prove proposition p. The procedure is to show that assuming "not p" (i.e. that p is false) leads to a logical contradiction. Thus p cannot be false, and must therefore be true.

For a simple example, consider the proposition "there is no smallest rational number greater than 0". In a reductio ad absurdum argument, we would start by assuming the opposite: that there is a smallest rational number, say, r₀.

Now let x = r₀/2. Then x is a rational number, and it's greater than 0; and x is smaller than r₀. But that is absurd - it contradicts our initial assumption that r₀ was the smallest rational number. So we can conclude that the original proposition must be true - "there is no smallest rational number greater than 0".

It is not uncommon to use this type of argument with propositions such as the one above, concerning the non-existence of some mathematical object. One assumes that such an object exists, and then proves that this would lead to a contradiction; thus, such an object does not exist. For examples, see Euclid's proof of the infinitude of primes, proof that the square root of 2 is irrational and Cantor's diagonal argument.

It is important to note that to form a valid proof, it must be demonstrated that given a proposition p, "not p" implies a property that is actually false in the mathematical system being used. The danger here is the logical fallacy of argument from lack of imagination, where it is proven that "not p" implies a property "q", which looks false, but is not really proven to be false. Traditional (but incorrect!) examples of this fallacy include false proofs of Euclid's fifth postulate (a.k.a. the parallel postulate) from the other postulates.

The reason these examples are not really examples of this fallacy is that the notion of proof was different in the 19th century; (Euclidean) geometry was seen as being a 'true' reflection of physical reality, and so deducing a contradiction by concluding something physically implausible (like the angles of a triangle not being 180 degrees) was acceptable. Doubts about the nature of the geometry of the universe led mathematicians such as Bolya, Gauss, Lobachevsky, Riemann, among others, to question and clarify what actually constituted 'geometry'. Out of these men's work, resulted Non-Euclidean geometry.For a further exposition of these misunderstandings see Morris Kline, _Mathematical Thought: from Ancient to Modern Times_.

Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts reductio ad absurdum arguments as universally valid. In schools such as intuitionism, the law of the excluded middle is not taken as true. From this way of thinking, there is a very significant difference between proving that something exists by showing that it would be absurd if it did not; and proving that something exists by constructing an actual example of such an object.

In symbolic logic, the reductio ad absurdum is represented as:

if

<math>S \cup \{ \neg p \} \vdash F</math>

then

<math>S \vdash p</math>

In the above, p is the proposition we wish to prove; and S is a set of statements which are given as true -- these could be, for example, the axioms of the theory we are working in, or earlier theorems we can build upon. We consider the negation of p in addition to S; if this leads to a logical contradiction F, then we can conclude that the statements in S lead to p.

Note that the set theoretic union, in some contexts closely related to logical disjunction (or), is used here for sets of statements in such a way that it is more related to logical conjunction (and).