1 CmSc 175 Discrete Mathematics Lesson 08: Proofs 1. Proving existential statements - Constructive proof Prove that  x P(x) i.e. There is some x for which P(x) is true. Choose a particular x and show that P(x) is true. Example1: Prove that there is a prime number less than 10 Proof: 2 is a prime number less than 10 Example 2: Prove the statement  x  y  z, such that x2 + y2 = z2 Proof: Let x = 3, y = 4, z = 5. 32 + 42 = 52 2. Proving universally quantified statements: Direct proof Prove that  x if P(x) then Q(x) The meaning of the statement is: All x that have the property P, have also the property Q. Proof: 1. We choose arbitrary some x with the property P 2. We show that Q(x) is true. 3. Because x is chosen arbitrary, it could be any x. So Q(x) is true for any x, i.e. for all x. Explanation of step 2: How do we show that some property is true? We use the definition of that property and its relation to P(x). Example of using definitions: Prove that 10 is an even number. Proof: By definition an even number can be written as 2 * n 10 can be written as 2 * 5 Hence 10 is an even number. Formally: If the number can be written as 2 * n then the number is even 10 can be written as 2 * n Therefore 10 is even.2 Example of direct proof: Prove that the sum of two even numbers is an even number.  x  y if even(x)  even (y) then even (x+y) Proof: Let x be 2 * m, y be 2 * n (by definition of even numbers) The sum would be: 2 * n + 2 * m = 2 * (m + n) By definition 2 * (m + n) is even. x and y were chosen arbitrary, hence for all x and y even numbers, the sum is even. Exercise: 1. Prove that the sum of an even and an odd number is odd 2. Prove that the sum of two odd numbers is even 3. Prove that the sum of any three consecutive integers is divisible by 3 3. Proving universally quantified statements: Contradiction and Contraposition 3.1. Contradiction We assume that the conclusion to be proved is false, and then we show that this contradicts at least one of the premises. Example: Prove that there is no largest integer. i.e. prove the statement: (~ y) such that (x y > x ) This is the negated existential statement, and we can rewrite it as follows: (1)  y  x such that y < x Suppose (1) is not true. Then its negation has to be true: (2)  y  x (y > x) i.e. there is an integer greater than any other integer. Let M be such integer. Consider N = M+1. N is an integer, and N is greater than M, which contradicts the assumption that M is the greatest integer.3 3.2. Contraposition (1)  x if P(x) then Q(x) (2)  x if ~Q(x) then ~P(x) (2) is the contrapositive of (1). They are equivalent statements. If we prove (2) then we have proved (1). (2) is proved by direct proof. Example: Prove that if a number has even square, then the number is even. (1)  x if even(x2) then even(x) contrapositive: (2)  x if ~ even(x) then ~even(x2) restated as: (2')  x if odd(x) then odd(x2) Proof of (2'): Let x = 2k+1 (by definition of odd numbers.) x2 = (2k+1)*(2k + 1) = 4k2 + 4k + 1 = 2*(2k2 + 2k) + 1 the last expression is odd by definition. 4. Disproof of universally quantified statement : Counterexample (1)  x if P(x) then Q(x) We want to prove that (1) is false. If it is false then its negation would be true. So, we want to prove that (2)  x P(x)  ~Q(x) is true. Since (2) is an existential statement, we can use the constructive proof by showing an element x that has the property P and does not have the property Q.4 Example: Prove that the statement "All prime numbers are odd" is false Proof: In order to prove that  x if prime(x) then odd(x) is false, we shall show that  x prime(x)  ~odd(x) is true. Let x = 2. 2 is a prime number by definition, and 2 is not