Functions

My friends and I are playing a game, and we have a problem. We need to flip a coin, but we haven't got one.

There's an app we could use instead – but let's be creative.

We do happen to have some six-sided dice. If we come up with the right kind of rule, dice rolls will work like coin tosses.

Let's say the numbers 1, 2, and 3 count as $\mathsf{heads}$, while 4, 5, and 6 count as $\mathsf{tails}$.

Other, similar rules would work just as well.

Say we stick with one such rule, where half the numbers map to heads, the other half to tails. And our dice rolls are fair: each number from 1 to 6 comes up just as often as each of the others. In that case we'll reach $\mathsf{heads}$ on half our rolls, and $\mathsf{tails}$ on the other half.

We've found a way to use fair dice rolls as a model of fair coin flips.111. We might also say that our rule expresses a relation that represents a coin using the sides of dice.

What is a function?

Our rule that converts dice rolls to coin flips is an example of a function.

What makes something a function? Let's get a little more abstract for just a second. Here's a function called $f$ that doesn't have to do with coins, or dice, or anything in particular:

A function is just a way to start from one set of things, and reach another set. Here, we start from points in $\mathsf{X}$ and arrive at points in $\mathsf{Y}$.222. We've numbered the points because it helps us talk about them. The names don't mean anything else, until we say they do. We aren't saying that is less than just because comes before , or anything like that. We could just as easily have chosen to name our points , , , and , , since all we need to do at this time is tell them apart. The points in $\mathsf{X}$ can also be called elements or members of $\mathsf{X}$.

No matter where we start in our source, a function must give us only one place to go in our target. In the current example, exactly one arrow needs to start at each of the three points in $\mathsf{X}$, and end somewhere in $\mathsf{Y}$.

We already saw two different functions, that transform fair dice rolls into fair coin tosses. The source set represented the six sides of the dice, so each function had six arrows.

If the number of arrows doesn't match the size of the source set, it's not a function.

These aren't functions. The one on the left has too few arrows – where do we go from $x_3$? The one on the right has too many – if we start at $x_2$, do we go to $y_1$ or $y_2$?

Importantly, a function doesn't need to reach everywhere in the target. More than one of its arrows can end in the same place.

Possible arrows

$\mathsf{X}$ and $\mathsf{Y}$ aren't the only source and target we could choose. Say we choose a target with three points (like $\mathsf{Y}$) but a source with only two points (unlike $\mathsf{X}$). In that case, how many ways are there to draw a function?

We don't need to label the sets or their points, to show all the ways we can follow the rules. Any time we have a source set with two things in it, no matter what they are, and we want to choose a function that reaches a target set with three things in it, no matter what they are, those are the 9 different mappings – combinations of arrows – we could possibly choose.

Some of those mappings make more sense than others, depending on the meaning we give to the members of the sets we want to map between.

The one on the left is clearly more valid, given the usual behaviour of cats and dogs. But what if we choose a different source set with the same size?

Humans may be omnivorous in general, but unless you know Max and Claire already, you probably can't say which of these describes their habits better.

We can choose any source and any target, and any possible function that goes between them, depending on our purposes. At the start of this post, we wanted to turn a dice roll into a coin flip. In our last two examples, we tried to show something about the diets of some creatures.

Once we decide on the sets, the possible ways we can draw arrows only depends on the size of the source and the size of the target.

Of course, people don't usually draw diagrams just because they want to remember things about people, or make rules about games. But as we move forward in this series, drawing diagrams like these will help us to understand probability in terms of following paths between collections of possibilities.

Composition

Why do my friends and I need to flip a coin for our game?

Because the next player only gets to move if it comes up heads!

This is also a function, and it fits together with our function from earlier.

Actually, if all we care about is starting with a dice roll and deciding whether the next player moves or not, we can forget coins were ever involved.

Gluing together functions like this is called composition. It always gives another function, called the composite. The source of the composite is the source of the first function, and the target is the target of the second function.

Each arrow in the composite is formed by collapsing a path made from two arrows from the original functions.

The composite doesn't care about what happens in between: the target of the first function, which is the source of the second function, which in this case is the set with $\mathsf{heads}$ and $\mathsf{tails}$ in it. The composite forgets what happens in between.

Remembering and returning

There's one more thing we should explore in this post. What does it mean to remember the path you followed—how you arrived where you did?

We've seen that a function doesn't need to reach every point in its target—but some functions do. Our dice rolling function is an example: there was always some way to reach either $\mathsf{heads}$ or $\mathsf{tails}$.

Functions like this are called "onto"—they map onto the entire target. But notice something else about this function: multiple arrows end in the same place.

A function can have arrows that end in the same place… but some functions don't: each point they reach in their target, they reach only once. These functions are called one-to-one: there's only one point in the source that reaches any one point in the target.

Our mapping from cats and dogs to their diets is an example.

This function is one-to-one, but it isn't onto: nothing reaches $\mathsf{herbivores}$.

If a function's source is smaller than its target, we know it won't have enough arrows to reach everywhere in the target. It can't be onto. And if a function's target is smaller than its source, then we know it can't be one-to-one—there are more arrows than there are places to go, and some must end in the same place!

A function can be one-to-one, or onto, or both, or neither. We've already seen one that's neither:

We don't reach every point in $\mathsf{Y}$, so we're not onto. And two arrows reach the same point, so we're not one-to-one. But since $\mathsf{X}$ is the same size as $\mathsf{Y}$, at least it is possible to draw a function that is both one-to-one and onto – called an isomorphism.

There are six possible isomorphisms from $\mathsf{X}$ to $\mathsf{Y}$.

If our function is an isomorphism, then there's a unique match-up between points in our source and points our target. For each of the six isomorphisms above, it's easy to flip around its arrows to get an inverse function, which goes in the opposite direction.

These inverses are also isomorphisms, and they are the only possible isomorphisms that go "backwards" from $\mathsf{Y}$ to $\mathsf{X}$. And because they represent unique match-ups, we could of course reverse them again to get the blue ones back.333. In this case we haven't distinguished the source and target points with labels, so the orange inverses actually appear identical to their respective blue functions, minus the colour change and horizontal mirroring.

Here's a specific example of an isomorphism: a rule that reverses the order of the numbers on our dice. When we roll a 6, we get a 1, and vice versa.

If we follow our function, and then its inverse—blue arrow, then orange—we arrive back where we started. We can also follow the inverse first—orange, then blue—and arrive back where we started, on the other side.

In either case, an isomorphism never forgets. And functions that aren't isomorphisms are "forgetful", in a sense. How?

What if my friends and I have the opposite problem we did yesterday? We have a coin, but no dice. Can we just reverse our function from earlier, to get another function that maps coin flips to dice rolls?

We can't. Look at the squiggly arrows – a function can't map $\mathsf{heads}$ to 1, 2, and 3 all at once. Our function can only have two arrows, but we wanted the possibility of rolling any of the six sides.444. Actually, it is possible to use coin flips to simulate dice rolls – but not a single coin flip, which has only two outcomes and can't be mapped to all six sides.

If I tell you that I rolled the dice and the converted result was $\mathsf{tails}$, you have no way of knowing if I actually rolled a 4, 5, or 6. Because the dice-to-coin function isn't one-to-one, some of its arrows end at the same place, and it forgets where it started. Once we follow a blue arrow, we can't follow an orange arrow back, unlike what we could do with the isomorphism.

But just like we could with the isomorphism, we can follow the blue arrows back if we choose some of the orange arrows, and follow them first.

We chose to map $\mathsf{heads}$ to 2, and $\mathsf{tails}$ to 6. That won't be enough to return us to 1, 3, 4, or 5 (red points) if we follow the blue arrows first. But if we follow the orange arrows first, our blue dice-to-coin function does have the two correct arrows to convert 2 and 6 back to their respective coin flips. So while the blue function does invert the orange one, the opposite is not true.

Actually, the blue dice-to-coin function can invert any such function we choose that converts a coin flip to a dice roll, so long as it reaches 1, 2, or 3 from $\mathsf{heads}$, and 4, 5, or 6 from $\mathsf{tails}$ – that is, so long as it respects the overall $\mathsf{heads}$-$\mathsf{tails}$ split of the blue function.

These are all of the possible right inverses of our dice-coin function.

So that's what happens when a function is onto but not one-to-one. What about the opposite?

We can easily invert the two existing blue arrows, but we have no idea how to return from somewhere we never arrived ($\mathsf{herbivores}$).555. Why would we want to invert this function? Say Max and Claire are on a team together, and someone mentions "the meat-eater on the team". An inverse function could tell us that they're referring to Max. Of course, if the team were larger, multiple team members' arrows might point to . Then, "the meat-eater" couldn't uniquely refer to Max anymore.

To invert our function, we have to choose one of the two squiggly arrows to follow.

I mapped $\mathsf{herbivores}$ to $\mathsf{Claire}$, since an omnivore is kind of a sometimes-herbivore, I guess. But does that make sense? This is an important reminder that just because the math is flexible and allows you to do something, doesn't mean that it makes sense to do it when you're using the math as a model of something real.

The situation is opposite to what we faced when trying to invert our dice-coin function. If we follow the blue arrows first, the inverse we've chosen can return us to the same starting person, but the extra arrow we had to choose will go unfollowed (grey).

However, if we follow the orange arrows of our inverse first, $\mathsf{herbivores}$ and $\mathsf{omnivores}$ both map to Claire and there's no way for us to return to $\mathsf{herbivores}$ (red).

Here, there are only two possible left inverses: one maps $\mathsf{herbivores}$ to Claire, like above. The other would map $\mathsf{herbivores}$ to Max—which seems contradictory with $\mathsf{carnivores}$ already mapping to Max, though nothing about the rules of functions alone would stop us from making that choice.

Any function that is one-to-one has at least one left inverse, and any function that is onto has at least one right inverse. If a function is both one-to-one and onto it's an isomorphism, and it has only one inverse, which is both the left and the right inverse—called simply "the" inverse.

That's it for now!

Next time we'll learn about channels. They're kind of different from the functions we've seen so far, and they'll be the parts we'll build our theory out of.