Functions
This chapter presents how to use functions in combinatorial problems. The main objective is that the reader sees how constructing functions and observe basic properties of them can help to deduce meaningful information about the problem. This is done in t
- PDF / 375,741 Bytes
- 18 Pages / 477 x 684 pts Page_size
- 58 Downloads / 252 Views
Functions
5.1
Functions in Combinatorics
Given two sets A and B, a function f from A to B is a correspondence rule that “sends” each element of A to some element of B. We write f : A −→ B. For each element x of A, we denote by f (x) the element of B to which x is sent. Consider also the set f [A] = {f (x) | x is in A}, called the image of A under f . This set represents all the elements of B where we sent an element of A with f . It is important that every element of A is sent to exactly one element of B. Elements of B may not have been assigned to any element of A, or they may be assigned to more than one element. (See Fig. 5.1.) It is common to find functions while working in problems in combinatorics. Knowing how to work with them can be of great help. Of all the functions from one set to another, we are mainly interested in three types: injective, surjective and bijective functions. We say that a function f : A −→ B is injective if, for all x, y in A with f (x) = f (y), we have that x = y. In other words, a function is injective if it sends different elements to different elements. We say that a function f : A −→ B is surjective if, for all z in B, there is at least one element x in A such that f (x) = z. In other words, there is no element in B that was not assigned to an element of A. This is equivalent to f [A] = B. We say that a function f : A −→ B is bijective if it is both injective and surjective. Given two functions f : A −→ B and g : B −→ C, we define the composition g ◦ f : A −→ C as the function from A to C such that for all x in A, (g ◦ f )(x) = g(f (x)). Example 5.1.1 Prove that if f : A −→ B and g : B −→ C are injective, then g ◦ f : A −→ C is also injective. Solution Let x and y be two elements of A such that (g ◦ f )(x) = (g ◦ f )(y). Then g(f (x)) = g(f (y)). Since g is injective, this means that f (x) = f (y). Since f is injective, this means that x = y. Thus, g ◦ f is injective. P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_5, © Springer Basel 2013
59
60
5 Functions
Fig. 5.1 The figure shows a function f from A to B represented by arrows
Exercise 5.1.2 Prove that if f : A −→ B and g : B −→ C are surjective, then g ◦ f : A −→ C is also surjective. Exercise 5.1.3 Given sets A and B and a function f : A −→ B, there is a function g : B −→ A such that (g ◦ f )(x) = x for all x in A and (f ◦ g)(z) = z for all z in B if and only if f is bijective. Example 5.1.4 Given two finite sets A and B, prove that, if there is an injective function f : A −→ B, then |A| ≤ |B|. Solution We prove this by induction on n = |A|. If n = 1, as B must have at least one element for us to be able to define a function from A to B, the statement is true. Suppose the statement is true for every A of size n, and we want to prove it for some A of size n + 1. Let x be any element of A and consider the sets A = A\{x} and B = B\{f (x)}. Note that if y is different from x, then f (y) is different from f (x). Thus, f sends elements in A to elements in B . Moreover, if we restri
Data Loading...
