Understanding Proof by Contradiction in Discrete Math
Explore the concept of proof by contradiction in discrete math through examples and templates. Learn how to derive contradictions to establish the truth of theorems, with demonstrations on topics like integers being both even and odd. Discover the power of contradictions in challenging assumptions and proving statements in mathematical logic.
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
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Proof by contradiction Section 3.5 in Jenkyns, Stephenson
Contradictions destroy the entire system that contains them Draw the truth table: A. F,F,F,F B. T,T,T,T C. F,T,F,T D. F,F,T,T E. None/more/other (p p) (p p) F F F F q p F F T T q F T F T
Contradictions destroy the entire system that contains them Draw the truth table: A. F,F,F,F B. T,T,T,T C. F,T,F,T D. F,F,T,T E. None/more/other (p p) (p p) F F F F q p F F T T q F T F T T T T T Here s the scary part:it doesn t matter what q is! q= All irrational numbers are integers. q= The Beatles were a terrible band. q= Dividing by zero is totally fine! All these can be proved true in a system that contains a contradiction!
Proof by contradiction template Thm. Proof (by contradiction): Assume not. That is, suppose that [ theorem] (Don t just write (theorem). For example, changes to , use DeMorgan s law if needed, etc.) [write something that leads to a contradiction: [p] so [ p]. But [p], a contradiction ] [write theorem] Conclusion: So the assumed assumption is false and the theorem is true. QED.
Example 1 Thm. There is no integer that is both even and odd. Proof (by contradiction) Assume not. That is, suppose that A. All integers are both odd and even B. All integers are not even or not odd. C. There is an integer n that is both odd and even. D. There is an integer n that is neither even nor odd. E. Other/none/more than one
Be careful about doing negations Theorem: there is no integer that is both even and odd ~ ? ? ? ? ? ? ? ? ~(? ? ? ?) Negation: ? ? (? ? ? ?) There is an integer n that is both even and odd
Example 1 Thm. There is no integer that is both even and odd. Proof (by contradiction) Assume not. That is, suppose there exists an integer n that is both even and odd. Try by yourself first
Example 1: proof Thm. There is no integer that is both even and odd. Proof (by contradiction) Assume towards contradiction that there exists an integer n that is both even and odd. Since n is even: ? ?,? = 2?. Since n is odd: ? ?,? = 2? + 1. So, 2? = 2? + 1, which gives 2 ? ? = 1 and ? ? = 1/2, which is impossible as a,b are integers, hence their difference is also an integer (we are using an axiom: the integers are closed under differentiation). We reached a contradiction. Conclusion: There is no integer that is both even and odd.
Example 2 A number x is rational if ? = ?/? for integers ? and b 0. E.g. 3=3/1, 1/2, -3/4, 0=0/1 A number is irrational if it is not rational E.g 2 (proved in textbook) Theorem: If x2 is irrational then x is irrational.
Example 2 Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume that A. There exists x where both x,x2 are rational B. There exists x where both x,x2 are irrational C. There exists x where x is rational and x2 irrational D. There exists x where x is irrational and x2 rational E. None/other/more than one
Example 2 Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume towards contradiction that there exists x where x is rational and x2 irrational. Try by yourself first
Example 2: proof Theorem: If x2 is irrational then x is irrational. Proof: by contradiction. Assume towards contradiction that there exists x where x is rational and x2 irrational. Since x is rational, x=a/b where a,b are integers, with b 0. Squaring both sides gives x2=a2/b2. As both a2,b2 are integers, b2 0, we get that x2 is rational. This is a contradiction to our assumption that x2 is irrational. Hence, x must be irrational. QED
Example 3 Theorem: 6 is irrational Proof (by contradiction). THIS ONE IS MORE TRICKY. TRY BY YOURSELF FIRST IN GROUPS.
Example 3: proof (contd) Theorem: 6 is irrational Proof (by contradiction). We will use the following lemma (=mini theorem): Lemma: product of odd integers is an odd integer. Proof of Lemma: Let x,y be odd integers. So ? = 2? + 1,? = 2? + 1 where ?,? ?. Then ?? = 2? + 1 2? + 1 = 2 2?? + ? + ? + 1 is an odd integer. QED (of lemma).
Example 3: proof (contd) Lemma: product of odd integers is an odd integer. Theorem: 6 is irrational Proof (by contradiction). Assume towards contradiction that 6 = 0. We choose c,d without any common divisor. Squaring gives ?2= 6?2. First, note that c must be even, otherwise if c is odd then (by lemma) ?2 is odd, but 6?2is even. So, d must be odd (otherwise c,d both divisible by 2). Let ? = 2?,? ? . Then 4?2= 6?2, which implies 2?2= 3?2. However, 2?2 is even but 3?2 is odd (by lemma). We reached a contradiction. Hence 6 is irrational. ? ? with ?,? ?,?
Example 4 Theorem: 2 + 3 is irrational Proof (by contradiction).
Example 4: proof Theorem: 2 + 3 is irrational Proof (by contradiction). Assume towards contradiction that 2 + 3 is rational. So, 2 + 3 = ?/? with ?,? ?,? 0. Squaring gives ?2 ?2= 2 + 3 So, 6 =1 2 showed is false. We reached a contradiction. Hence, 2 + 3 is irrational. 2= 5 + 2 6 ?2 ?2 5 =?2 5?2 2 ?2 is rational, which we just
Next class Proof by induction Read section 3.6 in Jenkyns, Stephenson
