Associated Topics || Dr. Math Home || Search Dr. Math

```Date: 04/29/2003 at 07:07:29
From: Ajay

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

```
Date: 04/29/2003 at 14:54:44
From: Doctor Achilles

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.

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

- Doctor Achilles, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Logic
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search