Proof Styles--Contradiction and Direct

Date: 04/22/2006 at 01:46:08
From: Nelson
Subject: Methods of mathematics proof

I've been taught the method to prove that sqrt(2) is an irrational 
number by proof by contradiction.

I want to know under what circumstances is it easier to prove a 
mathematical problem by the method of contradiction.  Can you prove 
that sqrt(2) is an irrational number by direct deduction?

Date: 04/22/2006 at 16:07:42
From: Doctor Vogler
Subject: Re: Methods of mathematics proof

Hi Nelson,

Thanks for writing to Dr. Math.  In some sense, it is always at least
as easy to prove something by contradiction than in any other way. 
This is because any direct proof or proof by contrapositive is also a
proof by contradiction in a different light.  If you are trying to
prove H implies C, then the direct proof starts with H and arrives at
C.  The proof by contrapositive starts with -C (not C) and arrives at
-H (not H).  The proof by contradictions starts with both H and -C,
which means that either of the other two types of proof will still
work, since you start with the same assumptions and more.  Then you 
try to arrive at a contradiction.  Well, if you arrive at C or -H,
then that contradicts your assumption, so you are done.  But if you 
are doing a proof by contradiction, then you can arrive at other
contradictions.  More importantly, you can use both assumptions H and
-C as you try to get the contradiction.

In any case, sometimes it's not completely clear what exactly a
"direct" proof is.  For example, you might use a theorem which was
proved by contradiction.

Well, given that caveat, here is a direct proof that sqrt(2) is
irrational.  It uses the Rational Roots Theorem for polynomials with
integer coefficients.  That theorem says that if the polynomial

  x^2 - 2 = 0

has any rational roots, then they must have the form a/b where a is a
factor of the constant term -2, and b is a factor of the leading
coefficient 1.  That means that a/b must be one of

  -2, -1, 1, or 2.

Since none of these have a square equal to 2, the polynomial

  x^2 - 2 = 0

must have no rational roots.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/