Difference between revisions of "Reductio Ad Absurdum"

Revision as of 18:36, February 3, 2011

Reductio ad absurdum, also called proof by contradiction, is a method of mathematical proof. It involves assuming the opposite of what one is trying to prove, and showing that this would lead to a contradiction. It works by the law of the excluded middle. The proof typically follows this structure:

1. Create an initial assumption
2. Follow a series of axiomatically valid steps
3. Reach a contradiction
4. Therefore the initial assumption is incorrect

Proof of Proposition P by Contradiction

1. Suppose ~P.
2. ...
3. Therefore, Q.
4. ...
5. Therefore, ~Q
6. Hence, Q and ~Q, a contradiction
7. Thus, P

Example

An example of this is Euclid's proof of the infinitude of the primes:

1. Assume there are finitely many primes
2. Take the product of all primes and call it N. Since N+1 is not in our finite set of primes, it must be composite
3. By the fundamental theorem of arithmetic, N+1 has a prime factorization. But N+1 is not divisible by any of the previous primes
4. Since N+1 is composite, there must be a prime missing from our set of primes. But this set contains all primes
5. Therefore, our initial assumption ("there are finitely many primes") is invalid

There is an academic controversy over whether proofs by contradiction (see also Excluded Middle) should be accepted qua proofs; either due to concerns regarding computability, or Intuitionist Mathematics. These are not necessarily held to be distinct concerns. Most mathematicians disregard any such controversy and accept proofs by contradiction.