Proofs:Contradiction

A proof by contradiction is a proof in which we assume the negation of the conclusion of our proposition/theorem, and show that this assumption leads to a contradiction. If the negation of the conclusion is false, then the original conclusion must be true. For example, say we are trying to prove that ${\sqrt {2}}$ is irrational. To prove this by contradiction, we assume that ${\sqrt {2}}$ is instead rational, and then make a series of maneuvers to show that this leads to a contradiction. This means that the assumption that ${\sqrt {2}}$ is rational is false, and thus proves that ${\sqrt {2}}$ must be irrational. Here is the full proof of this statement by contradiction:

Say that ${\sqrt {2}}$ is rational. Then by definition of a rational number, there exists two integers $p$ and $q$ such that $q\neq 0$ , ${\frac {p}{q}}$ is in its most simplified form (that is, p and q do not share any factors), and ${\sqrt {2}}={\frac {p}{q}}$ . Then, $({\sqrt {2}})^{2}=\left({\frac {p}{q}}\right)^{2}\to 2={\frac {p^{2}}{q^{2}}}\to 2q^{2}=p^{2}$ . Since $2q^{2}=p^{2}$ , $p^{2}$ is an even number, and thus p itself must be an even number (since $x^{2}$ is odd for x odd, and even for x even). So, there exists an integer k such that p = 2k, and thus $2q^{2}=p^{2}=(2k)^{2}=4k^{2}$ , which implies $q^{2}=2k^{2}$ . Therefore $q^{2}$ is even, and so q must be even. However, if p and q are both even, then they MUST share the factor 2. This contradicts the fact that ${\frac {p}{q}}$ is in its most simplified form. So, our original assumption that ${\sqrt {2}}$ is rational is false, and thus ${\sqrt {2}}$ must be irrational since it cannot be expressed as a simplified fraction ${\frac {p}{q}}$ , $p,q\in \mathbb {Z}$ , $q\neq 0$ .