Report

CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/ Clicker frequency: CA Todays topics • Proof by contradiction • Section 3.5 in Jenkyns, Stephenson Contradictions destroy the entire system that contains them • Draw the truth table: (p ∧ ¬p) q A. p q (p ∧ ¬p) F F F F T F C. T F F D. T T F E. B. F,F,F,F T,T,T,T F,T,F,T F,F,T,T None/more/other Contradictions destroy the entire system that contains them • Draw the truth table: (p ∧ ¬p) q A. p q (p ∧ ¬p) F F F T F T F T C. T F F T D. T T F T E. B. F,F,F,F T,T,T,T F,T,F,T F,F,T,T None/more/other • 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. [write theorem] • 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”] 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 b0. Squaring both sides gives x2=a2/b2. As both a2,b2 are integers, b20, 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 6 is irrational • Proof (by contradiction). • Theorem: THIS ONE IS MORE TRICKY. TRY BY YOURSELF FIRST IN GROUPS. Example 3: proof (contd) 6 is irrational • Proof (by contradiction). • Theorem: 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. 6 is irrational • Proof (by contradiction). • Theorem: Assume towards contradiction that 6 = with , ∈ , ≠ 0. We choose c,d without any common divisor. Squaring gives 2 = 62 . First, note that c must be even, otherwise if c is odd then (by lemma) 2 is odd, but 62 is even. So, d must be odd (otherwise c,d both divisible by 2). Let = 2, ∈ . Then 42 = 6 2 , which implies 22 = 32 . However, 22 is even but 3 2 is odd (by lemma). We reached a contradiction. Hence 6 is irrational. Example 4 2 + 3 is irrational • Proof (by contradiction). • Theorem: Example 4: proof 2 + 3 is irrational • Proof (by contradiction). • Theorem: Assume towards contradiction that 2 + 3 is rational. So, 2 + 3 = / with , ∈ , ≠ 0. Squaring gives So, 6 = 1 2 2 2 2 2 = −5 = 2+ 3 2 −52 2 2 2 =5+2 6 is rational, which we just showed is false. We reached a contradiction. Hence, 2 + 3 is irrational. Next class • Proof by induction • Read section 3.6 in Jenkyns, Stephenson