Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 10 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 25 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
23FUNCTIONS Let A and B be two non empty sets If we can assign to every element a in A w and only one element b in B we say we have a function ffrom A to B and write fA 9B The elements of the initial set A are called the inputs of f and A is called the domain of the function On the other hand B is called the target space To every a in A there corresponds a unique b in B we write b fa Notice that a is the input while b is the output The collection of outputs is called the image of f Naturally we have image of f E B Notice that some elements of B may not be outputs Not a function 0 has 2 outputs J ViolaPrioli It is a function from A to B Not a function From P to Q 2 is not an input J ViolaPrioli A function can be presented in four different ways a by arrows b by a chart c by pairs d by a formula Next consider f0 1f1 1 and f2 1 which we can easily present in a chart do it and with arrows There is also a formula for this function actually it is fx x2 x 1 for each x E 0 1 2 When dealing with nite sets it is customary to resort also to pairs on the left we write each input next to it its corresponding output Thus the function above coincides with f O 1 1 1 2 1 Another example is provided by A 1 O 1 2 3 B n39 1 S n S 10 and fx x2 1 Please verify this fact J ViolaPn39oli More illustrations follow f N a N fn 2n gNNfn2n1 h n39 n gt 2 a N hn largest prime p ltn So we have for instance h20 19 h13 11 h121 113 A function is called onetoone if different inputs have different outputs That is whenever at a39 in A implies fa fa in B In terms of arrows no two arrows can end up in the same output A function is called onto B when every element of b is an output that is when the image off B and not simply image of f Q B The templates or quothow to prove follow J Viol aPn39oli 1 to prove that fA a B is a function you must see thatfor everya in A fa exists it is uniquely de ned and belongs to B 2 to prove that fA a B is a onetoone function you must see rst that it is a function see above and in addition you must prove that fa fa implies a a Observe that it is of the form quotif P then Qquot Notice that this is the contrapositive of at a39 in A implies fa fa 3 to prove that fA a B is onto B you must show rst that it is a function see above and in addition you must prove that for every b in B there exists a in A such that fa b This usually boils down to quotsolving for a ILLUSTRATIONS a Let fN a N as follows f0 O f1 1 and if n gt 1 set fn largest prime in the decomposition of n For instance f2 2 f45 f3x3x5 5 f81 f3x3x3x3 3 etc This f is a function from N to N it is not onetoone because f15 5 f45 and is not onto N because the outputs are 0 1 and prime numbers look at the de nition so 4 is not in the image is not an output J ViolaPn39oli b f 2 a Z fn 2n 1 is a function is onetoone but is not onto 2 images are odd numbers c Letsz a N fn sum of digits of n This is a function clearly not oneto one since f11 f20 2 Is fonto N Explain Our next example needs a result proved by induction Claim every number greater than 1 is the sum of primes Proof The result is true for n 2 Assume it is true for 2 3 k Let us prove it true for k 1 Observe that k 1 3 k 2 Since by inductive hypothesis k 2 is the sum of primes and since 3 is a prime we have that k1 is the sum of primes So the claim has been proved for all n as sought d Let A n39 n 2 2 and fA a A given by fn sum of all prime divisors of n 50 for instance f10 f2x5 7 and f36 f3x3x2x2 10 Then f is not onetoone because f25 10 f21 However f is onto A since by the previous result every number ofA is the sum of primes PROBLEM Solve for a the equations 1 fa 20 and 2 fa 213 J ViolaPn39oli e Let A n39 n 2 2 and fA a A given by fn 1 largest prime divisor of n ls f onetoone ls f onto A Explain NOTE For more illustrations see our link Syllabus section 25 Reversing the arrows Given a function fA a B we address the following question when can we reverse the arrows and obtain a function from B to A We notice two points a every b in B must be the end point of a arrow or else we can not reverse Hence f must be onto B b two different arrows can not have the same end point or else there is not a unique way of coming back to A Hence we discover that f must be oneto one In other words iff is onetoone and onto B we can reverse the arrows and obtain a function from B to A which we call the inverse of f This is denoted f391 B a A read quotf inverse and not quotf to the minus 1quot DEFINITIONsz a B is called bi39lective if it is onetoone and onto B In other words when f39l exists J ViolaP oli When f is bijective how do we construct f39l Answer Iff is given by arrows we reverse the arrows Iff is given by a chart we swap the columns Iff is given by pairs we interchange the positions ofthe entries in each pair Iff is given by a formula y fx we solve for x The following propositions are quite simple THEOREM Let A an B be nite sets Then there exists fA 9B bijective if and only if A B By applying the Pigeonhole Principle elements of A are balls elements of B are the boxes we also have THEOREM If A gt B then there is no onetoone function fA 9B As an exercise prove that if A lt B there is nosz a B onto B J Viol aPn39oli COUNTING FUNCTIONS Assume A m and B n How many functions are there from A to B Without loss of generality since we are counting only we may assume the setstobeA12 mandBb1bn We see that f1 has n choices The same applies to f2 etc By the Fundamental Counting Principle we have n n n nm choices We have obtained that szeB B lAl As a veri cation construct the nine functions that exist from A to B ifA 1 2 and B 1 O 1 Next we are interested in nding the number of onetoone functions from A to B According to our theorem above we must start with sets A and B that satisfy A S B So consider A m S B n As before f1 has n choices Now f2 has only n l choices recall that f must be onetoone now Likewise f3 has n 2 choices etc Conclude that there are nn 1n 2 n m1 onetoone functions This number is known to us from previous classes it is the falling factorial IBIPIAII J ViolaPn39oli Finally if A B n there are nn functions from A to B and exactly n bijective functions J ViolaPn39oli