Class Notes (811,485)
CSCA67H3 (56)
Lecture

# Formal proofs

21 Pages
181 Views

Department
Computer Science
Course
CSCA67H3
Professor
Anna Bretscher
Semester
Winter

Description
Proofs Q. What is a proof? A proof is a convincing argument that a statement is true. Q. What makes up a proof? • a set of basic statements that we agree are true for a spec- iﬁed domain. E.g., if D = R then we have the basic rules about arithmetic and inequalities. • A series of logical steps that build on previously proven statements. We are concerned with the content of a proof and the structure of the proof. Example. Claim 1. Let x be any natural number. 2 If x ≥ 2 then (x + 2) ≥ 16. Proof Idea. Why do we believe this claim? • if x ≥ 2 then x + 2 ≥ 2 + 2 = 4 by arithmetic • squaring both sides, gives (x + 2) ≥ 16 30 www.notesolution.com 2 Claim 2. “There exists an integer x such that x +6x+9 = 0.” Proof Idea. Why do we believe this claim? • we can factor x +6x+9 = 0 to get (x+3)(x+3) = 0 2 • So, we know that if we let x = −3, then x + 6x + 9 = 0. Claim 3. “There does not exist a largest natural number.” Proof Idea. Why do we believe this claim? • Pick any arbitrary natural number x. • We know by basic arithmetic, that x+1 is a natural number and larger than x. 31 www.notesolution.com Formal Proof Structure Let’s formalize each of the previous claims. 2 Claim 1. Let xbe any natural number. If x ≥ 2 then (x + 2) ≥ 16. Q. How can we re-write Claim 1 in logical notation? ∀x ∈ N ,x ≥ 2 → (x + 2) 2 ≥ 16. Q. How can we prove a statement for all natural numbers? Let x be any arbitrary number. Q. How can we formally talk about “if, then”? We suppose that x ≥ 2 and then show that (x + 2) ≥ 16 is true. 32 www.notesolution.com Proof ∀x ∈ N ,x ≥ 2 → (x + 2) ≥ 16 Let x be an arbitrary numberNin Suppose x ≥ 2 . Then, by arithmetic x + 2 ≥ 2 + 2 = 4. And, by squaring both sides, gives (x + 2) ≥ 16 2 Therefore, x ≥ 2 → (x + 2) ≥ 16. Since x is an arbitrary natural number, N,x ≥ 2 → (x + 2 2) ≥ 16. 33 www.notesolution.com 2 Claim 2. “There exists an intxsuch thax + 6x + 9 = 0.” Q. In logic? ∃x ∈ Z,x + 6x + 9 = 0 Q. How can we formally prove a statement with there exists? Pick a value for the variable. Proof. Letx = −3. 2 2 Then, x + 6x + 9 = (−3) + 6(−3) + 9 = 0 Thus, x + 6x + 9 = 0 2 Since x ∈Z , ∃x ∈Z,x + 6x + 9 = 0. 34 www.notesolution.com Claim 3. “There does not exist a largest natural number.” Q. In logic? ∀x ∈ N,∃y ∈ N,x < y Notice that we have two quantiﬁers. Q. Does the order of the quantiﬁers matter? yes! ∃y ∈ N ,∀x ∈ N ,x < y says that there exists a largest number. Proof. Let x be an arbitrary natural number. Let y = x + 1. Then y N . Then, x < x + 1 = y. Therefore, x < y. Since y ∈N , ∃y N ,x < y Since x is an arbitrary natural numberN,∃y ∈ N,x < y. 35 www.notesolution.com Review of Proof Structure Universal Quantiﬁer. ∀x ∈ D,p(x) → q(x) Let x ∈ D. Suppose p(x) . . q(x) Therefore, p(x) → q(x) Since x is an arbitrary element in D, ∀x ∈ D,p(x) → q(x). Existential Quantiﬁer. ∃x ∈ D,p(x) Let x = a speciﬁc value. Then x ∈ D. prove this! Proof of.p(speciﬁc value). . Thus, p(x). Since x ∈ D,∃x ∈ D,p(x). 36 www.notesolution.com More Challenging Proofs. √ Claim 4. 2 is an irrational number. Proof Idea. Why do we believe this claim? • Use the Fundamental Theorem of Arithmetic. Any integer N can be represented as a product of primes. Such a representation is unique up to the order of prime factors. • We will derive a contradiction. √ • Assume that 2 is rational. √ p • Therefore, 2 = .q 2 • Squaring both sides: 2 = p2so 2q = p 2 q • How many prime factors does p2 have? q2? p has twice as many factors as p, so an even number and similarly for q . • What is the contradiction? We have the same number being represented by an even number of factors and by an odd number of factors contradicting the Fundamental Theorem of Arithmetic. 37 www.notesolution.com Claim 4, Formalized √ Claim 4. 2 is an irrational number. Q. What does it mean for a number x to be rational? There exist integers p,q such that x = q Q. How can we express “ 2 is an irrational number” using this deﬁnition? √ (⋆) ∀p ∈ Z,∀q ∈ Z, 2 ▯= . q Q. We only know how to prove universally quantiﬁed statements of the form p → q. How can we convert (⋆) into this form? √ (⋆⋆) ∀p ∈ Z,∀q ∈ Z,T → 2 ▯=p q Q. What is the contrapositive of (⋆⋆)? √ p ∀p ∈ Z,∀q ∈ Z, 2 = q→ F So we can prove the contrapositive instead of (⋆⋆)! 38 www.notesolution.com √ RTP. ∀p ∈ Z,∀q ∈ Z,T → 2 ▯=p q Proof by Contradiction. Let p ∈Z . Let q ∈ Z √ √ Suppose 2 = p, ie.,2 is rational. q 2 Then, 2 = 2 q So, 2q = p 2 2 Thus, the number o2 prime factors of 2q is odd and the number of prime factors of p is even. This contradicts the Fun. Thm. of Arithmetic. Therefore, F. √ Therefore 2 = p→ F q √ By contrapositive, T → 2 ▯= p q √ p Since q is an arbitrary integer, Z,T → 2 ▯= q √ p Since p is an arbitrary integer,Z∀,∀q ∈Z ,T → 2 ▯= q 39 www.notesolution.com Claim 5. The product of three consecutive natural numbers is an even number. Proof Idea. Q. How can we express three consecutive numbers mathemati- cally? Let x ∈ N, then x,x + 1,x + 2. Q. Why do we believe that this is true? there will be at least one even number. • Case 1. x is even. Then even(odd)(even) is even. Why? if x is even then there exists k such that 2k = x and therefore, 2k(2k + 1)(2k + 2) = 2(number) = even. • Case 2. x is odd. Then odd(even)(odd) is even. Why? if x is odd then there exists k such that 2k+1 = x and therefore, (2k + 1)(2k + 2)(2k + 3) = 2(k + 1)(number) = 2(number) = even. 40 www.notesolution.com Claim 5 – Formalized. Claim 5. The product of three consecutive natural numbers is an even number. Q. In logic? ∀x ∈ N,∃k ∈ N,x(x + 1)(x + 2)
More Less

Related notes for CSCA67H3
Me

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.