Understanding Proof by Contradiction in Mathematics
Proof by contradiction is a powerful technique used in mathematics to establish the validity of a statement by assuming its negation leads to a contradiction. This method involves supposing the opposite of what needs to be proven and demonstrating that this assumption inevitably results in an inconsistency. Through a series of visuals and examples, this content explores the concept of proof by contradiction, providing a clear explanation of its application and significance in mathematical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Warm-up: Show if ?2 is even, then ? is even. Proof by Contradiction CSE 311 Spring 2022 Lecture 16
If ?2 is even then ? is even Proof: We argue by contrapositive. Let ? be an arbitrary integer and suppose ? is odd. ?2 is odd.
If ?2 is even then ? is even Proof: We argue by contrapositive. Let ? be an arbitrary integer and suppose ? is odd. By definition of odd, ? = 2? + 1 for some integer ?. ?2= 2? + 12= 4?2+ 4? + 1. Factoring, ?2= 2 2?2+ 2? + 1. Since ? was an integer, 22+ 2? is an integer. So ?2 is odd by definition.
Announcements We re posting the handouts and solutions for this week s section later today. We think you could use another example or two of properly formatted induction proofs. They re primarily study for the midterm materials no harm having those early. You should still go to section this week through, your TAs are more useful than the written solutions. I ll post the slides for Friday (induction practice day) late tonight as well. Midterm info is here.
Proof By Contradiction Suppose the negation of your claim. Show that you can derive False (i.e. ( claim) F ) If your proof is right, the implication is true. So claim must be False. So claim must be True!
Proof By Contradiction Skeleton Suppose, for the sake of contradiction ? ? ? But ? and ? is a contradiction! So we must have ?.
Proof By Contradiction Claim: 2 is irrational (i.e. not rational). Proof:
Proof By Contradiction Claim: 2 is irrational (i.e. not rational). Proof: Suppose for the sake of contradiction that 2 is rational. But [] is a contradiction!
Proof By Contradiction If ?2 is even then ? is even. Claim: 2 is irrational (i.e. not rational). Proof: Suppose for the sake of contradiction that 2 is rational. By definition of rational, there are integers s,? such that t 0 and 2 = ?/? Let ? = gcd s,t,q = of ?,? and so ?,? have no more common prime factors. Therefore the gcd ?,? = 1. s ? gcd s,t By the fundamental theorem of arithmetic, we have divided out all common factors 2 =? ? That s a contradiction! We conclude 2 is irrational.
Proof By Contradiction If ?2 is even then ? is even. Claim: 2 is irrational (i.e. not rational). Proof: Suppose for the sake of contradiction that 2 is rational. By definition of rational, there are integers s,? such that t 0 and 2 = ?/? Let ? = gcd s,t,q = ?,? and so ?,? have no more common prime factors. Therefore the gcd ?,? = 1. s t gcd s,t By the fundamental theorem of arithmetic, we have divided out all common factors of 2 =? ? 2 =?2 ?2 2?2= ?2 so ?2 is even. That s a contradiction! We conclude 2 is irrational.
Proof By Contradiction If ?2 is even then ? is even. Claim: 2 is irrational (i.e. not rational). Proof: Suppose for the sake of contradiction that 2 is rational. By definition of rational, there are integers s,? such that t 0 and 2 = ?/? Let ? = gcd s,t,q = ?,? and so ?,? have no more common prime factors. Therefore the gcd ?,? = 1. s t gcd s,t By the fundamental theorem of arithmetic, we have divided out all common factors of 2 =? ? 2 =?2 ?2 2?2= ?2 so ?2 is even. By the fact above, ? is even, i.e. ? = 2? for some integer ?. Squaring both sides ?2= 4?2 Substituting into our original equation, we have: 2?2= 4?2, i.e. ?2= 2?2. So ?2 is even. Applying the fact above again, ? is even. But if both ? and ? are even, gcd ?,? 2. But we said gcd ?,? = 1 That s a contradiction! We conclude 2 is irrational.
Proof By Contradiction How in the world did we know how to do that? In real life lots of attempts that didn t work. Be very careful with proof by contradiction without a clear target, you can easily end up in a loop of trying random things and getting nowhere.
Whats the difference? What s the difference between proof by contrapositive and proof by contradiction? Show ? ? Starting Point Target Proof by contradiction ? ? (? ?) Something false Proof by contrapositive ? ? Show ? Starting Point Target Proof by contradiction ? Something false Proof by contrapositive --- ---
Another Proof By Contradiction Claim: There are infinitely many primes. Proof:
Another Proof By Contradiction Claim: There are infinitely many primes. Proof: Suppose for the sake of contradiction, that there are only finitely many primes. Call them ?1,?2, ,??. But [] is a contradiction! So there must be infinitely many primes.
Another Proof By Contradiction Claim: There are infinitely many primes. Proof: Suppose for the sake of contradiction, that there are only finitely many primes. Call them ?1,?2, ,??. Consider the number ? = ?1 ?2 ??+ 1 Case 1: ? is prime Case 2: ? is composite But [] is a contradiction! So there must be infinitely many primes.
Another Proof By Contradiction Claim: There are infinitely many primes. Proof: Suppose for the sake of contradiction, that there are only finitely many primes. Call them ?1,?2, ,??. Consider the number ? = ?1 ?2 ??+ 1 Case 1: ? is prime ? > ?? for all ?. But every prime was supposed to be on the list ?1, ,??. A contradiction! Case 2: ? is composite Some prime on the list (say ??) divides ?. So ?%??= 0. and ?1?2 ??+ 1 %??= 1. But ? = ?1?2 ??+ 1 . That s a contradiction! In either case we have a contradiction! So there must be infinitely many primes.
Just the Skeleton For all integers ?, if ?2 is even, then ?is even.
Just the Skeleton For all integers ?, if ?2 is even, then ?is even. Suppose for the sake of contradiction, there is an integer ?, such that ?2 is even and ? is odd. [] is a contradiction, so for all integers ?, if ?2 is even, then ? is even.
Just the Skeleton There is not an integer ? such that for all integers ?, ? ?.
Just the Skeleton There is not an integer ? such that for all integers ?, ? ?. Suppose, for the sake of contradiction, that there is an integer ? such that for all integers ?, ? ?. [] is a contradiction! So there is not an integer ? such that for all integers ?,? ?.
