Functions as sets of ordered pairs

Another thing that you will need to know as we move forward is a bit about functions. Functions may seem like mysterious entities, but set theoretically speaking, they are really quite simple. After all, what a function does is it takes an input, and provides a single output. For example, if we take the function $+2$, and apply it to the number $3$, we get $5$. There are various ways of specifying the $+2$ function, like $f(n)=n+2$, or $f: n \mapsto n+2$, but the only thing that is important is that there are a bunch of inputs, and for each input, there is just one output. So if $f$ is the $+2$ function, then $f(3)=5$.

Perhaps somewhat confusing to the untrained eye is the fact that $f(3)$, as specified above is, by itself, the same as the number $5$. So in this context, it makes sense to write things like $f(3)+3=8$, or $f(3) \in \mathbb{N}$.

Functions can be represented in set theory by sets of ordered pairs. These ordered pairs essentially represent a list of all input-output pairs that a function is made up of. For example, if we take the $+2$ function again, defined on the natural numbers $\mathbb{N}$, set theoretically, it would be the set of all the following ordered pairs: $$\begin{gathered} \langle 0, 2\rangle\\ \langle 1, 3\rangle\\ \langle 2, 4\rangle\\ \langle 3, 5\rangle\\ \langle 4, 6\rangle\\ \vdots \end{gathered}$$ Or in one line, $\{\langle 0, 2\rangle, \langle 1, 3\rangle, \langle 2, 4\rangle, \langle 3, 5\rangle, \langle 4, 6\rangle, …\}$. Again, this is just a list of all possible input-output pairs for the function.

Note the use of ‘$…$’ in specifying the $+2$ function. Since the function $+2$ is defined on all natural numbers, naturally, its set-theoretic representation will be an infinitely large set! What the dots represent is that the list goes on forever since, for any natural number, you can always just add $2$ and get another one.

One thing that you need to keep in mind is that not any set of ordered pairs constitutes a function. In particular, functions are those sets of ordered pairs where for each input, there is only one output. One way to formulate this idea is to say that if there is an input to the function, and seemingly two different outputs, then those two seemingly different outputs must be the same. Hence:

The above definition ensures that whatever conforms to that specification is an actual function. On the other hand, one can introduce more restrictions on these sets, to define certain special classes of functions.

Let’s start with some useful terminology. According to the above definition, there are no functions which are one-to-many, in the sense of assigning many outputs to one input. That would immediately ensure they are not a function.

What about many-to-one functions? Indeed, these are possible. Suppose we have a function that assigns to each person their age at the moment. At any one moment, this would give us a very large set of ordered pairs: $$\begin{gathered} \langle\text{Dwayne Johnson}, 51\rangle\\ \langle\text{Dua Lipa}, 28\rangle\\ \langle\text{Curtis Jackson}, 48\rangle\\ \langle\text{Idris Elba}, 51\rangle\\ \langle\text{Christian Bale}, 50\rangle\\ \vdots \end{gathered}$$

Since there are many people on Earth, there will be many that share their age at any one moment (at least as things currently stand). Above, you can immediately see that Dwayne Johnson and Idris Elba are the same age at the moment of writing this book. Thus, the person-to-person’s-age function is many-to-one. Again, note that it is a function, and thus not one-to-many, and this is by nature, since every person only has one age.

On the other hand, some functions are not many-to-one, but one-to-one. This means that for two distinct inputs, they never have the same output. Take the $+2$ function again. The $+2$ function on the natural numbers is one-to-one, since for each two distinct natural numbers $n, k$, $n+2\neq k+2$. This is easy to see since if $n+2=k+2$ were the case, then $n=k$ would also be the case, even though we specified those two numbers must be distinct. In other words, the same output can only be had if the input is really the same. One-to-one functions are also called injective.

At times, we may want to explicitly specify not only the domain on which the function is defined (like how the function $+2$ has as domain the natural numbers), but also what its codomain is, which is a (not necessarily proper) superset of its range. For example, we may say that $+2$ is a function from the domain $\mathbb{N}$ of natural numbers to the codomain $\mathbb{N}$ of natural numbers. This may be written $+2: \mathbb{N} \to \mathbb{N}$. Note that this notation is different from the above $n \mapsto n+2$ which specifies that for each $n$, $n$ is ‘mapped to’ $n+2$, i.e., $+2(n)=n+2$.

In connection, one may find that some functions ‘cover’ their codomain, in the sense that for each member of a function’s codomain, there is a certain input value which outputs just that member. A function that is not like this is the $+2$ function specified as $\mathbb{N} \to \mathbb{N}$, since neither $0$ nor $1$ is an output for any input value (since the input value would have to be either $-2$ or $-1$, which are not natural numbers). On the other hand, we may specify a function $\times2: \mathbb{N} \to \mathbb{N}_\text{Even}$ such that $n \mapsto 2\times n$. This function covers its codomain, the even numbers, since for every even number $k$, there is a natural number $n$ such that $n \times 2=k$. Functions like $\times 2: \mathbb{N} \to \mathbb{N}_\text{Even}$ are called surjective or onto. Note that whether a function $f$ is surjective is relative to how its codomain is specified. Clearly, $\times 2^*: \mathbb{N} \to \mathbb{N}$ would not be surjective, since no odd number ever gets output.

Finally, some functions are both injective and surjective, or both one-to-one and onto. These functions are called bijective or are said to be a one-to-one correspondence (sometimes, 1-1 correspondence.) For example, it is easy to see that the function $\times2: \mathbb{N}\to \mathbb{N}_\text{Even}$ is bijective or a one-to-one correspondence. We already know that it is surjective. But it is also injective, since there are no two distinct natural numbers $i, j$ such that $i\times 2=n$ and $j\times 2=n$ ($n \in \mathbb{N}_\text{Even}$). Thus, it is bijective.

Bijective functions are very important, since they essentially allow one to count the members of a set by pairing them with numbers. For example, if you have the set $\{a, b, c\}$, this set can be put into 1-1 correspondence with the set $\{1, 2, 3\}$ (in various ways), so it has three members. But notice that the set $\{a, b\}$ cannot be put into 1-1 correspondence with $\{1, 2, 3\}$. And the set $\{a, b, c, d\}$ cannot be put into 1-1 correspondence with $\{1, 2, 3\}$ either. Indeed, for any set $\{a_1, a_2, …, a_n\}$, it can only be put into 1-1 correspondence with one initial segment of the (positive) natural numbers, $\{1, 2, …, n\}$.

Note also that if $1$–$1$ correspondence provides a definition of ‘has the same number of elements as’, then $\mathbb{N}$ and $\mathbb{N}_\text{Even}$ have the same number of elements by the bijective function $\times 2$ (infinitely many), even though $\mathbb{N}_\text{Even} \subset \mathbb{N}$. Weird!

Finally, here is a definition that will be useful later on.