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: No, the idea of a proof by contradiction is:


*

*Assume that what you want to prove is actually false.

*Determine the logical consequences of that assumption.

*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.


*

*Assume that the set of prime numbers is finite.

*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.

*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}$.
A: 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.
