Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Proof by contradiction"
(→‎Euclid's proof of the infinitude of primes)
 
(20 intermediate revisions by 12 users not shown)
Line 1: Line 1:
−
'''Proof by contradiction''' is an indirect type of proof that assumes the proposition (that which is to be proven) is true and shows that this assumption leads to an error, logically or mathematically. Famous results which utilised 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)
+
'''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 ==
−
''' Proof that the square root of 2 is irrational'''
 
  
−
Assume <math>\sqrt{2}</math> is 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,
+
===Proof that the square root of 2 is irrational===
−
<math>\sqrt{2}=\frac{b}{a}</math>
 
−
<math>2=\frac{b^2}{a^2}</math>
 
−
<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>
 
−
<math>a^2=2c^2</math>
 
−
Since 2c^2 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.
 
  
−
'''Euclid's proof of the infinitude of primes'''
+
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
−
Assume there exist a finite number of primes p_1, p_2, ..., p_n.  Let <math>N=p_1p_2p_3...p_n+1</math>.  By the original assumption, N is not in the set of primes, so it is composite and divisible by some prime p_i.  If p_i|N and <math>p_i|p_1p_2...p_n, p_i</math> must also divide <math>1</math>.  However, no prime number evenly divides <math>1</math>, so our original assumption that there are only a finite number of primes is false.
+
<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>.
 +
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>
 +
 
 +
===[[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>.  <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==
 +
*[[Proof writing]]
 +
*[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 $\sqrt{2}$ 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.

Examples

Proof that the square root of 2 is irrational

Assume $\sqrt{2}$ is rational, i.e. it can be expressed as a rational fraction of the form $\frac{b}{a}$, where $a$ and $b$ are two relatively prime integers. Now, since $\sqrt{2}=\frac{b}{a}$, we have $2=\frac{b^2}{a^2}$, or $b^2=2a^2$. Since $2a^2$ is even, $b^2$ must be even, and since $b^2$ is even, so is $b$. Let $b=2c$. We have $4c^2=2a^2$ and thus $a^2=2c^2$. Since $2c^2$ is even, $a^2$ is even, and since $a^2$ is even, so is a. However, two even numbers cannot be relatively prime, so $\sqrt{2}$ cannot be expressed as a rational fraction; hence $\sqrt{2}$ is irrational. $\blacksquare$

Euclid's proof of the infinitude of primes

Assume there exists a finite number of primes $p_1, p_2,\ldots, p_n$. Let $N=p_1p_2p_3...p_n+1$. $N$ 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, $N$ must be divisible by some other prime not in our list, which contradicts the assumption that there is a finite number of primes. $\blacksquare$

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Proof_by_contradiction&oldid=177269"