Difference between revisions of "Reductio Ad Absurdum"
Jump to navigation
Jump to search
Masterbratac (talk | contribs) (mathiness++) |
|||
| Line 1: | Line 1: | ||
| − | '''Reductio ad absurdum''', also called [[proof]] by contradiction, is a method of mathematical proof. It involves assuming the opposite of what one is trying to prove, and showing that this would lead to a contradiction. | + | '''Reductio ad absurdum''', also called [[proof]] by contradiction, is a method of mathematical proof. It involves assuming the opposite of what one is trying to prove, and showing that this would lead to a contradiction. It works by the law of the excluded middle. The proof typically follows this structure: |
| + | |||
| + | #Create an initial assumption | ||
| + | #Follow a series of axiomatically valid steps | ||
| + | #Reach a contradiction | ||
| + | #Therefore the initial assumption is incorrect | ||
| + | |||
| + | An example of this is [[Euclid]]'s proof of the infinitude of the [[Prime number|primes]]: | ||
| + | |||
| + | #Assume there are finitely many primes | ||
| + | #Take the product of all primes and call it ''N''. Since ''N+1'' is not in our finite set of primes, it must be composite | ||
| + | #By the [[fundamental theorem of arithmetic]], ''N+1'' has a prime factorization. But ''N+1'' is not divisible by any of the previous primes | ||
| + | #Since ''N+1'' is composite, there must be a prime missing from our set of primes. But this set contains all primes | ||
| + | #Therefore, our initial assumption ("there are finitely many primes") is invalid | ||
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
Revision as of 16:28, June 30, 2008
Reductio ad absurdum, also called proof by contradiction, is a method of mathematical proof. It involves assuming the opposite of what one is trying to prove, and showing that this would lead to a contradiction. It works by the law of the excluded middle. The proof typically follows this structure:
- Create an initial assumption
- Follow a series of axiomatically valid steps
- Reach a contradiction
- Therefore the initial assumption is incorrect
An example of this is Euclid's proof of the infinitude of the primes:
- Assume there are finitely many primes
- Take the product of all primes and call it N. Since N+1 is not in our finite set of primes, it must be composite
- By the fundamental theorem of arithmetic, N+1 has a prime factorization. But N+1 is not divisible by any of the previous primes
- Since N+1 is composite, there must be a prime missing from our set of primes. But this set contains all primes
- Therefore, our initial assumption ("there are finitely many primes") is invalid