CS 30: Discrete MathematicsAmit%Chakrabarti%Winter%2017%A Very Special Type of RelationLet%S%be%a%set.%A%relation%R%on%S%that%is%• re9lexive,%• symmetric,%and%• transitive%is%called%an%equivalence%relation.%%Examples:%• Class%exercises%3.2%and%3.3.%• Equality%(the%most%important%example)%Functions: High-school Viewpoint0"5"10"15"20"25"30"35"40"0" 2" 4" 6"y"="x2"-1.5"-1"-0.5"0"0.5"1"1.5"y"="sin"x"Functions: CS Viewpointdef square(n): return n * ndef factorial(n): if n == 0: return 1 else: return n * factorial(n-1)Python%function%len(s)%gives%length%of%string%s.%Functions: IntuitionIntuitively,%a%function…%• takes%an%“input”%produces%an%“output”.%• thus,%connects%set%of%“inputs”%with%set%of%“outputs”.%• thus,%is%a%kind%of%relation%(a%very%special%kind).%Functions: DefinitionA%function%from%a%set%A%≠%∅!to%a%set%B%is%a%relation%%%%%%%%%%%%%%%%f%⊆%A%×%B%with%the%following%property:%• For%every%a%∈%A,%there%exists%one%and%only%one%%%%%%%b%∈%B%such%that%(a,b)%∈%f.%• i.e.,%for%every%input%there%is%an%output%and%there%is%only%one%output.%• We%write%f(a)%=%b,%instead%of%(a,b)%∈%f.%%Note%that%f(a)%is%always%uniquely%de9ined.%ALERT! This disagrees with Lehman-Leighton-Meyer book [LLM]; agrees with the Rosen book [Ros].Functions: PictorialThe%function%f(a)%=%a%+%1%from%{1,2,3,4}%to%{1,2,3,4,5,6}%4231564231Functions: PictorialThe%function%f(a)%=%a%from%{1,2,3,4,5,6}%to%itself%564231564231Functions: PictorialThe%function%f(a)%=%⎡a/2⎤%from%{1,2,3,4,5,6}%to%itself%564231564231Functions: PictorialA%function%from%{1,2,3,4,5,6}%to%itself%that%has%no%obvious%algebraic%formula%564231564231Not a Function!Output%unde9ined%for%input%2.%Mathematically,%there%is%no%pair%(2,x)%in%this%relation.%564231564231Not a Function!More%than%one%output%for%input%4.%There%should%be%only%one%pair%of%the%form%(4,x).%564231564231Functions: More DefinitionsSuppose%f%is%a%function%from%A%to%B.%The%notation%to%express%this%is:%f%:%A%→%B%• The%set%A%is%called%the%domain%of%f.%• The%set%B%is%called%the%co-domain%of%f.%• The%subset%of%B%given%by%{f(x)%:%x%∈%A}%%%%%%%%%%%%%%%%%%%%%%%is%called%the%range%of%f.%– Note%that%the%range%is%the%set%of%all%actual%outputs%of%f,%whereas%B%is%only%a%set%of%potential%outputs.%Surjective FunctionsSuppose%we%have%a%function%f%:%A%→%B.%%If%every%element%of%B%occurs%as%an%actual%output%of%f,%i.e.,%for%every%b%∈%B,%there%exists%an%a%∈%A%such%that%f(a)%=%b,%i.e.,%there%is%an%arrow%leading%in%to%every%element%of%B,%then%we%say%that%• f%is%surjective.%• f%is%a%surjection.%• f%is%onto.!Injective FunctionsSuppose%we%have%a%function%f%:%A%→%B.%%If%no%two%elements%of%A%produce%the%same%output,%i.e.,%for%every%x,%y%∈%A,%if%x%≠%y%then%f(x)%≠%f(y),%i.e.,%arrows%from%different%elements%of%A%lead%in%to%different%elements%of%B,%then%we%say%that%• f%is%injective.%• f%is%an%injection.%• f%is%one-to-one.%A Surjective FunctionBut%not%injective,%because%f(3)%=%f(5).%56423154231An Injective FunctionBut%not%surjective,%because%there%is%no%x%such%that%f(x)%=%3%5423564231More ExamplesLet%Z%be%the%set%of%all%integers%• Is%the%function%f%:%Z%→%Z%given%by%f(x)%=%2x%injective?%Is%it%surjective?%– Injective,%but%not%surjective%• How%about%f%:%Z%→%Z%given%by%f(x)%=%x%+%1%?%– Both%injective%and%surjective%• How%about%f%:%Z%→%Z%given%by%f(x)%=%⎣x/5⎦%?%– Surjective,%but%not%injective%• How%about%f%:%Z%→%Z%given%by%f(x)%=%|x|?%– Neither%injective%nor%surjective%BijectionsA%function%that%is%both%surjective%and%injective%is%called%a%bijective%function%(or%a%bijection).%%Exercise:%Let%f%:%A%→%B%be%a%function,%where%A%and%B%are%9inite%sets.%Can%you%say%something%interesting%about%A%and%B%if…%• f%is%surjective?%• f%is%injective?%• f%is%bijective?%%Hint:%think%about%|A|%and%|B|.%Study%Bee%%Concepts:%• Functions:%domain,%codomain,%range%• Surjective,%injective,%bijective%%Examples:%• Lots%of%examples%of%all%the%concepts%we’ve%de9ined%today.%• Study%them%carefully!%•