CSE115/ENGR160 Discrete Mathematics 02/08/11Without loss of generality (WLOG)ExampleSlide 4Common mistakes in exhaustive proof and proof by casesSlide 6Slide 7Slide 8Existence proofConstructive existence proofNon-constructive existence proofUniqueness proofSlide 13Proof strategyForward/backward reasoningSlide 16Slide 17Slide 18Slide 19Slide 20Adapting existing proofSlide 22Looking for counterexamplesSlide 24Slide 25Proof strategy in actionCSE115/ENGR160 Discrete Mathematics02/08/11Ming-Hsuan YangUC Merced1Without loss of generality (WLOG)•In proof, sometimes we can apply the same argument for different cases–x≥0, y<0: xy<0 |xy|=-xy=x(-y)=|x||y|–x<0, y ≥0:xy<0 |xy|=-xy=(-x)y=|x||y|•By proving one case of a theorem, no additional argument is required to prove other specified cases2Example•Show that (x+y)r < xr+yr when x and y are positive numbers and r is a real number with 0 < r < 1•Without loss of generality, assume x+y=1•The reason we can do this is because if x+y=t, then x/t+y/t=1. To prove this theorem, it is equivalent to ((x/t)+(y/t))r<(x/t)r+(y/t)r. Multiplying both sides by tr, we have (x+y)r < xr+yr 3Example•Because x+y=1 and x, y are positive real numbers, we have 0<x<1, and 0<y<1•Because 0<r<1, 0<1-r<1, so x1-r<1 and y1-r<1, which means x<xr and y<yr•Consequently, xr+yr>x+y=1, and (x+y)r =1r<xr+yr and we prove the theorem for x+y=1•As we assume x+y=1 without loss of generality in this proof, we know that (x+y)r<xr+yr is true whenever x, y are positive real numbers and r is a real number with 0<r<14Common mistakes in exhaustive proof and proof by cases•Draw incorrect conclusions from insufficient number of examples•Need to cover every possible case in order to prove a theorem•Proving a theorem is analogous to showing a program always produces the desired output •No matter how many input values are tested, unless all input values are tested, we cannot conclude that the program always produces correct output5Example•Is it true that every positive integer is the sum of 18 4th powers of integers?•The 4th powers of integers: 0, 1, 16, 81, … •Select 18 terms from these numbers and add up to n, then n is the sum of 18 4th powers•Can show that integers up to 78 can be written as the sum as such•However, if we decided this is enough (or stop earlier), then we come to wrong conclusion as 79 cannot be written this way6Example•What is wrong with this “proof” “Theorem”: If x is a real number, then x2 is a positive real number “Proof”: Let p1 be “x is positive” and p2 be “x is negative”, and q be “x2 is positive”. First show p1→q, and then p2→q. As we cover all possible cases of x, we complete this proof7Example•We missed the case x=0•When x=0, the supposed theorem is false•If p is “x is a real number”, then we need to prove results with p1, p2, p3 (where p3 is the case that x=0)8))()()(())((321321qpqpqpqppp Existence proof•A proof of a proposition of the form•Constructive proof: find one element a such that p(a) is true•Non-constructive proof: prove that is true in some other way, usually using proof by contradiction 9)(xxp)(xxpConstructive existence proof•Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways•By intuition or computation, we find that 1729=103+93=123+13•We prove this theorem as we show one positive integer can be written as the sum of cubes in two different ways10Non-constructive existence proof•Show that there exist irrational numbers x and y such that xy is rational•We previously show that is irrational•Consider the number . If it is rational, we have two irrational number x and y with xy is rational (x= , y= )•On the other hand if is not rational, then we let•We have not found irrational numbers x and y such that xy is rational•Rather we show that either the pair x= , y= or the pair have the desired property, but we do not know which of these two pairs works! 1122222222)2( thusand ,2,2222222yxyx22222,22 yxUniqueness proof•Some theorems assert the existence of a unique element with a particular property•Need to show–Existence: show that an element x with the desired property exists–Uniqueness: show that if y≠x, then y does not have the desired property•Equivalently, show that if x and y both have the desired property, then x=y•Showing that there is a unique element x such that p(x) is the same as proving the statement 12)))()(()(( ypxyyxpx Example•Show that if a and b are real numbers and a≠0, then there is a unique number r such that ar+b=0•Note that the real number r=-b/a is a solution of ar+b=0. Consequently a real number r exists for which ar+b=0•Second, suppose that s is a real number such that as+b=0. Then ar+b=as+b. Since a≠0, s must be equal to r. This means if s≠r, as+b≠013Proof strategy•Can be challenging•First analyze what the hypotheses and conclusion mean•For conditional statements, usually start with direct proof, then indirect proof, and then proof by contradiction14Forward/backward reasoning•Direct proof: –start with premises, together with axioms and known theorems, –we can construct a proof using a sequence of steps that lead to conclusion•A type of forward reasoning•Backward reasoning: to prove q, we find a stement p that we can prove that p→q15Example•For two distinct positive real numbers x, y, their arithmetic mean is (x+y)/2, and their geometric mean is . Show that the arithmetic mean is always larger than geometric mean •To show , we can work backward by finding equivalent statements 16xyxyyx  2/)(0)(424/)(2/)(2222yxxyyxyxxyyxxyyxExample•For two distinct real positive real numbers, x and y, (x-y)2>0•Thus, x2-2xy+y2>0, x2+2xy+y2>4xy, (x+y)2>4xy. So, •We conclude that if x and y are distinct positive real numbers, then their arithmetic mean is greater than their geometric mean17xyyx  2/)(Example•Suppose that two people play a game taking turns removing 1, 2, or 3 stones at a time from a pile that beings with 15 stones. The person who removes the last stone wins the game.•Show that the first player can win the game no matter what the second play does18Example•At the last step, the 1st player