Difference between revisions of "Proof by contradiction"
Enderramsby (talk | contribs) (→Euclid's proof of the infinitude of primes) |
|||
| (10 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | '''Proof by contradiction''' (also known as reducto ad absurdum or indirect proof) is an indirect type of proof that assumes the proposition (that which is to be proven) is false and shows that this assumption leads to an error, logically or mathematically. Thus, the proposition is true. Famous results which utilized proof by contradiction include the irrationality of <math>\sqrt{2}</math> and the infinitude of primes. | + | '''Proof by contradiction''' (also known as reducto ad absurdum or indirect proof) is an indirect type of proof that assumes the proposition (that which is to be proven) is false and shows that this assumption leads to an error, logically or mathematically. Thus, the proposition is true. Famous results which utilized proof by contradiction include the irrationality of <math>\sqrt{2}</math> 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 == | == Examples == | ||
| − | + | ===Proof that the square root of 2 is irrational=== | |
| − | Assume <math>\sqrt{2}</math> is [[rational number|rational]], i.e. it can be expressed as a rational fraction of the form <math>\frac{b}{a}</math>, where a and <math>b</math> are two [[relatively prime]] integers. Now, since | + | Assume <math>\sqrt{2}</math> is [[rational number|rational]], i.e. it can be expressed as a rational fraction of the form <math>\frac{b}{a}</math>, where <math>a</math> and <math>b</math> are two [[relatively prime]] integers. Now, since |
| − | <math>\sqrt{2}=\frac{b}{a}</math>, we have <math>2=\frac{b^2}{a^2}</math>, or <math>b^2=2a^2</math>. Since <math>2a^2</math> is even, <math>b^2</math> must be even, and since <math>b^2</math> is even, so is <math>b</math>. Let <math>b=2c</math>. We have | + | <math>\sqrt{2}=\frac{b}{a}</math>, we have <math>2=\frac{b^2}{a^2}</math>, or <math>b^2=2a^2</math>. Since <math>2a^2</math> is even, <math>b^2</math> must be even, and since <math>b^2</math> is even, so is <math>b</math>. Let <math>b=2c</math>. We have <math>4c^2=2a^2</math> and thus <math>a^2=2c^2</math>. |
| − | <math>4c^2=2a^2</math> | + | Since <math>2c^2</math> is even, <math>a^2</math> is even, and since <math>a^2</math> is even, so is a. However, two even numbers cannot be relatively prime, so <math>\sqrt{2}</math> cannot be expressed as a rational fraction; hence <math>\sqrt{2}</math> is irrational. <math>\blacksquare</math> |
| − | <math>a^2=2c^2</math>. | ||
| − | Since <math>2c^2</math> is even, <math>a^2</math> is even, and since <math>a^2</math> is even, so is a. However, two even numbers cannot be relatively prime, so <math>\sqrt{2}</math> cannot be expressed as a rational fraction; hence <math>\sqrt{2}</math> is irrational. <math>\ | ||
| − | + | ===[[Euclid's proof of the infinitude of primes]]=== | |
| − | Assume there exists a finite number of [[prime|primes]] <math>p_1, p_2,\ldots, p_n</math>. Let <math>N=p_1p_2p_3...p_n+1</math>. N is | + | Assume there exists a finite number of [[prime|primes]] <math>p_1, p_2,\ldots, p_n</math>. Let <math>N=p_1p_2p_3...p_n+1</math>. <math>N</math> is not divisible by any of the known primes since it will leave a remainder of one upon division by any one of them. Thus, <math>N</math> must be divisible by some other prime not in our list, which contradicts the assumption that there is a finite number of primes. <math>\blacksquare</math> |
==See also== | ==See also== | ||
*[[Proof writing]] | *[[Proof writing]] | ||
| − | *[http://www.artofproblemsolving.com/ | + | *[http://www.artofproblemsolving.com/articles/how-to-write-solution How to Write a Solution] by [[Richard Rusczyk]] and [[Mathew Crawford]] |
| + | |||
| + | [[Category:Proofs]] | ||
Latest revision as of 13:01, 21 August 2022
Proof by contradiction (also known as reducto ad absurdum or indirect proof) is an indirect type of proof that assumes the proposition (that which is to be proven) is false and shows that this assumption leads to an error, logically or mathematically. Thus, the proposition is true. Famous results which utilized proof by contradiction include the irrationality of 
and the infinitude of primes. 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.
Contents
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 
and 
are two relatively prime integers. Now, since
, we have 
, or 
. Since 
is even, 
must be even, and since is even, so is . Let 
. We have 
and thus 
.
Since 
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 exists a finite number of primes 
. Let 
. 
is not divisible by any of the known primes since it will leave a remainder of one upon division by any one of them. Thus, must be divisible by some other prime not in our list, which contradicts the assumption that there is a finite number of primes.
