CS 30: Discrete MathematicsAmit%Chakrabarti%%Styles%of%Proof%A Direct ProofTheorem:%Function%d%:%Z%→%Z%given%by%d(x)%=%2x%is%injective.%Recall%deDinition:%%%f%:%A%→%B%is%injective%means%%%for%every%x,%y%∈%A,%if%x%≠%y%then%f(x)%≠%f(y)%%%i.e.,%∀x,%y%∈%A%(x%≠%y%⇒%f(x)%≠%f(y))%%%i.e.,%∀x,%y%∈%A%(f(x)%=%f(y)#⇒%x%=%y)%Proof: %Consider%arbitrary%x,%y%∈%Z.%%Suppose%d(x)%=%d(y).%%Then%2x%=%2y.%%Therefore%x%=%y.%%Thus,%d%is%injective. %QED.%Another Direct Proof, Using CasesTheorem:%(A–B)%∪%(B–A)%⊆%(A%∪#B)%–%(A%∩%B).%Proof: %Consider%arbitrary%x%∈%(A–B)%∪%(B–A).%%Then%either%x%∈%A–B%or%x%∈%B–A.%%Case%1:%x%∈%A–B.%%Then%x%∈%A,%so%x%∈#A%∪#B.%%%Also,%x%∉%B,%so%x%∉#A%∩%B.%%%Therefore,%x%∈#(A%∪#B)%–%(A%∩%B).%%Case%2:%x%∈%B–A.%%Then%x%∈%B,%so%x%∈#A%∪#B.%%%Also,%x%∉%A,%so%x%∉#A%∩%B.%%%Therefore,%x%∈#(A%∪#B)%–%(A%∩%B).%%Thus,%in%all%cases,%x%∈#(A%∪#B)%–%(A%∩%B). %QED.%A Proof by ContradictionTheorem:%Function%d%:%Z%→%Z%given%by%d(x)%=%2x%is%injective.%Recall%deDinition:%%%%f%:%A%→%B%is%injective%means%%%∀x,%y%∈%A%(f(x)%=%f(y)#⇒%x%=%y)%Proof: %Suppose,%to%the%contrary,%that%d%is%not%injective.%%Then%¬∀x,%y%∈%Z%(d(x)%=%d(y)#⇒%x%=%y).%%So,%∃%x,%y%∈%Z%(d(x)%=%d(y)#∧%x%≠%y).%%So,%∃%x,%y%∈%Z%(2x%=%2y#∧%x%≠%y).%%So,%∃%x,%y%∈%Z%(x%=%y#∧%x%≠%y).%%But%this%is%a%contradiction! %QED.%Proof by Contradiction: 2300-yr-old ClassicTheorem:%There%are%inDinitely%many%primes.%Proof:%Suppose,%to%the%contrary,%that%#%of%primes%is%Dinite.%Full%list%of%primes:%2,%3,%5,%…,%p.%Consider%the%integer%n%=%(2%×%3%×%5%×%…%×%p)%+%1.%Dividing%n%by%2%leaves%remainder%1,%so%2%is%not%a%factor%of%n.%Dividing%n%by%3%leaves%remainder%1,%so%3%is%not%a%factor%of%n.%…%…%Dividing%n%by%p%leaves%remainder%1,%so%p%is%not%a%factor%of%n.%But%n%must%have%some%prime%factor%(possibly%n%itself).%This%factor%is%a%prime%greater%than%p.%%Contradiction! %QED.%Another Classic Proof by ContradictionTheorem:%√2%is%irrational.%Proof:%Suppose,%to%the%contrary,%that%√2%∈%Q.%Then%∃%p,%q%∈%N%s.t.%√2%=%p/q,%in%lowest%terms,%i.e.,%gcd(p,%q)%=%1.%So,%p2%=%2q2.%Thus,%p2%is%even.%%Therefore%p%is%even.%%%%[Because%if%p%were%odd%its%square%would%be%odd.%Exercise:%Prove%this!]%Let%p%=%2r.%%Substituting,%we%get%(2r)2%=%2q2.%%So,%2r2%=%q2.%Thus,%q2%is%even.%%Therefore%q%is%even.%Since%both%p%and%q%are%even,%gcd(p,%q)%≠%1.%Contradiction! %
View Full Document