Lila: Created page with "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 th..."

2021-09-24T16:28:11Z

Created page with "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 th..."

New page

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 <math> \sqrt{2} </math> is irrational. To prove this by contradiction, we assume that <math> \sqrt{2} </math> is instead rational, and then make a series of maneuvers to show that this leads to a contradiction. This means that the assumption that <math> \sqrt{2} </math> is rational is false, and thus proves that <math> \sqrt{2} </math> must be irrational. Here is the full proof of this statement by contradiction:

Say that <math> \sqrt{2} </math> is rational. Then by definition of a rational number, there exists two integers <math> p </math> and <math> q </math> such that <math> q \neq 0 </math>, <math> \frac{p}{q} </math> is in its most simplified form (that is, p and q do not share any factors), and <math> \sqrt{2} = \frac{p}{q} </math>. Then, <math> (\sqrt{2})^2 = \left(\frac{p}{q}\right)^2 \to 2 = \frac{p^2}{q^2} \to 2q^2 = p^2 </math>. Since <math> 2q^2 = p^2 </math>, <math> p^2 </math> is an even number, and thus p itself must be an even number (since <math> x^2 </math> is odd for x odd, and even for x even). So, there exists an integer k such that p = 2k, and thus <math> 2q^2 = p^2 = (2k)^2 = 4k^2 </math>, which implies <math> q^2 = 2k^2 </math>. Therefore <math> q^2 </math> 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 <math> \frac{p}{q} </math> is in its most simplified form. So, our original assumption that <math> \sqrt{2} </math> is rational is false, and thus <math> \sqrt{2} </math> must be irrational since it cannot be expressed as a simplified fraction <math> \frac{p}{q} </math>, <math> p,q \in \Z </math>, <math> q \neq 0 </math>.

Another famous example of proof by contradiction is the proof that there are an infinite number of prime numbers (see [https://www.math.utah.edu/~pa/math/q2.html Euclid's Proof] of this here).

==Resources==
* [https://en.wikipedia.org/wiki/Proof_by_contradiction#:~:text=In%20logic%20and%20mathematics%2C%20proof,false%20leads%20to%20a%20contradiction. Proof by Contradition], Wikipedia
* [http://www2.edc.org/makingmath/mathtools/contradiction/contradiction.asp Proof by Contradiction], Making Mathematics
* [https://www.math.utah.edu/~pa/math/q2.html Why are there infinitely many prime numbers?], University of Utah

Proofs:Contradiction - Revision history

Lila: Created page with "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 th..."