Proof by Contradiction

Date: 04/29/2003 at 07:07:29
From: Ajay
Subject: Proof by Contradiction

Is there any specific mathematical theory that states that Proof by 
Contradiction is a valid proof? E.g. sqrt(2) is irrational is 
normally proved using contradiction.

Date: 04/29/2003 at 14:54:44
From: Doctor Achilles
Subject: Re: Proof by Contradiction

Hi Ajay,

Thanks for writing to Dr. Math.

The justification comes from basic mathematical logic.  A basic proof 
might go like this:

Step 1: Prove that a contradiction must be false.

1a) Definition of contradiction: A contradiction exists any time a 
proposition "P" is asserted to be true in conjunction with its 
negation, "not-P."

1b) Definition of conjunction: A conjunction is a connective that 
joins two propositions. The conjunction of two propositions is true 
if and only if BOTH propositions are true individually. Therefore, 
if either individual proposition is false, or if both propositions 
are false, then the conjunction of the two is false.

1c) Definition of proposition: A proposition is a logical variable 
that stands for a statement. All propositions are either true or 
false, never both at the same time and never neither. (This is 
sometimes called the "law of the excluded middle.")

1d) Definition of negation ("not-"): The negation of a proposition is 
itself a proposition that necessarily carries the opposite truth value 
from the original (i.e. it is false if the original is true and true 
if the original is false).

1e) The proposition "P" is either true or false (follows from 1c).

1f) The proposition "not-P" (the negation of "P") is either false or 
true; it has the opposite truth value to "P" (follows from 1d).

1g) If "P" is true, then "not-P" is false; if "P" is false, then 
"not-P" is true (follows from 1f).

1h) Regardless of the truth value of "P", it is certain that either 
"P" is false or "not-P" is false (follows from 1g).

1i) The conjunction of "P" and "not-P" is necessarily false (follows 
from 1b and 1h).

1j) A contradiction is false (follows from 1i and 1a).

Step 2: Prove that nothing false can be derived from a set of true 
assumptions.

To make this proof complete, you have to prove that every step in a 
Proof by Contradiction is "truth preserving"; that is: every step is 
such that if the assumptions and conclusions that have preceded it are 
true, then the conclusion of that step must be true. An example of how 
this might work is as follows:

  Proof that A can be derived from the conjunction of A and B:

  Assume we have the conjunction of A and B given as true.
  Because a conjunction can only be true if BOTH of its parts
  are true, both A and B are true. Thus, A must be true.  
  Therefore, A follows from the conjunction of A and B.

I have proven that you can go from the conjunction of two things to 
either of those things individually. You have to do a similar proof 
for every step, showing that if what came before is true, then what 
follows must also be true. This is far too much for me to do right 
now, but mathematics and logic never use steps which have not been 
proven to be "truth preserving."

Step 3: Put steps 1 and 2 together.

In step 1 we showed that a contradiction is false. In step 2 we 
showed that our conclusions MUST be true if all our assumptions were 
true. So now let's imagine that we do a proof.

The first thing we do when we do a proof is make an assumption. We 
aren't sure if this assumption is true or not, but we're going to 
assume it is for a while and see what that gets us.

Then we do a series of "truth preserving" manipulations on our 
assumption and on the subconclusions we reach from it.

Then, all of a sudden, we find that we have reach a contradiction.

We know that we have concluded something that is false (Step 1 above).  
We also know that IF our assumption were true, then it would not be 
possible to conclude something which is false (Step 2 above).  
Therefore the only possibility is that the assumption was never true 
to begin with. We can therefore say with certainty that our assumption 
was false.

In other words, we have proven our assumption false.

Hope this helps. If you have other questions or you'd like to talk 
about this some more, please write back.

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