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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{2} } is irrational. To prove this by contradiction, we assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{2} } must be irrational since it cannot be expressed as a simplified fraction Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{p}{q} } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p,q \in \Z } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \neq 0 } .