Proofs:Contradiction

From Department of Mathematics at UTSA
Revision as of 10:28, 24 September 2021 by Lila (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

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

Another famous example of proof by contradiction is the proof that there are an infinite number of prime numbers (see Euclid's Proof of this here).

Resources