《Mathematics for Computer》Lecture 12 proofs

6.042/18.] Mathematics for Computer Science February 3, 2005 Srini devadas and Eric Lehman Lecture notes Proof Why do you believe that 3+3=6? Is it because your second-grade teacher, Miss Dalrymple, told you so? She might have been lying, you know Or are you trusting life experience? If you have three coconuts and someone gives you three more coconuts, then you have--ahal--six coconuts. But if that is the true basis for your belief, then why do you also believe that 3,000,000,000+3,000,000,000=6,000,000,000 Surely youve never actually counted six billion of anything Maybe 3+3=6 is just"intuitively obvious", and we shouldnt talk about it anymore Hey, here is a game! I secretly put one or more dollar bills into an envelope and then put twice as many dollar bills into a second envelo n n I seal both envelopes, mix them up, and present them to you. You can pick one and look inside to see how much money it contains. Then you can either take the money in that envelope or take the unknown amount of money in the other envelope. Those are the rules. For example, suppose we play this game and you find $8 in the envelope you initially selected $8 ? What is your most profitable course? Keep the $8? Or take the unknown amount in he other envelope? Are both options equally good? This situation is hardly more com licated than having three coconuts and being given three more. Yet now the correct conclusion is far from"intuitively obvious". Seemingly plausible arguments about this problem degenerate to absurdities and contradictions So you may want to dismiss 3+3=6 and hurry along, but eventually we do have to confront the underlying question: how can we know anything in mathematics? When intuition falters as a guide to truth, how can we distinguish valid mathematics from crack pot ravings? These are show-stopper questions. Without clear answers, all the number crunching and variable juggling in mathematics is just so much nonsense

6.042/18.062J Mathematics for Computer Science February 3, 2005 Srini Devadas and Eric Lehman Lecture Notes Proofs Why do you believe that 3 + 3 = 6? Is it because your second­grade teacher, Miss Dalrymple, told you so? She might have been lying, you know. Or are you trusting life experience? If you have three coconuts and someone gives you three more coconuts, then you have— aha!— six coconuts. But if that is the true basis for your belief, then why do you also believe that 3, 000, 000, 000 + 3, 000, 000, 000 = 6, 000, 000, 000? Surely you’ve never actually counted six billion of anything! Maybe 3 + 3 = 6 is just “intuitively obvious”, and we shouldn’t talk about it anymore. Hey, here is a game! I secretly put one or more dollar bills into an envelope and then put twice as many dollar bills into a second envelope: $n $2n I seal both envelopes, mix them up, and present them to you. You can pick one and look inside to see how much money it contains. Then you can either take the money in that envelope or take the unknown amount of money in the other envelope. Those are the rules. For example, suppose we play this game and you find $8 in the envelope you initially selected. $8 ? What is your most profitable course? Keep the $8? Or take the unknown amount in the other envelope? Are both options equally good? This situation is hardly more com￾plicated than having three coconuts and being given three more. Yet now the correct conclusion is far from “intuitively obvious”. Seemingly plausible arguments about this problem degenerate to absurdities and contradictions. So you may want to dismiss 3 + 3 = 6 and hurry along, but eventually we do have to confront the underlying question: how can we know anything in mathematics? When intuition falters as a guide to truth, how can we distinguish valid mathematics from crack￾pot ravings? These are show­stopper questions. Without clear answers, all the number crunching and variable juggling in mathematics is just so much nonsense

The Two-Envelopes game Here are some "solutions You picked an envelope at random, so you were just as likely to pick the one with more dollars as the one with fewer. Therefore if you see $8 then the other envelope is equally likely to contain either $4 or $ 16. On average, the other envelope contains(4+16)/2= 10 dollars, which is more than the $8 you see. So you should clearly switch to the unopened envelope However, a similar argument applies no matter what amount you see initially So you should always switch, regardless of the amount in the first envelope Thus, the best strategy is to pick one envelope and then, without even bothering to look inside, take the amount of money in the other. But that's absurd You were just as likely to pick the envelope with more dollars as with fewer So, on average, the amount of money in the envelope you picked is the same as the amount in the unopened envelope. So staying or switching makes no difference But what if you saw $1? In that case, you could be certain that the other enve- lope contained $2. So your strategy would make a difference Look at the problem from my perspective. Clearly, I should not put $1 in either envelope; that would give you a big advantage. If you opened the envelope with $l, then you would know to switch. But then if you see $2 in an envelope, you know that the other envelope must contain $4 since we just ruled out $1. So you also have a big advantage in this situation. My only choice is to never put $2 in an envelope either. And I cant use $3; if you saw that, you'd know the other envelope held $6. And if you see $4, you know the other envelope must contain $8. Apparently, I can t run the game at all! Were revisit this problem later in the term when we study probability

2 Proofs The Two­Envelopes Game Here are some “solutions”: • You picked an envelope at random, so you were just as likely to pick the one with more dollars as the one with fewer. Therefore, if you see $8, then the other envelope is equally likely to contain either $4 or $16. On average, the other envelope contains (4 + 16)/2 = 10 dollars, which is more than the $8 you see. So you should clearly switch to the unopened envelope. However, a similar argument applies no matter what amount you see initially. So you should always switch, regardless of the amount in the first envelope. Thus, the best strategy is to pick one envelope and then, without even bothering to look inside, take the amount of money in the other. But that’s absurd! • You were just as likely to pick the envelope with more dollars as with fewer. So, on average, the amount of money in the envelope you picked is the same as the amount in the unopened envelope. So staying or switching makes no difference. But what if you saw $1? In that case, you could be certain that the other enve￾lope contained $2. So your strategy would make a difference! • Look at the problem from my perspective. Clearly, I should not put $1 in either envelope; that would give you a big advantage. If you opened the envelope with $1, then you would know to switch. But then if you see $2 in an envelope, you know that the other envelope must contain $4 since we just ruled out $1. So you also have a big advantage in this situation. My only choice is to never put $2 in an envelope either. And I can’t use $3; if you saw that, you’d know the other envelope held $6. And if you see $4, you know the other envelope must contain $8. Apparently, I can’t run the game at all! We’re revisit this problem later in the term when we study probability

Proofs 1 The axiomatic Method The standard procedure for establishing truth in mathematics was invented by Euclid,a mathematician working in Alexadria, Egypt around 300 BC. His idea was to begin with five assumptions about geometry, which seemed undeniable based on direct experience (For example, There is a straight line segment between every pair of points. )Proposi tions like these that are simply accepted as true are called axioms Starting from these axioms, Euclid established the truth of many additional proposi tions by providing proofs". A proof is a sequence of logical deductions from axioms and previously-proved statements that concludes with the proposition in question. You probably wrote many proofs in high school geometry class, and you'll see a lot more in this course There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work Important propositions are called theorems A lemma is a preliminary proposition useful for proving later propositions A corollary is an afterthought, a proposition that follows in just a few logical steps from a theorem The definitions are not precise. In fact, sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove Euclids axiom-and-proof approach, now called the axiomatic method, is the founda- tion for mathematics today. Amazingly, essentially all mathematics can be derived from just a handful of axioms called ZFC together with a few logical principles. This does not completely settle the question of truth in mathematics, but it greatly focuses the issue You can still deny a mathematical theorem, but only if you reject one of the elementary ZFC axioms or find a logical error in the proof 1.1 Our Axioms For our purposes, the ZFC axioms are too primitive- by one reckoning, proving that 2+2=4 requires more than 20,000 steps! So instead of starting with ZFC, were going to take a huge set of axioms as our foundation: we'll accept all familiar facts from high school math This will give us a quick launch, but you will find this imprecise specification of the axioms troubling at times. For example, in the midst of a proof, you may find yourself wondering, " Must I prove this little fact or can I take it as an axiom? Feel free to ask for guidance, but really there is no absolute answer. Just be upfront about what you're assuming, and don' t try to evade homework and exam problems by declaring everything an axiom

Proofs 3 1 The Axiomatic Method The standard procedure for establishing truth in mathematics was invented by Euclid, a mathematician working in Alexadria, Egypt around 300 BC. His idea was to begin with five assumptions about geometry, which seemed undeniable based on direct experience. (For example, “There is a straight line segment between every pair of points.) Proposi￾tions like these that are simply accepted as true are called axioms. Starting from these axioms, Euclid established the truth of many additional proposi￾tions by providing “proofs”. A proof is a sequence of logical deductions from axioms and previously­proved statements that concludes with the proposition in question. You probably wrote many proofs in high school geometry class, and you’ll see a lot more in this course. There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work. • Important propositions are called theorems. • A lemma is a preliminary proposition useful for proving later propositions. • A corollary is an afterthought, a proposition that follows in just a few logical steps from a theorem. The definitions are not precise. In fact, sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove. Euclid’s axiom­and­proof approach, now called the axiomatic method, is the founda￾tion for mathematics today. Amazingly, essentially all mathematics can be derived from just a handful of axioms called ZFC together with a few logical principles. This does not completely settle the question of truth in mathematics, but it greatly focuses the issue. You can still deny a mathematical theorem, but only if you reject one of the elementary ZFC axioms or find a logical error in the proof. 1.1 Our Axioms For our purposes, the ZFC axioms are too primitive— by one reckoning, proving that 2 + 2 = 4 requires more than 20,000 steps! So instead of starting with ZFC, we’re going to take a huge set of axioms as our foundation: we’ll accept all familiar facts from high school math! This will give us a quick launch, but you will find this imprecise specification of the axioms troubling at times . For example, in the midst of a proof, you may find yourself wondering, “Must I prove this little fact or can I take it as an axiom?” Feel free to ask for guidance, but really there is no absolute answer. Just be upfront about what you’re assuming, and don’t try to evade homework and exam problems by declaring everything an axiom!

The ZFC Axioms omitted. The variables denote distinct sets. Essentially all of mathematics can These are the axioms of Zermelo-Fraenkel set theory with some technicaliti derived from these axioms together with a few principles of logic Extensionality. Sets are equal if they contain the same elements 2(2∈x兮z∈y)→x=y Union. The union of a collection of sets is also a set yvz(u(z∈∧∈x)→z∈y) Infinity. There is an infinite set; specifically, a set contained in the union of its ele- ments y(r(x∈y)∧z(z∈y→3u(z∈∧∈y) Power Set. All subsets of a set form another set y(v(∈z→t∈x)→z∈y) Replacement. The image of a function is a set vyz(0(,2)→2=y)→32(z∈y分3(∈x∧叭(m,z) Regularity. Every nonempty set contains a set disjoint from itself y(y∈x)→(y∈xAVz(z∈y→nz∈x) Choice. We can pick one element from each set in a collection yav(∈A∈x)→3u((∈uA∈t)∧(u∈tAt∈y)分u=v) Were not going to be working with the ZFC axioms in this course. We just thought you might like to see them

4 Proofs The ZFC Axioms These are the axioms of Zermelo­Fraenkel set theory with some technicalities omitted. The variables denote distinct sets. Essentially all of mathematics can be derived from these axioms together with a few principles of logic. Extensionality. Sets are equal if they contain the same elements: ∀z(z ∈ x ⇔ z ∈ y) ⇒ x = y Union. The union of a collection of sets is also a set: ∃y∀z(∃w(z ∈ w ∧ w ∈ x) ⇒ z ∈ y) Infinity. There is an infinite set; specifically, a set contained in the union of its ele￾ments. ∃y(∃x(x ∈ y) ∧ ∀z(z ∈ y ⇒ ∃w(z ∈ w ∧ w ∈ y))) Power Set. All subsets of a set form another set. ∃y∀z(∀w(w ∈ z ⇒ w ∈ x) ⇒ z ∈ y) Replacement. The image of a function is a set. ∀w∃y∀z(φ(w, z) ⇒ z = y) ⇒ ∃y∀z(z ∈ y ⇔ ∃w(w ∈ x ∧ φ(w, z))) Regularity. Every nonempty set contains a set disjoint from itself. ∃y(y ∈ x) ⇒ ∃y(y ∈ x ∧ ∀z(z ∈ y ⇒ ¬z ∈ x)) Choice. We can pick one element from each set in a collection. ∃y∀z∀w((z ∈ w ∧ w ∈ x) ⇒ ∃v∃u(∃t((u ∈ w ∧ w ∈ t) ∧ (u ∈ t ∧ t ∈ y)) ⇔ u = v)) We’re not going to be working with the ZFC axioms in this course. We just thought you might like to see them

Proofs 1.2 Proofs in practice n principle, a proof can be any sequence of logical deductions from axioms and previously- proved statements that concludes with the proposition in question. This freedom in con- structing a proof can seem overwhelming at first. How do you even start a proof? Here's the good news: many proofs follow one of a handful of standard templates Proofs all differ in the details, of course, but these templates at least provide you with an outline to fill in. Well go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit ogether; one may give you a top-level outline while others help you at the next level of detail. And well show you other, more sophisticated proof techniques later on The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You're certainly free to say things your own way instead were just giving you something you could say so that you're never at a complete loss 2 Proving an implication An enormous number of mathematical claims have the form "If P, then Q"or, equiva lently, "P implies Q". Here are some examples ·( Quadratic Formula)fax2+bx+c=0anda≠O, then x=(-b± 4ac)/2a . Goldbach's Conjecture)If n is an even integer greater than 2, then n is a sum of two rimes ·If0<x<2,then-x3+4x+1>0. There are a couple standard methods for proving an implication 2.1 Method #1 In order to prove that P implies Q 1. Write,"Assume p 2. Show that Q logically follows

� Proofs 5 1.2 Proofs in Practice In principle, a proof can be any sequence of logical deductions from axioms and previously￾proved statements that concludes with the proposition in question. This freedom in con￾structing a proof can seem overwhelming at first. How do you even start a proof? Here’s the good news: many proofs follow one of a handful of standard templates. Proofs all differ in the details, of course, but these templates at least provide you with an outline to fill in. We’ll go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit together; one may give you a top­level outline while others help you at the next level of detail. And we’ll show you other, more sophisticated proof techniques later on. The recipes below are very specific at times, telling you exactly which words to write down on your piece of paper. You’re certainly free to say things your own way instead; we’re just giving you something you could say so that you’re never at a complete loss. 2 Proving an Implication An enormous number of mathematical claims have the form “If P, then Q” or, equiva￾lently, “P implies Q”. Here are some examples: • (Quadratic Formula) If ax2 + bx + c = 0 and a = 0, then x = (−b ± √b2 − 4ac)/2a. • (Goldbach’s Conjecture) If n is an even integer greater than 2, then n is a sum of two primes. • If 0 ≤ x ≤ 2, then −x3 + 4x + 1 > 0. There are a couple standard methods for proving an implication. 2.1 Method #1 In order to prove that P implies Q: 1. Write, “Assume P.” 2. Show that Q logically follows