Proof by contradiction
Proof by Contradiction
Proof by contradiction is an indirect type of proof that assumes the proposition (that which is to be proven) is true and shows that this assumption leads to an error, logically or mathematically. Famous results which utilised proof by contradiction include the irrationality of and the infinitude of primes. (if you know how, please make the following proofs look better). This technique usually works well on problems where not a lot of information is known, and thus we can create some using proof by contradiction.
Examples
Proof that the square root of 2 is irrational
Assume is rational, i.e. it can be expressed as a rational fraction of the form , where a and are two relatively prime integers. Now, Since is even, must be even, and since is even, so is . Let . We have, Since 2c^2 is even, is even, and since is even, so is a. However, two even numbers cannot be relatively prime, so cannot be expressed as a rational fraction; hence is irrational.
Euclid's proof of the infinitude of primes
Assume there exist a finite number of primes p_1, p_2, ..., p_n. Let . By the original assumption, N is not in the set of primes, so it is composite and divisible by some prime p_i. If p_i|N and must also divide . However, no prime number evenly divides , so our original assumption that there are only a finite number of primes is false.