Difference between revisions of "Proof by contradiction"

Revision as of 20:14, 17 June 2006

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 $\sqrt{2}$ and the infinitude of primes. (if you know how, please make the following proofs look better)

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, $\sqrt{2}=\frac{b}{a}$ $2=\frac{b^2}{a^2}$ $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$ $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.

Euclid's proof of the infinitude of primes: Assume there exist a finite number of primes p_1, p_2, ..., p_n. Let $N=p_1p_2p_3...p_n+1$ . 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 $p_i|p_1p_2...p_n, p_i$ must also divide $1$ . However, no prime number evenly divides $1$ , so our original assumption that there are only a finite number of primes is false.

@@ 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.
+'''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)
 ----
@@ Line 13: / Line 13: @@
 Euclid's proof of the infinitude of primes:
-Assume there exist a finite number of primes <math>p_1, p_2, ..., p_n</math>.  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.
+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.

Page

Toolbox

Search

Difference between revisions of "Proof by contradiction"

Revision as of 20:14, 17 June 2006