Constructing Proofs CS 1050
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 1050 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/234144/cs-1050-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Constructing Proofs
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Sequences amp Summations CS 1050 Rosen 17 Sequence A sequence is a discrete structure used to represent an ordered list A sequence is a function from a subset of the set of integers usually either the set Ol2 or 12 3 to a set S We use the notation an to denote the image of the integer n We call an a term of the sequence Notation to represent sequence is an Examples 1 12 13 14 or the sequence an Where an 1n ne Z 124816 an Where an 2n neN 12223242 an Where an H2 116 Z Common Sequences Arithmetic a ad a2d a3d a4d n2 1 4 916 25 n3 1 8 27 64125 H4 116 81 256 625 2n 2 4 816 32 3n 3 9 27 81 243 n 1 2 6 24120 Summations Notation for describing the sum of the terms am amH an from the sequence an 1 1 amam1 an 2 aj jm j is the index of summation dummy variable The indeX of summation runs through all integers from its lower limit m to its upper limit n Examples 5 4 212ltj11234515 11 j0 ilj112 13 14 15 11 5 121j112131415 J2 Summations follow all the rules of multiplication and addition C 2 Cl2n C 2C no n1 n n 39 39l k rzarjzzar 22611 10 10 k1 n n l k l k ar l 2617 arn a 2 ar k1 k0 Telescoping Sums Ska aj l a1 a0 a2 a1 a3 a2 an an l an a0 Example 2k2k12 12 0222 1232 2242 32 42 216 0216 Closed Form Solutions A simple formula that can be used to calculate a sum Without doing all the additions Example 2k nnl k1 2 Proof First we note that k2 kl2 k2 k22k1 2k1 Since 12k12 2k1 then we can sum each side from k1 to kn n ik2 k 1222k 1 kl kl PTOOf cont k1 k1 k2 k 12 i2kZ 1 n2 02 2200 n k1 n2 n 22 k k1 n 2 kzn n 2 Closed Form Solutions to Sums Zj01nnn12 10 if 02 12 n2 nn12n16 j0 le 722n12 k1 4 1 ar a r r 1 n k 2 CWquot 2 k0 1 Double Summations i2i3i6i 11 i1 11 612182460 Sequences amp Summations CS 1050 Rosen 17 Sequence A sequence is a discrete structure used to represent an ordered list A sequence is a function from a subset of the set of integers usually either the set Ol2 or 12 3 to a set S We use the notation an to denote the image of the integer n We call a11 a term of the sequence Notation to represent sequence is an Examples 1 12 13 14 or the sequence an Where an 1n ne Z 124816 an Where an 21 HEN 12223242 an Where an H2 116 Z Common Sequences Arithmetic a ad a2d a3d a4d n2 1 4 916 25 n3 1 8 27 64125 H4 116 81 256 625 2n 2 4 816 32 3n 3 9 27 81 243 n 1 2 6 24120 Summations Notation for describing the sum of the terms am amH an from the sequence an 1 1 amam1 an2aj Jm j is the indeX of summation dummy variable The index of summation runs through all integers from its lower limit m to its upper limit n Examples J j11234515 4 10 Mm EMM j112 13 1415 1 j 1 5 1 21j112131415 j2 Summations follow all the rules of addition n n Z C12nc20 110 11 11 7 I n1 rzar 262W 2 Earl 10 10 k1 n n Telescoping Sums 2a aj1al aoa2 a1 J1 a3 a2 an an 1 an a0 Example chZ k DZ 12 0222 1232 2242 32 42 216 0216 Closed Form Solutions A simple formula that can be used to calculate a sum Without doing all the additions Example nn l k1 2 Proof First we note that k2 kl2 k2 k22k1 2k1 Since kZkl2 2k1 then we can sum each side from k1 to kn gk2 ltk 1gt212lt2k 1gt k A Proof cont k2 k 12 2k 1 k 12 12k 1 1 n2 02 2200 n n2 n 221k 2 n n n k 1 2 w Closed Form Solutions to Sums ij01nnn12 j0 if 02 12 n2 nn12n16 n 2 12 k3 n n 4 n1 Zark zar ar 1 Double Summations ii2i3i i612 i1 j1 i1 j1 i1 i1 61218246O CS Discrete Mathematics for Fail Papadimitriou amp Vazirani Lecture Variance Question At each time step I ip a fair coin If it comes up Heads Iwalk one step to the right if it comes up Tails Iwalk one step to the left How far do I expect to have traveled from my starting point after n Denoting a rightemove by 1 and a leftemove by 71 we can describe the probability space here as the set of all words of length n over the alphabet i1 each having equal probability Let the rv X denote our position relative to our starting point 0 aftern moves T us XX1X2Xn7 1 if ith toss is Heads where X 71 otherwrse Now obviously we have 0 The easiest rigorous way to see this is to note that gtlt 1 x 71 0 so by linearity of expectation 21EXl 0 Thus after n steps my expected position is 0 But of course this is not very informative and is due to the fact that positive and negative deviations from 0 cancel out What the above question is really asking is What is the expected value of our dirtance from 0 Rather than consider the rv which is a little awkward due to the absolute value operator we will instead look at the rv X2 Notice that this also has the effect of making all deviations from 0 positive so it should also give a good measure of the distance traveled However because it is the squared distance we will need to take a square root at the en Let39s calculate EXZ 1502 EX1Xz Xn2 15631th 21X1XJ 271 15092 Else EXlX In the last line here we used linearity of expectation To proceed we need to compute E013 and EXlX forif Let39s consider rstXLZ SinceXl can take on only values i1 clearly X2 1 always so EXZ 1 What about EXlX Since X and X are independent it is the case that EXlX 01 Plugging these values into the above equation gives EXZnx10 n So we see that our expected squared distance from 0 is n One interpretation of this is that we might expect to be a distance of about away from 0 after n steps However we have to be careful here we cannot 1The following fact was proved in e1ass at the same time as we proved 1inearity of expectation Lecture 20 For independent 0m variahIes XY we have EXY EXEY Ifyou missed the proof in e1ass you should try to prove it yourself from the de nition of expectation in similar fashion to the proof ofTheorem 201 Note that EXY EXEY is false for general rv39s XY as an example just look at E Z in the present example CS 70 Fall 2006 Lecture 23 1 simply argue that EXZ Why not We will see shortly see ChebysheV39s Inequality below how to make precise deductions about from knowledge of EX For the moment however let39s agree to View EXZ as an intuitiVe measure of spread of the rV X In fact for a more general rV with expectation u what we are really interested in is 7 W the expected squared distancefrom the mean In our random walk example we had y 0 so 7 m2 just reduces to De nition 231 Variance For a rV X with expectation y the Variance ofX is de ned to be VarX 7 w 7 W The square root VarX is called the standard deViation of X The point of the standard deViation is merely to undo the squaring in the Variance Thus the standard deViation is on the same scale asquot the rV itself Since the Variance and standard deViation differ just by a square it really doesn39t matter which one we choose to work with as we can always compute one from the other immediately We shall usually use the Variance For the random walk example aboVe we haVe that VarX It and the standard deViation ofX is The following easy observation giVes us a slightly different way to compute the Variance that is simpler in many cases Theorem 231 For a rVX with expectation y we have VarX EXZ 7 2 Proof From the de nition of Variance we haVe VarX EX I02 EXZ 2MX HZ EXZ 2MEX M2 EXZ 2 In the third step here we used linearity of expectation D Let39s see some examples of Variance calculations 1 Fair die LetX be the score on the roll ofa single fairdie Recall from an earlierlecture that So we just need to compute which is a routine calculcation 2 1 2 2 2 2 2 2 91 EX612 3 4 5 6 Thus from Theorem 221 91 49 35 VarX EXZ 7 15002 K 7 I 12 2 Biased coin Let X the the number of Heads in It tosses of a biased coin with Heads probability p ie X has the binomial distribution with parameters mp We already know that rtp Writing 1 39f 39th t 39 H d39 as usualX X1Xz Xn whereXl l 1 gs ls ea we haVe 0 otherw1se EXZ EX1Xz Xn2 2L1 EX 21 EXlX quotXP 1 W2 7Lsz rtpl 7p CS 70 Fall 2006 Lecture 23 2 In the third line here we have used the facts that EXi2 p and that EXX EXEX p2 since X X l are independent Note that there are nn 7 1 pairs 139 j with i 7 j Finally we get that VarX EX2 7 EX2 np1 7p2 As an example for a fair coin the expected number of Heads in n tosses is g and the standard deviation is 2 9 Poisson distribution Let X have the Poisson distribution with parameter A We saw in the last lecture that EX A And we also have 00 Ari 00 7A A171 171 7 A A 1 71 w Aiil w EX22i2e A7A ie AA i71e 7 e z lt71 lt71 0 Check you follow each of these steps In the last step we have noted that the two sums are respec tively EX and EiPrX i1 Finally we get VarX EX2 7 EX2 A So for a Poisson random variable the expectation and variance are equal 5 Number of xed points Let X be the number of xed points in a random permutation of n items ie the number of students in a class of size n who receive their own homework after shuf ing We saw in an earlier lecture that EX 1 regardless of n To compute EX2 write X X1 X2 I Xn Where Xi 1 if i is a xed point 0 otherw1se Then as usual we have n EX2 EEX2EXiXl 1 i1 i j Since X is an indicator rv we have that EXi2 PrX 1 In this case however we have to be a bit more careful about EXX note that we cannot claim as before that this is equal to EXEX because X and X l are not independent why not But since both X and X l are indicators we can compute EXX directly as follows EXX PrX1AX 1 Prboth i and j are xed points 7 1 7 nn7139 Check that you understand the last step here Plugging this into equation 1 we get EX2 nx mi 1 x W17 11 2 Thus VarX EX2 7 EX2 271 1 Le the variance and the mean are both equal to 1 Like the mean the variance is also independent of n Intuitiver at least this means that it is unlikely that there will be more than a small number of xed points even when the number of items n is very large Chebyshews Inequality We have seen that intuitively the variance or more correctly the standard deviation is a measure of spread or deviation from the mean Our next goal is to make this intuition quantitatively precise What we can show is the following 2Notice that in fact VarX 2VarX and the same was true in the random walk example This is in fact no coincidence and it depends on the fact that the X are mutually independent See Problem 1 on Homework 11 So in the independem case we can compute Variances of sums Very easily Note that this isn39t the case however in example 4 CS 70 Fall 2006 Lecture 23 3 Theorem 232 Chebyshev s Inequality For a random Variable X with expectation y andfor any a gt 0 VarX 7 gt lt 7 PrHX m a a2 Before proving Chebyshev39s inequality let39s pause to consider what it says It tells us that the probability of any given deviation 1 from the mean either above it or below it note the absolute value sign is at most 32 As expected this deviation probability will be small if the variance is small An immediate corollary of Chebyshev39s inequality is the following Corollary 233 For a random Variable X with expectation y and standard deviation 0 x Va X 1 PrllX Ml 2 I30 S 7 I3 Proof Plug a 30 into Chebyshev39s inequality D So for example we see that the probability of deviating from the mean by more than say two standard deviations on either side is at most 41 In this sense the standard deviation is a good working de nition of the width or spread of a distribution We should now go back and prove Chebyshev39s inequality The proof will make use of the following simpler bound which applies only to nonnegative random variables ie rv39s which take only values 2 0 Theorem 234 Markov s Inequality Fora non7negative random VariableX with expectation M and any a gt E X PrX 2 a g Proof From the de nition of expectation we have Eaax PrX a 22mm PrX7a 2 azgmx 7 a PrX 2 a The crucial step here is the second line where we have used the fact that X takes on only non7negative values Why is this step not valid otherwise D Now we can prove Chebyshev39s inequality quite easily Proof of Theorem 222 De ne the rv Y X 7 a Note that EY 7 m2 VarX Also notice that the probability we are interested in PrlX 7 M 2 a is exactly the same as PrY 2 12 Why Moreover Y is obviously non7negative so we can apply Markov39s inequality to it to get PrY 2 012 g Llt gt LTEX a a This completes the proof D Let39s apply Chebyshev39s inequality to answer our question about the random walk at the beginning of the lecture Recall thatX is our position after n steps and that 0 VarX n Corollary 223 says that CS 70 Fall 2006 Lecture 23 4 Doing Sums What is 22 1 k0 ar a 26Wquot 1th k0 7 1 Leta 1 andr 12 n k2n11 What if k starts at 1 22 iz k iz k 20 k1 k0 2n1 1 2n 2n1 1 2n r 423 1 2quot 2quot 2quot 1 2n 1 So we have two more Closed form solutions n 2n1 1 24 quot 2quot 1 24 Solve 239Hc0 2322 quot i2 q224 i2 Z HCO 2 cli2i Z HCO 2ncl2n 11 1 y2 2 Z HCO 612 1 2H 2 27 160 6122 1 1 2 14 quk4 200 Find 2k k100 200 200 zkzzk gik k100 k1 200201 99100 2 2 20100 49500 15150 Derive the closed form for 262 kl First we note that k3 kl3 3k23kl then we sum both sides of the equation from 1 to n 1 1 71 2M3 k 13 23k2 3k1 kl kl On the left hand side we have a telescoping sum so it is equal to n3 n3 i k2 i3k i1 k1 k1 k1 2 3ampth2 3i n k1 k1 3ik23n1 n Rearranging the terms we get Direct Proofs 1 Example 1 De nition An integer n is even if and only if there exists and integer k such that 2k n Let n be an integer If n is even then n2 is even 11 Proof in Symbols Given Inferred Rule of Inference n is even Elk E K2k n k is an integer such that 2k n 4k2 n2 2 2 n2 Let I be an integer such that l 2k2 21 n2 Ell 6 M21 n2 n2 is even modus ponens using De nition of even and given existential instantiation Table 2 p174 algebra square 2k n factor out 2 closure of integers algebra substitute 1 for 2k2 existential generalization Table 2 p174 Inferred 6 and de nition of even algebra 12 Proof in words We assume that n is even From the de nition of even we know that there is an integer k such that 2kn 1 We can square both sides of equation 1 to that 4k2 n2 We can then factor out a 2 and get 2 218 n2 2 Because the integers are closed under addition and multiplication we know that there exists an integer I such that 2192 I When we substitute 1 into equation 2 we that 21 n2 Because we have found an integer I such that 21 n2 the de nition of even tells us that n2 is even I 2 Example 2 De nition A number s is rational if and only if there exists two integers a and y such that 5 If s and t are rational numbers then s t is also rational 21 Proof in Symbols Given Inferred Rule of Inference s is rational Elab E Z 5 de nition of Rational t is rational s for some ab E Z existential instantiation Table 2 p174 Elcd 6 Mg t de nition of Rational t for some cd E Z existential instantiation Table 2 p174 s t 5 algebra substitution 5 t 01 algebra multiplication of fractions Let n be an integer such that n ad be closure of integers Let in be an integer such that m bd closure of integers s t algebra substitution 539 t is rational de nition of Rational 22 Proof in words Let s and t be rational numbers From the de nition of rational we know that there exist integers a and b such that s Likewise we know that there exist integers c and 1 such that t g From here we can substitute for s and for t and that s t g This is equivalent to saying that s t Mg Let n ad be and let in bd Because the integers are closed under addition and multiplication we know that n and m are integers Thus we have found two integer in and n such hat s t Hence we know that s t is rational by de nition I 3 Example 3 De nition Let a and b be integers We say a divides b written ab if and only if Elk 6 Mali b Let a b and c be integers If ab and ac then abc 31 Proof in Symbols Given ab ac Inferred Rule of Inference 1 Elk 6 Mali b de nition of divices 2 Ell E Zal c de nition of divides 3 ak b for some k E Z existential instantiation 4 aj c for some j E Z existential instantiation 5 be akaj algebra multiply 4 and 5 6 be akaj algebra associtivitg of integers 7 Let I E Z kaj closure of integers under multiplication 8 be al algebra substitue 7 into 6 9 abc de nition of divides Verify that your set of cases is complete Proof by Cases When writing a proof by cases be sure to do the following Clearly identify your cases Address each case separately Do not address them in parallel that it accounts for all possibilities Have at least one concluding sentence after you have addressed all cases 1 Example 1 If n is an integer then n3 n is even 11 Proof in Symbols Case 1 If n is even then n3 n is even Given Inferred Rule of Inference n is even Elk E 2k 2 n n 2k for some integer k n3 8k3 n3 n 8k3 2k n3 n 24192 19 Let I 4k2 k n3 n 21 n3 n is even de nition of even existential instantiation algebra cube n 2k algebra substitute algebra factor out a 2 closure of integers algebra substitution de nition of even Case 2 If n is odd then n3 n is even Given Inferred Rule of Inference n is odd n3 n 21 n3 n is even Elk E K2k 1 n n 2k 1 for some integer k de nition of odd existential instantiation n3 8k3 12192 6k 1 algebra cube n 2k 1 n3 n 8193 12192 6k 1 2k 1 algebra substitution n3 n 8193 12192 8k 2 algebra collect like terms n3 n 24k3 M2 4k 1 algebra factor out a 2 Let I 4193 M2 4k 1 closure of integers algebra substitution de nition of even Proof if n is an integer then n3 3 is even 1 Example 1 The sum of the rst 71 odd integers is 712 We will prove this by induction on 71 As a basis consider the case when 71 1 The sum of the rst odd integer is 1 which is equal to 12 Thus our base case is true For our inductive step we will inductively assume that the sum of the rst n odd integers is 712 and we will prove that the sum of the rst n 1 odd integers is 71 12 Our inductive hypothesis tells us that 1232n 1n2 1 The 71 1 odd integer is 272 1 2 271 1 Therefore we calculate the sum of the rst 71 1 odd integers by adding 271 1 to equation 1 This gives 1232n 17122n1 2 When we expand 71 12 we can see that 71 12 722 271 1 Substituting this into equation 2 yields 1232n 1n12 3 Thus we now have that the sum of the rst 71 1 odd integers is 71 12 as desiredl 1I would much prefer that you write 2171 2i 1 instead of 1 2 3 2n 1 However don t use the Z notation if it will cause you to make mistakes De n ition A g B if and only if every element of A is also an element of B Let A B and C be sets If A g B and B Q C then A g C 1 Proof in Symbols Given 1 A g B 2 B Q C Inferred Reasoning 1 Let a be an arbitrary element of A 2 Va E A E B definition of subset 3 a E B universal instantiation using 1 and 2 4 Vb E B b E C definition of subset 5 a E C universal instantiation using 5 and 4 6 Va E A E C universal generalization of 1 and 5 7 A g C definition of subset 2 Proof in Words Let A B and C be sets such that A g B and B Q C We will prove that A g C We consider two cases It A 0 In this case we can immediately conclude that A g C because the empty set is a subset of every set A Because we know that A is not empty we may let a be an arbitrary element of A From the de nition of subset we know that every element of A including a is an element of B Thus a E B Likewise we know that a E C Because we have shown that any arbitrary element of A is also an element of C we can that every element of A is also an element of C Thus the de nition of subset tells us that A g C I would also be acceptable to begin this proof follows Let a be an arbitrary element of A We may assume such an 3 exists because otherwise the theorem is trivially true 1 CS 70 Discrete Mathematics for Spring PapadimitriouVazirani Lecture 1 Purpose Oi the course CS 70 is a new course designed to complement Math 55 We will focus on fewer topics driven by compu tational tasks We hope to make the course more relevant to CS students and hence to instill a deeper and longerlasting understanding of the underlying mathematics What we want to teach Precise reliable powerful thinking will allow you to use and develop more complex and subtle ideas in CS well beyond the obvious brute force approach to every problem and will help you to avoid silly errors on all your CS nal exams The ability to state and prove nontrivial facts in particular about programs will enable you to write rigorously correct programs which in turn provide solid building blocks for evermore complex yet still reliable systems Mathematical foundations and ideas useful throughout CS will provide familiarity with logic inductively de ned structures integer and polynomial arithmetic and probabilitiesiconcepts that underly all of the more advanced courses in CS Course outline abbreviated Propositions and Proofs Mathematical lnduction recursion the stable marriage problem Propositional Logic automated proof and problemsolving Arithmetic Algorithms gcd primality testing the RSA cryptosystem Polynomials and their Applications errorcorrecting codes secret sharing Probability and Probabilistic Algorithms load balancing hashing probabilistic constructions condi tional probability Bayesian inference Diagonalization SelfReference and Uncomputability Propositions and Proofs Many of the unenlightened believe proofs to be pointless formal exercises in guessing a way through a maze to reach a 2400yearold fortune cookie Far from it We all like to say things CS 70 Spring 2004 Lecture 1 1 PROPOSlTlON THEOREM WORLD MODEL AXlOMS PROOF This encryption system cannot be broken My program works ef ciently in all cases There are no circumstances under which I would lie to Congress It is inconceivable that our legal system would execute an innocent person and so on Few of us like to say things that turn out to be false Proof means never having to say you re sorryiit provides a means for guaranteeing your claims once and for all1 What we would like to do now is to make these concepts more precise Most discrete mathematics courses just get on with doing proofs this isn t a bad idea but does skip over some important concepts Proofs in mathematics and computer science as opposed to law and politics require a precisely stated proposition to be proved A proposition is a sentence that is either true or false2 A theorem informally speaking is a proposition that is guaranteed by a proof Examples of propositions 1a Some mammals lay eggs 1b Some mammals have feathers 2 The acceleration of a rigid body is proportional to the force applied 3 The angles of a triangle add up to 180 degrees 4 For all nonnegative integers rt r12 rt 41 is prime 5 For all integers rt if rt gt 2 then there are no positive integers a b c such that a b c 6 For every even integer rt gt 2 there are two primes a and b such that a b rt It is important to note that every proposition is true or false with respect to a possible world A world or a model in logical terminology is conversely something with respect to which every proposition of interest is either true or falseithat is it is completely speci ed For physics chemistry biology etc which are empirical sciences we are usually interested in truth with respect to the real worldithe one we actually live in But of course we don t know which one that is For example 1a happens to be true in the real world but could easily have been otherwise whereas 1b may or may not be true Exercisez what could we mean by this Could one prove that 1b is false 2 is one of Newton s laws It was assumed to be incontrovertibly true for many years and many explana tions were given for why it could not possibly be otherwise but it is in fact false in the real world 3 Now mathematicians physicists and engineers have been proving theorems in Newtonian mechanics for centuries and continue to do so As a matter of physical fact most of these theorems are false in the real world They are however still theorems in Newtonian mechanics An incorrect proof is not a proof but a false theorem may still be a theorem provided it follows logically from a speci ed set of axioms An axiom is a proposition that is assumed to be true without proof ln Newtonian mechanics Newton s laws are taken as axiomatic Proof therefore is a means of showing that a theorem follows logically from a set of axioms 1 What about incorrect proofs you may ask An incorrect proof is not a proof any more than arti cial grass is grass 2Sentences that are not propositions include questions and commandsithese cannot be true or false although they can be perceptive or absur Many people state that Newton s laws were disproved by Einstein This is not the case Einstein merely proposed laws that are inconsistent with Newton s Empirical laws such as Newton s can only be disproved by observations or by discovering an internal inconsistency CS 70 Spring 2004 Lecture 1 2 FOLLOWS LOGlCALLY MODELS Now we have to explain what is meant by follows logically A proposition B follows logically from another proposition A if B is true in all possible worlds in which A is true This relationship is often written as A I B which can be pronounced A logically entails B If one draws a picture of the set of worlds where A holds and the set of worlds where B holds the set where A holds will be contained within the set where B holds whenever A I B More mathematically let M A be the set of worlds where A holds and M B the set of worlds where B holds we call these worlds the models of A and B Then A B ifand onlyif MA MB This relationship is shown in Figure 1a The direction of the Q may be somewhat counterintuitive nor mally we think of A being stronger or bigger than B if A entails B One route to reain intuition is to remember that every axiom added to A reduces the set of possible worlds where A holds so makes it more feasible for this set to be contained within the set of Bworlds Figure 1b Figure 1 a A entails B iff B is true in every world where A is true b Adding axioms toA to make A reduces the set of possible worlds the gure shows a case where this allows A to entail B We said earlier that a proof guarantees a proposition More precisely using the de nition of logical entail ment we see that a proof guarantees the truth of a theorem to the extent that the axioms themselves are true We will see in the next section some of the methods by which this guarantee is provided Let us return to the consideration of the propositions in our list above Proposition 3 The angles of a triangle add up to 180 degrees is one of Euclid s axioms It is simply postulated to be true In fact it is true only in planar geometry A triangle inscribed on the surface of a sphere can violate the axiom and general relativity says that space itself is curved so geometries violating the axiom are actually more realistic As with Newtonian mechanics the theorems that Euclid and many generations of schoolchildren after him derived are true only in an idealized at universe When we come to purely mathematical propositions the situation is a little different mathematical axioms are taken as de ning the world under discussion rather than attempting to describe it For example Peano s axioms de ne what it means to be a natural number nonnegative integer O is a natural number If n is a natural number sn is a natural number CS 70 Spring 2004 Lecture 1 3 UNlVERSAL QUANT F ER CUUNTEREXAMPLE CUNJECTURE EXlSTENTlAL QUANT F ER where is the successor function We usually write s0 as 1 ss0 as 2 and so on From this simple beginning we can build up more de nitionsiaddition multiplication subtraction division prime numbers and so on Theorems in mathematics are usually true because the axioms of mathematics are usually true by de nition4 Mathematical texts usually talk about proving that a proposition is true or false which is really shorthand for entailed by the standard axioms or inconsistent with the standard axioms We will do the same thing but we will try to be careful about citing the axioms that are required Why do this First it s a good practice because it eliminates some errors that occur when one accidentally invokes a false axiom second it often reveals opportunities to prove a more general theorem because some axioms may not be required for the proof and third the axioms you re relying on may later turn out to be inconsistent so it s good to keep a record This third possibility is extremely unlikely for most of the proofs we will do At this point we ll introduce a little bit more notation Let us write proposition 4 as 4 Vn n2 n 41 is prime The V symbol is the universal quanti er here it binds the variable n and means for all n Strictly speaking the proposition should be written 4 VnE Nn2n41 is prime where N is the set of natural numbers This quali cation is too often omitted when the context makes it only somewhat obvious How does one prove a universally quanti ed statement We can check that it is true for lots of examples n O n 1 and so on all the way up to n 39 Does this constitute a proof Of course not The proposition is false because 402 40 41 is not prime The case n 40 is called a counterexample for the proposition Proposition 5 is Fermat s last theorem It has been known for over 300 years and called a theorem for much of that time because Fermat claimed to have a proof and no counterexample was ever found It recently became a proper theorem when Andrew Wiles developed a proof several hundred pages long Proposition 6 is Goldbach s conjecture A conjecture is a proposition that has not been proved or dis proved Using quanti er notation it is written Vn if n is even then 3ab such that a and b are prime and a b n Here 3 is the existential quanti er meaning For some or There exists For any particular n the existentially quanti ed statement can be proved simply by nding any particular a and b whereas of course the universal quanti cation over n cannot be proved by exhibiting examples It can be disproved by exhibiting a counterexample but none has been found despite testing up to enormous values of n we suspect the conjecture is true One may say Surely something so simple ought to be provable easily But Fermat s last theorem has turned out so far to have a very complex proof and Kurt Godel s famous lncompleteness Theorem showed that there are true propositions that have no proof in arithmetic Unfortunately there is also no way to tell if Goldbach s conjecture is one of those We have gone on long enough about propositions and proofs Let s start proving some propositions 4We say usually because occasionally a proposed set of axioms for some part of mathematics is shown to be inconsistentithat is selfcontradictoryiand therefore cannot be true 5Godel s lncompleteness Theorem is not generally a good excuse for being unable to nd a proof in a homework question CS 70 Spring 2004 Lecture 1 4 CUNJUNCT UN lMPUCATlUN meter P Q P PAQ PQ PgtQ P gtQ False False True False False True True False True True False True True False True False False False True False False True True False True True True True Table 1 Truthtable de nitions of the standard logical operators Proof by enumeration We begin with a very simple proof method based on the de nition of logical entailment Consider the following trivial example Given Roses are red and violets are blue Prove Roses are red This is obviously correct because of the meaning of and A proposition P and Q which in mathemat ical notation is written P A Q is true just when P is true and Q is true Thus we can view A as an operator that constructs a complex proposition called a conjunction out of two simple ones This operator is de ned by the truth value of the complex proposition for all possible truth values of its constituents as shown in Table 1 To prove formally that roses are red P given that roses are red and violets are blue P A Q we rst identify all the possible cases where P A Q is true There is just one such case namely the fourth line of the table And indeed in that case roses are red P is also true This completes the proof Duh This seems rather daft but actually it illustrates very well the fundamental concept of formal proof by enumeration of possible cases We will see later in the course that the same basic idea can be instantiated in a program that performs feats of deduction well beyond the powers of human beings Proof by enumeration is tedious beyond belief so we ll look at only one more case Given lf Dewey isn t elected then I ll eat my hat Dewey isn t elected Prove I ll eat my hat The rst sentence here has the form of an implication ln mathematical notation this is written as P gt Q The truth table for gt is given in Table 1 Notice that the implication P gt Q is only false in the case where its antecedent P is true and its consequent Q is false The implication is true in those cases where the antecedent is false This is ne because in such cases the implication simply doesn t apply Proof First we identify all those cases where P gt Q and P are both true There is just one such case namely the fourth line of the table And indeed in that case I ll eat my hat Q is also true D Notice the D marking the end of a proof6 Some people like to read texts and papers just looking at the parts between the Proof and the D regarding the ordinary text as useless ller Other people do the exact opposite regarding the proof text as tedious detail You can usually guess which category a person belongs to 61H better days people wrote QED instead standing for for quad emt demonstrandumiLatin for which was the thing to be demonstrate CS 70 Spring 2004 Lecture 1 5 lNEERENCE RULE LUGlCALLY EQUlVALENT NEGATlUN CUNTRAPUSWVE CONVERSE Proof by application of inference rules Notice that once we have done a proof by enumeration we can extract a general pattern called an inference rule The two patterns in the preceding section are For any propositions P and Q the proposition P can be inferred from the proposition P A Q For any propositions P and Q the proposition Q can be inferred from the propositions P and P gt Q These can also be written using the following notation P A Q P P gt Q P Q The former rule is called andelimination The latter rule is called modus ponens Latin for placing method and is one of the most common steps used in proofs There are many more such rules some of which we will see in subsequent sections Rules can be chained together For example if we know A A B and B gt C we can apply andelimination to derive B and then modus ponens to derive C A full truthtable proof would require eight rows to handle the three propositions Proof by contrapositive Consider the propositions If John is at work he s logged in If John isn t logged in he s not at work Clearly each of these propositions can be proved from the other They are logically equivalent propositionsi that is their truth values are the same in all possible worlds Writing the rst as P gt Q and the second as Q gt P where we have used the negation symbol n it is easy to verify this equivalence using truth tables We will see many such equivalences in later lectures The proposition Q gt P is the contrapositive of P gt Q This is not to be confused with the converse which is Q gt P and is not equivalent Proof by contrapositive also called indirect proof means proving that P gt Q by proving Q gt P instead Since the two are equivalent proving one of them automatically establishes the other Here is a very simple example Theorem 11 For any integer n if n2 is even then n is even Proof We will prove the contrapositive if n is odd then n2 is odd 1 If n is odd then by de nition n 2a 1 for some integer a 2 For any numbers x and y we know thatxy gt x2 yz Hence n2 2a12 4a24a1 22a2 2a 1 3 Since a is an integer 2n2 2a is an integer 4 Hence by the de nition of oddness n2 is odd D CS 70 Spring 2004 Lecture 1 6 NOH proof Failure to note the justi cation for each step can lead easily to nonproofs Consider the following example Theorem 12 not 1 71 Proof 1 4 7171 fix71 712 71m Presumably at least one of these steps is false But each one presumably looked reasonable to the author of the proof Writing out the full justifying axioms for each step quickly reveals an axiom that is false it is simply untrue that for any numbers x and y JTy Other classic errors Dividing both sides of an equation by a variable For example axbx hence ab The axiom to which this step implicitly appeals is false because if x O the claim a b does not follow Some extra work may be needed to prove x 7 O Dividing both sides of an inequality by a variable This is even worse For example axltbx hence alt b Here the claim a lt b is false if x lt O and unproven if x 0 Proof by cases Sometimes we don t know which of a set of possible cases is true but we know that at least one of the cases is true If we can prove our result in each of the cases then we have a proof The English phrase damned if you do and damned if you don t sums up this proof method Here s a nice example Theorem 13 For some irrational numbers x and y xy is rational Proof 1 Since the theorem is existentially quanti ed we need only prove the existence of at least one example Consider the case x and y It must be true that a is rational or b is irrational 2 In case a we have shown irrational numbers x and y such that xy is rational 3 In case b consider the values x and y We have xy MW z 2 by the axiom xy z 6 Hence we have shown irrational numbers x and y such that xy is rational CS 70 Spring 2004 Lecture 1 7 NUNCUNSTRUCT VE RATlUNAL NUMBER REDUCED FORM 4 Since one of cases a and b must be true it follows that for some irrational numbers x and y xy is rational D Notice that even after the proof we still don t know which of the two cases is true so we can t actually exhibit any irrational numbers satisfying the theorem This is an example of a nonconstructive proof one in which an existential theorem is proved without constructing an example Proof by contradiction Also called reduCtio ad absurdum reduction to an absurd thing proof by contradiction is closely related to proof by contrapositive The idea is to assume the opposite of what one is trying to prove and then show that when combined with the axioms this leads to a contradiction Consider the following example A rational number is a number that can be expressed as the ratio of two integers For example 23 35 and 916 are all rationals The reduced form of a rational is a fraction in which the numerator and denominator share no factors other than 1 For example the reduced form of 36 is 1 2 Note that any number with a nite or recurring decimal representation is a rational Theorem 14 is irrational Proof Assume is rational N By the de nition of rational numbers there are integers a and b with no common factor other than 1 such that ab 9 For any numbers x and y we know thatxy gt x2 yz Hence 2 aZbz 5 Multiplying both sides by b2 we have a2 2b2 2 E b is an integer hence b2 is an integer hence a is even by the de nition of evenness 0 Hence by the theorem proved earlier a is even gt1 Hence by the de nition of evenness there is an integer C such that a 2C 00 Hence 2b2 4C2 hence b2 2C2 2 9 Since C is an integer C is an integer hence b2 is even 0 Hence by the theorem proved earlier b is even Hence a and b have a common factor 2 contradicting step 1 H N Hence step 1 is false ie is irrational CS 70 Spring 2004 Lecture 1 8 mEam QEQQ What is 2 2 k0 Leta 1 andr 12 2n1 1 iz k What If k starts at 1 k0 2 iZ k iZ k 20 k1 k0 2n1 1 2n 2n1 1 2n 2quot i 22quot 1 2quot 2quot 2quot 1 2n 1 Two more Closed form solutions n 2n1 1 2quot 2n i 2k 2 1 Solve 239Hco mixquot n l n n i 2 60261 2 T rq xzv y z cwzw221 2 bcx2 1 2 U 2W qCKZHU l 2M 2MqM U 200 Find 1 200 200 99 2quot 1 200201 99100 2 2 20100 49500 2 15150 n 2 Derive the closed form for Elf First we note that k3 kl3 3k23kl then we sum both sides of the equation from 1 to n ve k 13 018 3k1 On the left hand side we have a telescoping sum so it is equal to H3 n3 i3k2 i3k 1 k1 k1 k1 3ik2 3ikn k1 k1 n Rearranging the terms we get 1 One To One We say a function f A gt B is onetoone or infective if f always maps different elements of A to different elements of B Formally f A gt B is injective if and only if Vay E A 3f y gt f2t fy Intuitively this means that if we give f different inputs we get different outputs Consider these examples a f States gt Cities defined by f2t 2 capital of 3 Because each U S city is the capital of at most one state f is one toone i e maps exactly one city to each state f R gt R defined by f7t v 1 is also one toone f Cities gt States defined by at location of a is not one to one because f Atlanta fMacon Georgia f lR gt R defined by f7t 2 is not one to one because f 1 f1 1 If we were to draw lines to connect elements of A and B each element of A would be connected to exactly one element of B this is the definition of function and each element of B would be connected to at most one element of A Note that it is acceptable for some elements of B to not be connected to any elements of A Refer to figures 3 4 and 5 on pages 59 61 of the textbook l a Proving f is Injective To prove that f A gt B is injective we must prove that for every pair 3y E A if a 95 y then at y The general method of proving statements with universal quantifiers i e VaPz is to prove Pz true for an arbitrary a Universal generalization then allows us to conclude that Pz is true for all 3 Specifically to prove that f is injective we will prove that for arbitrary elements 3y E A if at 1 then at y When dealing with specific functions i e functions with a definition such as at 32 as opposed to a general function f A gt B it is often difficult to apply rules of inference to the statement a 915 y However recall that an implication and its contrapositive are logically equivalent This means that in the case of injective functions tthe following propositions have the same truth value 3 3 gt at y we m gt of y N NJ gt at 3 Therefore instead of proving that if 1 y then f7 ye y we may instead prove that if f7 2 y then y 1Note that c and y are arbitrary elements of A not any elements of A We do not assign c and y speci c values to the contrary the only information we assume about c and y is that they are elements of A l a i Proof Outline In summary to prove f A gt B is injective 1 Let at and y be arbitrary and not necessarily unique elements of A 2 2 Prove that either a if at 915 y then at 915 y or u if at y then at y 3 State that because the proposition in step 2 is true for arbitrary at and y it is true for all at and y 4 Conclude that f is injective l a ii Example Proof We will prove that f 1R1L gt IR1L de ned by at at2 is one to one Let at and y be arbitrary elements of IR1L We will use the contrapositive to show that if at 915 y then at 915 y In other words we will prove that if at y then at y Assume that at 2 y The de nition of f tells us that at2 y2 This is equivalent to saying at2 y2 0 We can factor at2 y2 into at yat y and that at yat y 0 We know that the product of two real numbers ab is zero only if at least one of a or b is zero Therefore either at y 0 or at y 0 This means that either at y or at y Because at and y are both positive by de nition8 the second case is impossible Therefore we know that at y as desired We have thus shown that for arbitrary values of at and y if at 915 y then at y We may therefore conclude that for any pair aty E A if at y then at y Hence f is one to one by de nition I 2 Onto We say a function f A gt B is onto or surjective if every element in B corresponds to some element in A Formally f A gt B is surjective if and only if Vb E BEla E A a b In other words there are no leftovers in the codomain Again refer to gures 3 4 and 5 on pages 5961 of the textbook Consider the following examples a f Cities gt States defined by at 2 location of at is surjective because every state contains at least one city Notice that each state corresponds to may cities This is acceptable f IR gt IR defined by at at 1 is surjective For every y 6 R we can nd an at E R namely at y 1 such that at y In our case at y 1y 1 1 2 y 2Be sure A is not empty 3This means that we de ned a and y to be elements of the positive real numbers f States gt Cities de ned by f2t capital of a is not surjective because there are many cities that are not the capital city of any state For example Detroit f IR gt IR de ned by f2t NJ is not surjective because there is no real number such that 23 Proving f is Surjective To prove that f A gt B is surjective we must demonstrate that for every b E B there exists an a E A such that fa b When dealing a speci c function we can often do this by constructing an 1 based on an arbitrary b In other words given b we nd a formula for 1 However because b is an arbitrary element nding this formula is not always easy A good way to obtain extra information about b is to use c 2 a i Proof Outline In summary to prove f A gt B is surjective 1 Let b be an arbitrary element of B 2 Prove that there exists an a E A such that fa b There are two possible approaches Construct 1 based on b In other words nd a formula for 1 based on b Simply show that some a must exist This is more difficult but is sometimes necessary 3 State that because there exists an a for an arbitrary b then there exists an a for every b 4 Conclude f is surjective 2 a ii Example Proof We will prove that f IR gt IR de ned by at 2 31 7 is surjective Let y be an arbitrary real number Consider a 1 Because the real numbers are closed under addition and multiplicationquot we know that a is in the domain i e a 6 IR Furthermore 19911 3Lg77y Thus we can that for any y we can nd an a such that f7t y Hence f is surjective by de nition I 4In this case multiplication by 3 Bijective and Inverse De nition f A gt B and g B gt A are inverses if and only if Va 6 A gfa a and Vb E b fgb b Intuitively g is an inverse of f if g reverses the change made by f De nition f A gt B is bijective if and only if it is injective and surjective Most proofs that f is bijective will contain two separate parts A proof that f is injective and a proof that f is bijective 3 3 Proof using Bijective and Inverse Theorem f A gt B has an inverse if and only if f is bijective 3 a i Outline This proof has several parts We begin with an outline 1 If f has an inverse then f is bijective a If f has an inverse then f is injective b If f has an inverse then f is surjective 2 If f is bijective then f has an inverse First to prove a statement of the form a if and only if b we must prove both if a then b and if b then a This gives us steps 1 and 2 Next to show that f is bijective we must show that f is injective and that f is surjective Thus we break step 1 into steps 1a and 1b We now sketch a proof of each step a la We will do this by contradiction We will assume f has an inverse g and assume to the contrary that f is not injective Then we will demonstrate why it is impossible for f to not be injective 1b We will prove this directly We will assume that f has an inverse 9 Then we will choose an arbitrary element b E B and construct an a E A such that a b 2 We will prove this directly We will assume that f is bijective We will then construct a function g B gt A and prove that 7 g is a valid function from B to A 7 g is an inverse of f