# Idea of a proof by contradiction

Is the idea of a proof by contradiction to prove that the desired conclusion is both true and false or can it be any derived statement that is true and false (not necessarily relating to the conclusion)? Or can it simply be an absurdity that you know is false but through your derivation comes out true?

• A proof by contradiction is you suppose something true and after some steps, you find that it is false (you contradict what you supposed). $$\mathrm{Suppose}\; x\geqslant1\;\cdots\; x=0.$$ – Jika Jun 3 '14 at 22:51

It can be both: take the following simple problem. Is is possible to cover an $8\times8$ chessboard which has had its two white corners removed using domino-like pieces of size $2\times1$?

Let us assume it is possible and we have somehow managed to do it. Notice we covered $32$ black squares and $30$ white squares. Also notice a domino-like piece will cover 1 black and 1 white square.

Since each domino-like piece covers 1 black square and we covered $32$ white pieces the number of dominoes we used is $16$.

On the other hand Since each domino-like piece covers 1 white square and we covered $30$ white pieces the number of dominoes we used is $15$.

Therefore $16=15\dots$ wait wut? In this case it wasn't a direct contradiction. It just lead to something that clearly can't happen.

No, the idea of a proof by contradiction is:

1. Assume that what you want to prove is actually false.
2. Determine the logical consequences of that assumption.
3. Find that this line of thought inevitably leads to a contradiction, showing it to be wrong, meaning therefore that what you want to prove is true.

I think the best example is the proof that there are infinitely many prime numbers.

1. Assume that the set of prime numbers is finite.
2. Since the total number of primes is finite, you can multiply them all together to obtain a number that is divisible by all the primes.
3. But what is the prime factorization of the number that is one more than the product of all primes? It must either be a "new" prime or it must be a composite number that is divisible by a prime we managed to overlook; but either way, the assumption that there are finitely many primes is wrong, meaning therefore that there are infinitely many primes.

Proof by contradiction can also be used to prove that certain numbers are irrational, like $\sqrt{2}$.

• Good point, I've changed it accordingly. – user153918 Jun 3 '14 at 23:01
• I guess my question should have elaborated a little more. My question is directly related to your step 3, what sort of contradiction are you trying to draw? Any sort of contradiction or does it have to be a statement that is at ends with the assumption you describe in step 1. – skyfire Jun 4 '14 at 10:24
• For me to be convinced, it needs to be a contradiction of the step 1 assumption. Maybe there are examples of proof by contradiction where the contradiction drawn isn't a contradiction of the assumption, but if I was reading such a proof, I would wonder if it is a valid proof, I would wonder if the author didn't make some mistake along the way. – user153918 Jun 5 '14 at 21:21
• Although... someone could split hairs with me about the proof by contradiction that $\sqrt{2}$ is irrational. The step 1 assumption would be that it is rational. The first logical consequence in step 2 would be that then $\sqrt{2} = \frac{a}{b}$ with $a, b \in \mathbb{Z}$ and $\gcd(a, b) = 1$. The step 3 contradiction is that $\gcd(a, b) > 1$. – user153918 Jun 5 '14 at 21:24
• The contradiction can be any sort of contradiction, it does not have to involve the statement that was originally assumed to be true. The example stated here of the irrationality of $\sqrt{2}$ is this way, as you pointed out. Proofs where the contradiction is with the thing you originally assumed can usually be rewritten as proofs by contraposition instead of proofs by contradiction. – Carl Mummert Jun 5 '14 at 22:22