Wednesday, February 20, 2008

example of reductio ad absurdum

I am occasionally asked about the meaning of the title of this blog. Reductio ad absurdum is the name given to a particular method of proof that works toward a statement which 'reduces to an absurdity'. It is a conniving brand of proof that is reason enough for anyone to appreciate logic. We prove that a statement is true by demonstrating that it cannot be false.

A textbook example (too literally) of reductio ad absurdum or 'proof by contradiction' is found in a proof that √2 is irrational. To prove directly that there is no whole number ratio equal to √2 would involve a thorough investigation of an infinite number of fractions. This would be time consuming, to say the least. Instead, we will assume that we are wrong and prove the impossibility of that sad state of affairs.

So here we go.

Assume toward a contradiction that √2 is a rational number. Then there exist two integers p and q such that √2 = p/q. Furthermore, Without Loss Of Generalization (WLOG), we can demand that p/q is a fraction in reduced form, so that p and q have no common factors. Now:

√2 = p / q
2 = p² / q²
2q² = p²

This means that is even, which in turn means that p is even. If p is even, then it has a factor of 2 and has two factors of 2. Therefore p² = 4k² for some integer k. This gives us:

2q² = 4k²
q² = 2k²

Therefore is even, which in turn means that q is even. Recall that p is also even, as we demonstrated above. But p and q cannot both be even because we said that they have no common factors. Therefore, we have reached a contradiction, and we must conclude (since our algebra was sound) that our initial assumption was impossible, namely that √2 is a rational number. Therefore √2 is an irrational number. End of Proof.

Ah... I enjoy that every time.

1 comment:

  1. Nate and Joie, unfortunately I do not have much of mathematical value with which to comment. But, I just wanted to say that after I read your post, I imagined in my mind's eye you asking Will, "Hey Will, is the square root of 2 an irrational number?" And his emphatic, enthusiastic answer would be: "Oh, yeah." :) It brought a lot of joy to my heart!