Class Notes (905,832)
CA (538,520)
UTSC (32,637)
CSCA67H3 (57)
Lecture

Formal proofs

21 Pages
181 Views

Department
Computer Science
Course Code
CSCA67H3
Professor
Anna Bretscher

This preview shows pages 1-3. Sign up to view the full 21 pages of the document.
Proofs
Q. What is aproof?
Aproof is aconvincing argument that astatement is true.
Q. What makes up a proof?
aset of basic statements that we agree are true for aspec-
ified domain. E.g., if D=Rthen we havethe basic rules
about arithmetic and inequalities.
Aseries of logical steps that build on previously proven
statements.
Weare concerned with the content of aproof and the structure
of the proof.
Example.
Claim 1. Let xbe anynatural number.
If x2then (x+2)216.
Proof Idea. Whydo webelievethis claim?
if x2then x+22+2=4byarithmetic
squaring both sides,gives (x+2)216
30
www.notesolution.com
Claim 2. There exists an integer xsuch that x2+6x+9=0.
Proof Idea. Whydo webelievethis claim?
wecan factor x2+6x+9=0to get (x+3)(x+3) =0
So,weknowthat if welet x=3,then x2+6x+9=0.
Claim 3. There does not exist alargest natural number.
Proof Idea. Whydo webelievethis claim?
Pickanyarbitrarynatural number x.
Weknowbybasic arithmetic,that x+1 is anatural number
and larger than x.
31
www.notesolution.com
Formal Proof Structure
Let’sformalizeeach of the previous claims.
Claim 1. Let xbe anynatural number.If x2then (x+2)2
16.
Q. Howcan were-write Claim 1in logical notation?
xN,x 2(x+2)216.
Q. Howcan weprove a statement for all natural numbers?
Let xbe anyarbitrarynumber.
Q. Howcan weformally talk about “if,then”?
We suppose that x2and then showthat (x+2)216 is
true.
32
www.notesolution.com

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
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- ified 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 quantifiers. Q. Does the order of the quantifiers 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 Quantifier. ∀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 Quantifier. ∃x ∈ D,p(x) Let x = a specific value. Then x ∈ D. prove this! Proof of.p(specific 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 definition? √ (⋆) ∀p ∈ Z,∀q ∈ Z, 2 ▯= . q Q. We only know how to prove universally quantified 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
Unlock Document


Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

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

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit