CSL 101 Discrrete mathematics-l3-l4.pdf

CSL 101 DISCRRETE MATHEMATICS LECTURE 3-4 Dr. Barun Gorain Department of CSE, IIT Bhilai Email: [email protected]  2 SOME MORE FACT ON COUNTABILIT...

CSL 101 DISCRRETE MATHEMATICS LECTURE 3-4 Dr. Barun Gorain Department of CSE, IIT Bhilai Email: [email protected]  2 SOME MORE FACT ON COUNTABILITY Theorem 2: Let A be a countably infinite set, and B an infinite subset of A. Then B is countable. Proof let f : N → A be a bijection witnessing that A is countable. We want to construct a bijection g : N → B. Let k1 = min f{k ε N : f(k) ε B}. That is, k1 is the smallest number that gets mapped into B by f. Define g(1) := f(k1). We proceed inductively from here. Assume we have defined g(1), g(2) ……, g(n). Let kn+1 = min { k ε N : f(k) ε B \ {g(1); : : : ; g(n)}} Prove that g:N→ B is a bijection  3 UNCOUNTABLE SETS The closed interval [0,1] is uncountable Proof: Suppose that there exists a bijection from r:N→[0,1] Then we will be able to list down all the real numbers in [0,1] as follows di= 1 if dii ≠1 =2 if dii =0 Note that r is not same as any of ri in the above list.  4 BASIC PROOF TECHNIQUES  This Lecture We are going to apply the logical rules in proving mathematical theorems. Direct proof Contrapositive Proof by contradiction Proof by cases  Basic Definitions An integer n is an even number if there exists an integer k such that n = 2k. An integer n is an odd number if there exists an integer k such that n = 2k+1.  Direct Proofs Goal: If P, then Q. (P implies Q) Method 1: Write assume P, then show that Q logically follows. Claim: If , then Reasoning: When x=0, it is true. When x grows, 4x grows faster than x3 in that range. Proof: When  Direct Proofs The sum of two even numbers is even. Proof x = 2m, y = 2n x+y = 2m+2n = 2(m+n) The product of two odd numbers is odd. Proof x = 2m+1, y = 2n+1 xy = (2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn+m+n) + 1.  This Lecture Direct proof Contrapositive Proof by contradiction Proof by cases  Proving an Implication Goal: If P, then Q. (P implies Q) Method 2: Prove the contrapositive, i.e. prove “not Q implies not P”. Claim: If r is irrational, then √r is irrational. Proof: We shall prove the contrapositive – “if √r is rational, then r is rational.” Since √r is rational, √r = a/b for some integers a,b. So r = a2/b2. Since a,b are integers, a2,b2 are integers. Therefore, r is rational. Q.E.D. (Q.E.D.) "which was to be demonstrated", or “quite easily done”. ☺  Proving an “if and only if” Goal: Prove that two statements P and Q are “logically equivalent”, that is, one holds if and only if the other holds. Example: An integer is even if and only if the its square is even. Method 1: Prove P implies Q and Q implies P. Method 1’: Prove P implies Q and not P implies not Q. Method 2: Construct a chain of if and only if statement.  Proof the Contrapositive An integer is even if and only if its square is even. Method 1: Prove P implies Q and Q implies P. Statement: If m is even, then m2 is even Proof: m = 2k m2 = 4k2 Statement: If m2 is even, then m is even Proof: m2 = 2k m = √(2k) ??  Proof the Contrapositive An integer is even if and only if its square is even. Method 1’: Prove P implies Q and not P implies not Q. Statement: If m2 is even, then m is even Contrapositive: If m is odd, then m2 is odd. Proof (the contrapositive): Since m is an odd number, m = 2k+1 for some integer k. So m2 = (2k+1)2 = (2k)2 + 2(2k) + 1 So m2 is an odd number.  This Lecture Direct proof Contrapositive Proof by contradiction Proof by cases  Proof by Contradiction Theorem: 2is irrational. Proof (by contradiction): Suppose 2was rational. Choose m, n integers without common prime factors (always possible) such that m 2= n Show that m and n are both even, thus having a common factor 2, a contradiction!  Proof by Contradiction Theorem: 2is irrational. Proof (by contradiction): Want to prove both m and n are even. 2= m so can assume m = 2l n m2 = 4l 2 2n = m 2n 2 = 4l 2 2n 2 = m 2 n 2 = 2l 2 so m is even. so n is even.  Infinitude of the Primes Theorem. There are infinitely many prime numbers. Proof (by contradiction): Assume there are only finitely many primes. Let p1, p2, …, pN be all the primes. We will construct a number N so that N is not divisible by any pi. By our assumption, it means that N is not divisible by any prime number. On the other hand, we show that any number must be divisible by some prime. It leads to a contradiction, and therefore the assumption must be false. So there must be infinitely many primes.  Infinitude of the Primes Theorem. There are infinitely many prime numbers. Proof (by contradiction): Let p1, p2, …, pN be all the primes. Consider p1p2…pN + 1. Claim: if p divides a, then p does not divide a+1. Proof (by contradiction): a = cp for some integer c a+1 = dp for some integer d => 1 = (d-c)p, contradiction because p>=2. So none of p1, p2, …, pN can divide p1p2…pN + 1, a contradiction.  This Lecture Direct proof Contrapositive Proof by contradiction Proof by cases  The Square of an Odd Integer Idea 0: find counterexample. 32 = 9 = 8+1, 52 = 25 = 3x8+1 …… 1312 = 17161 = 2145x8 + 1, ……… Idea 1: prove that n2 – 1 is divisible by 8. n2 – 1 = (n-1)(n+1) = ??… Idea 2: consider (2k+1)2 (2k+1)2 = 4k2+4k+1 If k is even, then both k2 and k are even, and so we are done. If k is odd, then both k2 and k are odd, and so k2+k even, also done.  This Lecture Last time we have discussed different proof techniques. This time we will focus on probably the most important one – mathematical induction. This lecture’s plan is to go through the following: The idea of mathematical induction Basic induction proofs (e.g. equality, inequality, property,etc) An interesting example  Odd Powers Are Odd Fact: If m is odd and n is odd, then nm is odd. Proposition: for an odd number m, mk is odd for all non-negative integer k. Let P(i) be the proposition that mi is odd. Idea of induction. P(1) is true by definition. P(2) is true by P(1) and the fact. P(3) is true by P(2) and the fact. P(i+1) is true by P(i) and the fact. So P(i) is true for all i.  Divisibility by a Prime Theorem. Any integer n > 1 is divisible by a prime number. Let n be an integer. If n is a prime number, then we are done. Otherwise, n = ab, both are smaller than n. If a or b is a prime number, then we are done. Otherwise, a = cd, both are smaller than a. If c or d is a prime number, then we are done. Otherwise, repeat this argument, since the numbers are getting smaller and smaller, this will eventually stop and we have found a prime factor of n. Idea of induction.  Idea of Induction Objective: Prove This is to prove The idea of induction is to first prove P(0) unconditionally, then use P(0) to prove P(1) then use P(1) to prove P(2) and repeat this to infinity…  The Induction Rule 0 and (from n to n +1), Much easier to prove with P(n) as proves 0, 1, 2, 3,…. an assumption. Very easy to prove P (0), P (n) P (n+1) mN. P (m) For any n>=0 Like domino effect…  This Lecture The idea of mathematical induction Basic induction proofs (e.g. equality, inequality, property,etc) An interesting example A paradox  Proof by Induction Let’s prove: r  1. Statements in green form a template for inductive proofs. Proof: (by induction on n) The induction hypothesis, P(n), is: r  1.  Proof by Induction Induction Step: Assume P(n) for some n  0 and prove P(n + 1): r ( n+1)+1 − 1 r  1. 1 + r + r 2 + + r n+1 = r −1 Have P (n) by assumption: So let r be any number 1, then from P (n) we have n +1 r −1 1+ r + r + 2 +r = n r −1 How do we proceed?  Proof by Induction adding r n+1 to both sides, r n +1 − 1 n +1 1+ + r n + r n+1 = +r r −1 r n +1 − 1 + r n +1 (r − 1) = r −1 r ( n+1) +1 − 1 = r −1 But since r 1 was arbitrary, we conclude (by UG), that r ( n+1)+1 − 1 r  1. 1 + r + r 2 + + r n+1 = r −1 which is P (n+1). This completes the induction proof.  Proving an Equality Let P(n) be the induction hypothesis that the statement is true for n. Base case: P(1) is true Induction step: assume P(n) is true, prove P(n+1) is true. by induction  Proving a Property Base Case (n = 1): Induction Step: Assume P(i) for some i  1 and prove P(i + 1): Assume is divisible by 3, prove Is divisible by 3. Divisible by 3 Divisible by 3 by induction  Proving a Property Base Case (n = 2): Induction Step: Assume P(i) for some i  2 and prove P(i + 1): Assume is divisible by 6 Prove is divisible by 6. Divisible by 6 Divisible by 2 by induction by case analysis  Proving an Inequality Base Case (n = 3): Induction Step: Assume P(i) for some i  3 and prove P(i + 1): Assume , prove by induction since i >= 3  Proving an Inequality Base Case (n = 2): is true Induction Step: Assume P(i) for some i  2 and prove P(i + 1): by induction  This Lecture The idea of mathematical induction Basic induction proofs (e.g. equality, inequality, property,etc) An interesting example A paradox  Puzzle Goal: tile the squares, except one in the middle for Bill. n 2 n 2  Puzzle There are only L-shaped tiles covering three squares: For example, for 8 x 8 puzzle might tile for Bill this way:  Puzzle Theorem: For any 2n x 2n puzzle, there is a tiling with Bill in the middle. Did you remember that we proved is divisble by 3? Proof: (by induction on n) P(n) ::= can tile 2n x 2n with Bill in middle. Base case: (n=0) (no tiles needed)  Puzzle Induction step: assume can tile 2n x 2n, prove can handle 2n+1 x 2n+1. n 2 Now 2 n+1 what??  Puzzle The new idea: A stronger property Prove that we can always find a tiling with Bill anywhere. Theorem B: For any 2n x 2n puzzle, there is a tiling with Bill anywhere. Clearly Theorem B implies Theorem. Theorem: For any 2n x 2n puzzle, there is a tiling with Bill in the middle.  Puzzle Theorem B: For any 2n x 2n puzzle, there is a tiling with Bill anywhere. Proof: (by induction on n) P(n) ::= can tile 2n x 2n with Bill anywhere. Base case: (n=0) (no tiles needed)  Puzzle Induction step: Assume we can get Bill anywhere in 2n x 2n. Prove we can get Bill anywhere in 2n+1 x 2n+1.  Puzzle Induction step: Assume we can get Bill anywhere in 2n x 2n. Prove we can get Bill anywhere in 2n+1 x 2n+1. n 2 n 2  Puzzle Method: Now group the squares together, and fill the center with a tile. Done!