Counting I where bi= l if and only if Ti is in that subset. For example, if n= 10, then the subset (a2, I3, 5, 17, 11o) maps to a 10-bit sequence as follows subset. 2, sequence We just used a bijection to transform the original problem into a question about sequences- exactly according to plan! Now if we answer the sequence question, then weve solved our original problem as well But how many different n-bit sequences are there? For example, there are 8 different 3-bit sequences (0,0,0)(0,0,1) 0,1,0) (0,1,1 (1,0,0)(1,0,1)(1,1,0)(1,1,1) Well, we can write the set of all n-bit sequences as a product of sets {0,1}×{0,1}×…x{0,1}={0,1} Then Product Rule gives the answer {0,1}2=|{0,1yn This means that the number of subsets of an n-element set X is also 2n. Well put this 3 More Functions: Injections and Surjections Bijective functions are incredibly powerful counting tools. A few other kinds of functions are useful as well; we'll look at two now and one more next time. A function f: X-Y surjective if every element of Y is mapped to at least once injective if every element of y is mapped to at most once bijective if every element of r is mapped to exactly once Weve repeated the definition of a bijective function for comparison. Notice that these definitions immediately imply that a function is bijective if and only if it is both injectiv and surjective. Now the names"surjective"and"injective"are hopelessly unmemorable and nondescriptive. Some people prefer the terms onto and into, respectively, perhaps the grounds that these are hopelessly unmemorable and nondescriptive- but shorter. Anyway, here are a couple examples� �� Counting I 9 where bi = 1 if and only if xi is in that subset. For example, if n = 10, then the subset {x2, x3, x5, x7, x10} maps to a 10­bit sequence as follows: subset: x2, x3, x5, x7, x10 sequence: { ( 0, 1, 1, 0, 1, 0, 1, 0, 0, 1 } ) We just used a bijection to transform the original problem into a question about sequences— exactly according to plan! Now if we answer the sequence question, then we’ve solved our original problem as well. But how many different n­bit sequences are there? For example, there are 8 different 3­bit sequences: (0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1) Well, we can write the set of all n­bit sequences as a product of sets: {0, 1}n {0, 1} × {0, 1} × . . . × {0, 1} =� n terms Then Product Rule gives the answer: |{0, 1} = n | |{0, 1}|n = 2n This means that the number of subsets of an n­element set X is also 2n. We’ll put this answer to use shortly. 3 More Functions: Injections and Surjections Bijective functions are incredibly powerful counting tools. A few other kinds of functions are useful as well; we’ll look at two now and one more next time. A function f : X Y → is: • surjective if every element of Y is mapped to at least once • injective if every element of Y is mapped to at most once • bijective if every element of Y is mapped to exactly once We’ve repeated the definition of a bijective function for comparison. Notice that these definitions immediately imply that a function is bijective if and only if it is both injective and surjective. Now the names “surjective” and “injective” are hopelessly unmemorable and nondescriptive. Some people prefer the terms onto and into, respectively, perhaps on the grounds that these are hopelessly unmemorable and nondescriptive— but shorter. Anyway, here are a couple examples: