CSC 28 - Discrete Structures - Proof ------------------------------------ ** These notes are not intended as a replacement to lecture. There sole purpose ** is to remind me what I want to say, and remind you what I thought was ** important A theorem is a statement we intend to prove true. Theorem: If x and y are even integers, then xy is an even integer. Most theorems are of the form: If X, then Y. Sometimes it is hard to see. Theorem: Suppose x and y are even integers. The product xy is even. Theorem: The product xy is even when x and y are both even. Whenever possible, think of the theorem as: if X then Y. -- Proving: A implies B. A implies B is true except when A is true and B is false. Show A implies B true by showing that whenever A is true, so is B. - Assume A is true. - Argue that B is true. This shows B is true whenever A is true. Ex: - Suppose x and y are even integers. - This means x=2k and y=2j for some integers k and j. - The product xy = 4kj = 2(2kj). - By definition, xy is even. Notes: - Begin your proof with what you assume to be true (the hypothesis of your implication). - Don't argue the truth of a theorem by example. Stay abstract. You know x and y are even integers, but that's all you know about them. - Your proof must work forward from your assumptions to your goal. You may work backward on scratch paper to help you figure out how to work forward. - Write your proof in prose. When read out loud, it should sound like a well-written paragraph. - Quite often you'll use definitions to make progress. Definitions: x is even iff x=2k for some integer k. x is odd iff x=2k+1 for some integer k. x is prime iff x >= 2 and x=jk for some integers 1 < j,k < x. x|y (x divides y) iff y=xk for some integer k. x \in Q iff x=y/z for some integers y and z, and z!=0. X is a subset of Y iff a in X implies a in Y. X=Y iff X is a subset of Y and Y is a subset of X Examples: Theorem: Suppose x and y are integers. If x is even and y is odd, then xy is even. Proof: Suppose x is an even integer and y is an odd integer. Then x=2k and y=2j+1 for some integers k and j. Multiplying, we get xy=4kj+2k=2(2kj+k), which is even. [Theorem: If x|y and y|z, then x|z.] Theorem: Let A and B be sets. Then, A intersect B is a subset of A union B. Turn into implication: If x in A intersect B, then x in A union B. - Suppose A and B are sets and x is in A intersect B. - By definition, x in A and x in B. <= Logical form of intersection. - Logically, x in A or x in B is also true. - By definition, x in A union B. <= Logical form of intersection. ** Counterexample To show A --> B is a false statement - Find an example situation that makes A true and B false. - Show it makes A true. - Show it makes B false. Theorem: If x is prime, then x is odd. Counterexample: Consider 2. It is prime since is has no positive divisors other than 1 and 2 and is not less than 2. But, it is also not odd since 2=2(1) which makes it even. ** Contrapositive: A --> B == not B --> not A. To prove A --> B by contraposition: - Suppose B is false. - Show A is false. Theorem: Suppose a, b, and c are integers. If not(a|bc), then not(a|b) or not(a|c). [Note: it's often harder to prove things are not true than to show they are] Proof: We prove the contrapositive. Suppose a, b and c are integers and a|b and a|c. ... show a|bc as before ... [Theorem: Suppose a, b and c are real numbers and a > b. If ac <= bc then c <= 0.] ** Contradiction: To show A is true, it suffices to show it is not false. - Assume A is false. - Show that something impossible results. - Therefore, A can't be false. When what you want to prove is an implication A --> B: - Suppose A and not B (which is equivalent to not(A --> B)). - Show that something impossible results. - Therefore, A --> B. Ex: Theorem: Suppose A \intersection C \subset B and a \in C. Then a \notin A\B. Ex: Theorem: If x^2 + y = 13 and y != 4 then x != 3. ** Steps to proof of theorem On scratch: - Express theorem as A --> B - Compare alternatives, attempt most promising Direct: Assume A. Show B. Contrapositive: Assume not B. Show not A. Contradiction: Assume A and not B. Show an impossibility. - Figure out steps from assumption to conclusion Write proof: - Write in prose. - Work from assumptions to conclusion. CSC 28 - Discrete Structures - Proof by Induction ------------------------------------------------- ** These notes are not intended as a replacement to lecture. There sole purpose ** is to remind me what I want to say, and remind you what I thought was ** important All postage values of at least 8 can be made from 3 and 5 cent stamps. Prove using two steps: - Show 8 cents of postage can. - Show that if x >= 8 and x can be made of 3 and 5 cent stamps, then so can x+1. - If I have any handful of stamps adding to x, then I can - Remove a 5 and replace it with two 3s, or if no 5s - Remove three 3s and replace with two 10s. - In either case, I now have x+1 cents of postage. This argument proves my claim because (i) I know that it's possible to get some smallest number of postage out of 3s and 5s (called the base case), and (ii) I can apply my rule as many times as necessary to get to any amount of postage >= my base case amount. Theorem: Suppose P(x) is a predicate on integers, a is an integer, P(a) is true and so is \forall x >= a, P(x) --> P(x+1). Then, \forall y >= a P(y) is true. Given Goal ----- ---- a \in Z \forall y >= a P(y) P(a) \forall x >= a, P(x) --> P(x+1) Given Goal ----- ---- a \in Z P(y) P(a) \forall x >= a, P(x) --> P(x+1) y is arbitrary and >= a Given Goal ----- ---- a \in Z P(y) P(a) \forall x >= a, P(x) --> P(x+1) y is arbitrary and >= a P(a) --> P(a+1) P(a+1) --> P(a+2) ... P(y-1) --> P(y) Proof: Suppose y >= a is arbitrary. Then because \forall x >= a, P(x) --> P(x+1), we know P(a) --> P(a+1) and P(a+1) --> P(a+2) and ... and P(y-1) --> P(y). But, since P(a) is true, a series of modus ponens arguments tells us P(y) is true. Therefore, \forall y >= a P(y) is true. This means that if we ever want to Prove \forall y >= a P(y) all we need to do is satisfy the hypothesis P(x) is a predicate on integers, a is an integer, P(a) is true and so is \forall x >= a, P(x) --> P(x+1). Recipe: ------ - Determine P and a. - Prove subtheorem: P(a) true. - Prove subtheorem: Suppose x is an integer, x >= a and P(x) is true. Then, P(x+1) is true. Examples: -------- Theorem. 1 + 2 + ... + n = (n)(n+1)/2 for every n >= 1. Scratch: Let P(x) mean "1+2+...+x = x(x+1)/2" Let a = 1 (the smallest number we want to prove something about) Proof (by induction): As a base case, let n=1. Then 1+2+...+n = 1 and (n)(n+1)/2 = (1)(2)/(2) = 1. For the inductive case, suppose k >= 1 and 1 + 2 + ... + k = (k)(k+1)/2. Adding k+1 to both sides, we see .... ------ Theorem. 2^0 + 2^1 + ... + 2^n = 2^(n+1) - 1, for every integer n >= 0. ------ Induction is not only useful for mathematical sums. Theorem: The sum of the interior angles of a convex polygon with n >= 3 corners is (n-2)180 degrees. Base case: The sum of the interior angles of a convex polygon with 3 corners is 180 degrees. Inductive step: Assumption: Suppose k >= 3 and the sum of the interior angles of a convex polygon with k >= 3 corners is (k-2)180 degrees. Goal: The sum of the interior angles of a convex polygon with k+1 corners is (k-1)180 degrees. Proof sketch: Base case: Well known that triangle angles sum to 180. Inductive step: Say we have a convex polygon with k+1 corners c0, c1, ..., ck. Draw a line from c0 to c2 and remove triangle (c0,c1,c2). The result is a convex polygon with k corners. Inductive assumption says its angles sum to (k-2)180 degrees. Replacing (c0,c1,c2) adds 180 degrees to this sum, giving a total of (k-1)180. ------ Strong induction ---------------- - Determine P and a. - Prove subtheorem: P(a) true. - Prove subtheorem: Suppose x is an integer, x >= a and P(a) ... P(x) are true. Then, P(x+1) is true. Theorem: Every integer greater than 1 can be written as a product of primes.