2

How does one construct the proof by contradiction? I know Direct Proof and Proof by Contrapositive really well but just can't understand proof by contradiction.

Saim Salman
  • 29
  • 1
  • 2
    Welcome to MathSE. The question unfortunately needs a lot more context before anyone can attempt to answer it. – Ishfaaq Oct 09 '14 at 05:22

2 Answers2

6

Statement: If $p$ is true, then $q$ is true.
Direct Proof: Assume $p$ is true, try to proof $q$ is true.
Contrapositive: Assume $q$ is false, try to proof $p$ is false.
Contradiction: Assume $p$ is true and $q$ is false, try to proof the assumption will lead to result makes no sense.

5

Brief summary. Assume provisionally that the statement you want to prove true is actually false. Work out some consequences until you arrive at something you know is false. As long as your deductions are all accurate, the only way you could have obtained a false conclusion is if the provisional assumption you made was incorrect. That is, the statement you want is not false, it is true.

Possible format (not the only way of setting out this kind of proof) -

Theorem. The statement $S$ is true.

Proof. Assume that $S$ is false. Then
...$\langle$various deductions$\rangle$...
and therefore $\langle$some conclusion$\rangle$.
But this is false. $\langle$For example, you might have proved that $0=1$.$\rangle$
Therefore the statement $S$ is true.

Example. We observe by calculation that to $8$ significant figures, $$8+31\sqrt{15}\quad\hbox{and}\quad20\sqrt{41}$$ are both equal to $128.06248$. Are these numbers really equal?

Answer. No, they are not equal.

Proof. Suppose the contrary, that is, $$8+31\sqrt{15}=20\sqrt{41}\ .$$ Squaring both sides, $$14479+496\sqrt{15}=16400\ ,$$ so $$496\sqrt{15}=1921\ .$$ Squaring both sides again, $$3690240=3690241\ .$$ But this is false. Hence our original supposition was false; that is, $$8+31\sqrt{15}\ne20\sqrt{41}\ .$$

What next? There are many examples of proof by contradiction online, please read a few and then try to do some yourself. Make sure that at some stage you read the two classics of proof by contradiction: $\sqrt2$ is irrational, and there are infinitely many primes.

Good luck!

David
  • 82,662