Functions and Relations

# Functions and Relations

## Sets

Consider two sets, which we will call S and T.

There are several ways in which the two sets S and T may be related:

• The sets may be identical, that is, every element of one set is also an element of the other set.
• The sets may be disjoint, that is, no element belongs to both sets. There is no overlap between the sets.
• Set S may be a proper subset of set T. That is, every element of S is also an element of T, but T has some elements that are not in S.
• Set T may be a proper subset of set S.
• The sets may overlap (some elements are in both S and T), without either being a proper subset of the other (each set contains some elements that are not in the other set).

## Relations

However, this page isn't really about sets. This page is really about relations and functions. For clarity, all our examples use disjoint sets (see Figure 1). However, the same definitions apply regardless of the relationship between the two sets. The only difference is that, if we didn't use disjoint sets, the examples would be harder to figure out.

Suppose we have two sets, S and T. A relation on S and T is a set of ordered pairs, where the first thing in each pair is an element of S, and the second thing is an element of T.

For example, suppose S is the set {A, B, C, D, E}, while T is the set {W, X, Y, Z}. Then one relation on S and T is {(A,Y), (C,W), (C,Z), (D,Y)}. There are four ordered pairs in the relation. We can draw this as four arrows going from S to T (see Figure 2). One arrow goes from A to Y; another goes from C to W; another goes from C to Z; and another goes from D to Y.

The purpose of this page is just to define terms. Giving names to things is not important unless you can later use those names to talk about the things. These terms we define here are used throughout mathematics, and are pretty important; but we don't go into any of that here. We just define the terms.

The most important of the terms we will define is function. You have probably seen this word defined in algebra or calculus, and you may think this is another meaning for the same word. It's important to realize that there is only one meaning in mathematics for the word "function", and this is it. Moreover, the definition given here is the "best" definition because, since the definition is given in terms of sets, it is the most general and most applicable definition. Any other definition is just a special case.

Anyway, to continue.

The domain of a relation on S and T is the set of elements of S that appear as the first element in an ordered pair of the relation. In the relation {(A,Y), (C,W), (C,Z), (D,Y)}, the domain is {A, C, D}. If you look at Figure 2, these are the elements of S that have arrows coming out of them.

The range of a relation on S and T is the set of elements of T that appear as the second element in an ordered pair of the relation. In the relation {(A,Y), (C,W), (C,Z), (D,Y)}, the range is {W, Y, Z}. If you look at Figure 2, these are the elements of T that have arrows pointing to them.

For some reason, the word codomain has become popular as a synonym for "range." I think it's an ugly word. If anyone has an explanation for why this word has become popular, I would very much like to hear it.

In Figure 2, not every element of T has an arrow pointing to it. That is, there are some elements of T (in particular, the element X) that do not occur as a second element of an ordered pair. We say that the relation is into T.

Suppose we have a relation in which every element occurs (at least once) as a second element of an ordered pair. For example, the relation {(A,Y), (B, X), (C,W), (C,Z), (D,Y)} (See Figure 3) is just like the previous relation, except that it also contains the ordered pair (B, X). The relation is onto: every element of set T has an arrow (at least one) pointing to it.

While the word "onto" has a precise definition (the range of the relation is the set T itself), the word "into" is not usually so well defined. "Into" could be used to mean "not onto" (there is at least one element of T that does not have an arrow pointing to it), or it could mean "not necessarily onto", that is, there might be some element of T that does not have an arrow pointing to it. Different authors might choose to define "into" in different ways, or not define it precisely, or just not define it at all.

Suppose we put in every possible arrow from S to T. That is, from each element of S we draw arrows to each element of T (see Figure 4). This "largest possible relation" is called the Cartesian product of S and T. Every other relation on S and T is a subset of the Cartesian product.

(How is it possible for a relation to be a subset of another relation? Remember that a relation is just a set of ordered pairs. Or, in our pictures, a relation is a set of arrows.)

Next we will say that a relation is one to one, or 1-1, if no element of S occurs more than once as the first element of an ordered pair, and no element of T occurs more than once as a second element of an ordered pair. In other words, no element of S or T has more than a single arrow attached to it. (See Figure 5).

(This definition holds even when S and T are not disjoint, but the picture is a little more confusing. An element that is in both S and T could have a single arrow attached to it, as before, but at both ends!)

## Functions

Now we get to what is perhaps the most important term. Suppose every element of S occurs exactly once as the first element of an ordered pair. In our pictures (see Figure 6), every element of S has exactly one arrow coming from it. This kind of relation is called a function.

Another word for function is mapping. A function is said to map an element in its domain to an element in its range.

Here are some important facts about a function from S to T:

1. Every element in S in the domain of the function; that is, every element of S is mapped to some element in the range. (If some element in S has no mapping (arrow), then the relation is sometimes called a partial function, but it is not a function!)
2. No element in the domain maps to more than one element in the range.
3. The mapping is not necessarily onto; some elements of T may not be in the range.
4. The mapping is not necessarily 1-1; some elements of T may have more than one element of S mapped to them.
5. S and T need not be disjoint.

To tell whether a relation on S and T is a function, you can ignore T altogether. Just look at S. If every element of S has one and only one element coming out of it, then the relation is a function.

## Kinds of functions

There are three kinds of functions that are important enough to have special names: surjection, injection, and bijection.

Since the domain of a function from S to T is the entire set S (by the definition of function), and since the range of a surjective function from S to T is the entire set T, this means that every element of both sets is in the relation (has an arrow connected to it).

Also note that if you have a surjection from S to T, S may have more elements than T, or it may have the same number of elements, but it cannot have fewer elements than T. This is because every element of S has exactly one arrow emanating from it, but each element of T has at least one arrow pointing to it, and could have many.

An injection or one-to-one function from S to T is a function that is one to one. That is, every element in both S and T has at least one arrow attached to it. By the definition of function, of course, every element of S has exactly one arrow emanating from it, no more, no less. A one-to-one function also requires that every element of T can have no more than one arrow pointing to it; but there could be elements of T that do not have any arrows pointing to them.

Figure 7 shows an injection. However, we had to modify the sets a little bit to get this example. A little thought will show that, with an injection from S to T, T must have at least as many elements as S. To get our example, we removed some elements from S. (We could equally as well have added elements to T.)

Finally, a function that is both 1-1 and onto is called a bijection. Such a function maps each and every element of S to exactly one element of T, with no elements left over. shows a bijection. Again, we had to modify the sets a little because, with a bijection, sets S and T have to have exactly the same number of elements.

A bijection is particularly interesting because this kind of function has an inverse. If you took a bijection from S to T and reversed the direction of all the arrows, you would have a bijection from T to S. This new function would be the inverse of the original function.