Proof by Cases • To prove a conditional statement of the form: ○ \p_1∨p_2∨…∨p_n)→q • Use the tautology ○ \p_1∨p_2∨…∨p_n)→q ↕ ○ (p_2→q)∧(p_2→q)∧…∧(p_n→q) • Each of the implications p_i→q is a case. • Example ○ Let a@b=max{a, b}=a if a≥b, ○ otherwise a@b=max{a, b}=b. ○ Show that for all real numbers a, b, c § (a@b)@c=a@(b@c) ○ (This means the operation @ is associative.) ○ Let a, b, and c be arbitrary real numbers. ○ Then one of the following 6 cases must hold. § a≥b≥c § a≥c≥b § b≥a≥c § b≥c≥a § c≥a≥b § c≥b≥a Without Loss of Generality • Show that if x and y are integers and both x∙y and x+y are even, • then both x and y are even. • Use a proof by contraposition. • Suppose x and y are not both even. • Then, one or both are odd. • Without loss of generality, assume that x is odd. • Then x=2m+1 for some integer m. • Case 1: y is even. ○ Then y=2n for some integer n, so ○ x+y=(2m+1)+2n=2(m+n)+1 is odd. • Case 2: y is odd. ○ Then y=2n+1 for some integer n, so ○ x∙y=(2m+1)(2n+1)=2(2m∙n+m+n)+1 is odd. • We only cover the case where x is odd • because the case where y is odd is similar. • The use phrase without loss of generality (WLOG) indicates this. Existence Proofs • Proof of theorems of the for ∃x P(x). • Constructive existence proof: ○ Find an explicit value of c, for which P(c) is true. ○ Then ∃x P(x) is true by Existential Generalization (EG). • Example: ○ Show that there is a positive integer that can be written as ○ the sum of cubes of positive integers in two different ways: ○ 1729=〖10〗3+93=〖12〗3+13 • Nonconstructive existence proof ○ In a nonconstructive existence proof, ○ we assume no c exists which makes P(c) true ○ and derive a contradiction. • Example ○ Show that there exist irrational numbers x,y such that x^y is rational. ○ We know that √2 is irrational. ○ Consider the number 〖√2〗^√2. ○ If 〖√2〗^√2 is rational § we have two irrational numbers x and y with x^y rational § namely x=√2 and y=√2. ○ If 〖√2〗^√2 is irrational § then we can let x=〖√2〗^√2 and y=√2 so that § x^y= (〖√2〗^√2 )√2=〖√2〗(√2×√2)=〖√2〗^2=2. Uniqueness Proofs • Some theorems asset the existence of • a unique element with a particular property, ∃!x P(x). • The two parts of a uniqueness proof are ○ Existence § We show that an element x with the property exists. ○ Uniqueness § We show that if y≠x, then y does not have the property. • Example ○ Show that if a and b are real numbers and a≠0, then ○ there is a unique real number r such that ar+b=0. ○ Existence § The real number r =−b/a is a solution of ar+b=0 § because a(−b/a)+b=−b+b=0. ○ Uniqueness § Suppose that s is a real number such that as+b=0. § Then ar+b=as+b, where r=−b/a. § Subtracting b from both sides § and dividing by a shows that r = s. Additional Proof Methods • Later we will see many other proof methods: • Mathematical induction ○ which is a useful method for proving statements of the form ∀n P(n), ○ where the domain consists of all positive integers. • Structural induction ○ which can be used to prove such results about recursively defined sets. • Cantor diagonalization ○ used to prove results about the size of infinite sets. • Combinatorial proofs use counting arguments.
