Counting I xabcde 123 The function on the left is surjective(every element on the right is mapped to at least once), but not injective(element 3 is mapped to twice). The function on the right is injec- tive(every element is mapped to at most once), but not surjective(element 4 is mapped to zero times) Earlier, we observed that two sets are the same size if there is a bijection between them Similarly, surjections and injections imply certain size relationships between sets Rule 4 (Mapping Rule). 1.lf:X→ Y is surjective, then X≥|Y 2.Jf:X→ Y is injective,, then X≤|Y 3. Iff X- Y is bijective, then X=Y 3.1 The Pigeonhole Principle Here is an old puzzle many socks must you withdraw to be sure that you have a matching pair i A drawer in a dark room contains red socks, green socks, and blue socks. He For example, picking out three socks is not enough; you might end up with one red,one green, and one blue. The solution relies on the Pigeonhole Principle, which is a friendly name for the contrapositive of part ( 2)of the Mapping Rule. Let's write it down If X >Yl, then no function f X-Y is injective Now let's rewrite this a second time to eliminate the word"injective" since, by now, there's not a ghost of a chance that you remember what that means Rule 5(Pigeonhole Principle). IfIX>Y, then for every function f: X- Y there exist two different elements of X that are mapped to the same element of10 Counting I X Y X Y a - 1 a - 1 3 2 3 2   b PPPPPP b PPPPPP   c  q 3 c Q  q  3 3 Q PPPPPP    d   q d  Q  4 Q 4  QQ e  s 5 The function on the left is surjective (every element on the right is mapped to at least once), but not injective (element 3 is mapped to twice). The function on the right is injec￾tive (every element is mapped to at most once), but not surjective (element 4 is mapped to zero times). Earlier, we observed that two sets are the same size if there is a bijection between them. Similarly, surjections and injections imply certain size relationships between sets. Rule 4 (Mapping Rule). 1. If f : X → Y is surjective, then |X Y | ≥ | |. 2. If f : X → Y is injective, then |X Y | ≤ | |. 3. If f : X → Y is bijective, then |X| = | | Y . 3.1 The Pigeonhole Principle Here is an old puzzle: A drawer in a dark room contains red socks, green socks, and blue socks. How many socks must you withdraw to be sure that you have a matching pair? For example, picking out three socks is not enough; you might end up with one red, one green, and one blue. The solution relies on the Pigeonhole Principle, which is a friendly name for the contrapositive of part (2) of the Mapping Rule. Let’s write it down: If |X > Y | | |, then no function f : X Y → is injective. Now let’s rewrite this a second time to eliminate the word “injective” since, by now, there’s not a ghost of a chance that you remember what that means: Rule 5 (Pigeonhole Principle). If |X > | | |Y , then for every function f : X Y there exist two different elements of X that are mapped to the same element of Y . →