Mappings and Functions

This is a topic which is generally quite intuitive, but still gives trouble to many students, particularly since it is very rarely taught on its own.

We consider some sets A and B. We take each element of A and assign to it some subset of B. This assignment is called a mapping. More formally, if f is a mapping from A to B, then for each element a in A, there exists some subset B' of B, such that f(a) = B'. To illustrate, consider the set A as your 5 closest friends. Now let B be {tall, short, dark-haired, fair-haired, male, female}. Then you can have a mapping for each of your friends in A, which describes them in terms of the characteristics listed in B. For example, you might have some short, dark-haired female friend, let's call her Angela. Then if we say that f is the description mapping, f(Angela) = {short, dark-haired, female}.

As you can see, mappings are a general way of connecting the elements of one set, with the elements of another set. These sets, of course, will generally not be friends and descriptors. In more general settings, we will have the sets belong to some number system. However, this does not make a difference in what the mappings themselves mean. That is, if we take your 5 closest friends and call them 1, 2, ... 5, then take the descriptors in B and call them, in order, 1, 2, ... 6, we can do the same thing as before. If, for example, Angela is friend 1, we have f(1) = {2, 3, 6}. This statement gives exactly the same information as the one before, i.e., that your friend Angela is short, dark-haired and female.

Naturally, not all mappings will be from or to finite sets. In fact, most interesting mappings only happen in infinite (countable or uncountable) sets. This makes no difference to the definition of the mapping. The idea remains the same: to each specific element of A, we assign some subset of B.

We now move to a specific type of mapping, called a function. A function from A to B is a mapping which assigns to each element of A a subset of B with a single element in it. In other words, it assigns one element of B to each element of A. For example, let's take the integers (... -1, 0, 1, 2, ...) and take the function f(x) = x * x. Then f(0) = 0, f(1) = 1 = f(-1), f(2) = 4 = f(-2) and so on. Note that different elements of A can be assigned the same element from B, but not the other way around. We call A the domain of the function and B the codomain of the function. Furthermore, the set of all elements of B which are assigned to some element of A by f is called the range of f. In the above example, f will never give a negative number. Its range is the positive integers. In addition, we call f(x) the image of x under f.

The reason that functions are important is that, under certain conditions, they can be composed together. That is, if we have 3 sets, A, B and C and two functions, f and g, such that f is a function from A to B and g is a function from B to C, we can define the function h = gf from A to C. As an example, consider the functions f(x) = x * x and g(y) = y + 1. Then we can compose them together to get g(f(x)) = (x * x + 1).

Now the question is, under what conditions can we compose functions like that? The only real requirement is that the range of f is a subset of the domain of g. That is, we need that whatever f gives as its "output" can be plugged into g. If this is not the case, then there will be some f(x) which g can not assign any value to. We then say that g can not be composed with f.

We will now look at more specific families of function. The first such family are the "one-to-one" functions, or "injections". These are the functions for which, if f(x) = f(y), then x = y. That is, if we take two distinct elements in the domain of f, their images in the range of f are also distinct. If we have such a function, then we can also talk about the idea of a pre-image. That is, if f(x) = y, we say that x is the pre-image of y. If f is not on-to-one, we cannot say that, as there might be some other element 2, for which f(w) = y. But the restriction that at most one element can map into y means that the idea of a preimage is possible.

The second family we will consider are the "onto" functions, or surjections. These are the functions for which the codomain is also the range. If we take all the real numbers, f(x) = x * (x - 1) * (x + 1) is an onto function. For any y you pick, there exists some x, for which y = f(x). It is not a one-to-one function, since f(1) = f(0) = f(-1) = 0, but it is onto. Onto functions are important, because if a function f from A to B is onto, it can be composed with any function g with domain B.

Finally, we consider the functions which are both one-to-one and onto. These are known as bijections, or invertible functions. If an f is a bijection, it means that every element in the domain, A, maps to exactly one element in the codomain, B. This means that, going in reverse, we can assign to each element in B its preimage under f on A and make a new function g, which will be the inverse of f. For example, let us take the function f(x) = x + 1. It is both one-to-one and onto, so it is invertible. Since it maps x to x+1, we can simply reverse the mapping to get a function g, which maps x+1 to x. This function g, will be the inverse of f. Clearly, this function, as expected, is g(x) = x - 1.

As you can see, even a function as simple as f(x) = x + 1, belongs to a very special family of functions. This is unsurprising. The functions which are the most powerful and have the most desirable characteristics are generally very restricted. Though we generally think of functions as simple things like x + 1, x/2 and so on, these are very well-behaved functions, and not representative of the majority of functions.