Fun with Category Theory and Dynamical Systems

I have always loved finding those parts of mathematics where big ideas just pop out almost by accident, appearing fully formed in a surprising and delightful way. Who, for example, could fail to marvel at how topology manages to capture so many unique and striking meanings into words like continuous which can mean very different things just by choosing a different topology in which to interpret the same definition?

Something like this happens in categories by considering limits and colimits. One simply draws a simple picture, follows a simple set of rules, and important ideas pop out. Here, I’m going to present the technique, and then draw a particular picture and see how two big ideas in dynamical systems jump out and startle us with their unexpected appearance.

Don’t worry if you’re not up to speed on category theory. In fact, I won’t even be using real category theory at all here, because we don’t need that kind of abstraction. The only ideas we need are sets, functions, function composition, and identity functions. I’ll assume you know what these mean.

Sets without elements?

Here’s a game: How much can we say about sets without talking about their elements (that is, the things inside of them)? We can still talk about the functions from one set to another, including the identity function, and even composition of those functions. We just can’t talk about the members themselves.

At first, that might seem like a silly restriction, sort of like trying to go a whole day without using any words with the letter Q. That’s okay; I don’t need to convince you it’s not silly. If I were trying to convince you, though, I might mention that the more general notion of categories includes more than just sets, and those things might not have elements. I might also say that the whole idea of membership in a set is an ultimately undefinable primitive idea in conventional mathematics, and using that idea too informally has led to logical paradoxes in the past. So it makes some sense to ask whether, instead of just assuming that set membership makes sense, we can start with a different foundation (functions) and derive the idea of set membership in a logically sound way. But again, you don’t need to be convinced. Just humor me. It’s a game. Those are the rules.

Let’s practice:

• Can I say “The set A has only one element” without saying anything about elements?
  …
  Surprisingly, yes! Instead of talking about the one element, I can say this: “Given any other set B, there is exactly one function f : B → A.”

If A had more than one element, then you could choose where to map an element of B. A having only one element means that everything in B has to map to that element; there is no choice. So the existence of exactly one such function means the same thing as saying A has one element.

Can you find a way to say “The set A is empty”? There is more than one answer. I’ll leave it as an exercise for the reader! (Hint: you can do it with a straight-forward application of constructions and diagrams in this post.)

Let’s do one that’s a little more complicated, just to get an idea of how things go in general.

• Can you say “The set A has the same elements as the set B” without saying anything about elements?
  …
  Since we have no way to actually name or describe those elements (since we’re forbidden from even talking about them), we can not say this. But we can get close, by saying that A has the same number of elements as B. Here’s how to do it: “There is a function f : A → B, and another function g : B → A, and g ∘ f is the identity function on A, and f ∘ g is the identity function on B.”

In mathematics, this is known as a one-to-one correspondence, and it proves that these two sets have the same number of elements (formally: the same cardinality, since it might actually be infinite and therefore not a number, per se.)

This will be a sort of pattern. We can’t name the things in our sets, but we can get an idea of what’s in them by showing that they correspond to the things we want. So instead of a set with the same elements, we got a set, and a function that shows how whatever is in that set corresponds to the set we wanted. Another way of saying this is to say that the sets are the same “up to one-to-one-correspondence,” or more abstractly, “up to isomorphism.”

Getting the hang of it? Okay, one more. This one will come up later, so follow along. Take a couple of sets: call them A and B. The cartesian product of A and B, written A × B, is the set of ordered pairs (x, y), where x is an element of A, and y is an element of B.

Back to our game from earlier.

• Can you define the cartesian product without talking about elements?
  …
  Well, just like the previous example, we can’t be sure what exactly the elements in our set are called, but we can say that a set has the right number of elements to be the cartesian product. And what’s more, we can even provide a pair of functions that give the components of the ordered pair, giving a way to interpret everything in that set as an ordered pair.

To look at how that’s done, let’s define a couple functions p and q, called projections, that each pick one of the components out of an ordered pair.

The green function is p : A × B → A, and the red function is q : A × B → B. They don’t really do much. They are almost as boring as the identity function! But just like the identity function was useful for saying how two sets have the same number of elements, these will be useful for defining the cartesian product.

We have a problem: the projections are defined in terms of what they do with elements, but we cannot talk about elements. (The rules of the game allow us to talk about the identity function as we did last time, but we have no such exception for projections.) So at first glance, the best we can do is just say that p and q are functions from A × B to A and B.

All that structure about ordered pairs and components, sadly, is lost. But we can recover it by saying something about how this relates to other ways to define functions to A and B. Here’s the final answer.

“A × B is a set where there are two functions p : A × B → A, and q : A × B → B, and for any other set S and functions f : S → A and g : S → B, there is a unique h : S → A × B, such that f = p ∘ h, and g = q ∘ h.”

Well, that was a mouthful. Here’s what it means.

• The functions f and g mean that every element of S has some associated pair of elements from A and B. Any particular S may not be associated to all of the possible pairs, but importantly, we can choose an S and f and g that associate any pair, if we like.
• That h exists means, therefore, that for any choice of elements from A and B, there’s an element in A × B that corresponds to it. The projections p and q tell us which A and which B each element corresponds to.
• That h is unique means that there is only one such element for each pair, since otherwise there would be a choice of which element h points at.

So, all together, this says A × B has exactly one element in it for each choice of a pair of elements from A and B, and p and q tell us which pair that is. Success!

Generalizing to the limit

That last answer has a common form. It says that among all the possible choices of a set and related functions (that is, S, f, and g), there is one particular choice (A × B, p, and q) that’s somehow universal, because any other choice you could make is nothing more than a mapping to that universal one. In category theory, this form of thing is called a limit. This is only distantly related to the limits you might have seen in calculus, so if that’s what jumped in your mind, go ahead and forget it again.

The cool thing about limits is that you can take any collection of sets and functions that you like, and ask what their limit is. Start from any little diagram of sets and functions, and an idea pops out. Often, it’s an important central idea about sets and functions, like cardinality and one-to-one correspondence (which come from the diagram with one set) or cartesian products (which come from the diagram with two or more sets, as we saw). The limit is always the universal set, along with functions to all of the sets you started with, so that any other set and functions are uniquely determined by a mapping from that set into the universal set. The idea then just pops out of which diagram you start with.

Let’s look at another example, though it’s a bit of an odd one. Let’s take an empty diagram, with no sets and functions at all. Then the limit of this diagram is just some set U, such that for any other set S, there is a unique function h : S → U.

Sound familiar? That was the answer to the first question in our game where we described sets with one element. That answer, as well, is just the limit, this time of the empty diagram!

So far, the diagrams we’ve looked at had only sets, and not functions. There’s another wrinkle in the picture if you want to construct the limit of a diagram with a function. Here’s a diagram with two sets A and B and a function f, as well as the universal object U and functions p and q that form the limit of this diagram.

The rule says that when you compose a function into the diagram (say, p) with a function in the diagram itself (say, f), you have to get the same thing as the function into the diagram that points to the same place. So f ∘ p = q. In category theory, this is sometimes expressed by saying it “commutes”, which is just a fancy word that means it doesn’t matter which path you take, because you get the same function in the end.

In this case, that means q is completely determined by p and f, so we don’t need to think about it at all! In fact, this ends up meaning we don’t need to think about B or f either, and the limit here is the same as a diagram with just A: any set with the same cardinality as A, where p is a specific one-to-one correspondence that witnesses this. So this wasn’t an interesting example. But there are interesting limits with functions, and we’re about to see one.

Dynamical systems appear!

If we’re thinking of simple diagrams to work out limits for, what about this one?

The diagram has a single object A, and a single function f from A to itself. One of the smallest diagrams we can think of. What could its limit be?

We can just follow the same process, and end up with this statement: “U is some set, together with a function g : U → A, where f ∘ g = g. Additionally, for any other set S and function k : S → A where f ∘ k = k, there is a unique function h : S → U so that g ∘ h = k.”

But what does that really mean? We can puzzle it out.

• f ∘ g = g means that f doesn’t change anything in the result of g. In other words, for any x in the result of g, we must have f(x) = x. There’s a word for values that are unchanged by a function: fixed points (or sometimes fixpoints, or stationary points). So g can only point to the fixed points of f.
• By the same logic, any choice of k can only point to the fixed points of f. But it’s possible to choose a k that points to any fixed point of A.
• That h exists, then, means that g must map some element of U to every fixed point of f. (If it didn’t, then k might map something to that fixed point, and it couldn’t be obtained by composing with g.)
• That h is unique means that g maps only one thing to each fixed point of f. (Otherwise, there would be a choice of where h should map some things, so h wouldn’t be unique.)

So U is in one-to-one correspondence with the fixed points of f, and g is that one-to-one correspondence. Essentially (up to isomorphism) the limit of this diagram is the fixed points of f.

Fixed points are a fundamental idea that pops up all over the place. I’ve written about their role in denotational semantics of programming languages before. So I find it delightful that they jump out of such a simple diagram. At the same time, though, it’s not surprising that they jump out of this diagram, which is the one that really expresses the essence of a discrete dynamical system: a set (the phase space), together with a function from that set to itself that defines a dynamics on that phase space.

Reversing course: colimits

One famous thing about category theory that everything has a dual, obtained by just reversing the directions of all the arrows. In this case, we can convert the definition of a limit into a different definition: the colimit. This looks just like the limit, but reverses the direction of the arrows.

As a warm-up, let’s consider the diagram with just two sets. Recall that the limit of this diagram was the cartesian product of those two sets. (More specifically, it was the cartesian product, along with the two projection functions that explained how to interpret each element as an ordered pair.)

The same diagram can be used with arrows reversed to find a colimit.

The formal definition is this: The colimit of the diagram is a set A + B, together with functions p : A → A + B and q : B → A + B, such that for every other set S and functions f : A → S and g : B → S, there is a unique function h : A + B → S so that f = h ∘ p and g = h ∘ q.

Let’s unpack what that means, now. First of all, everything in A maps to something in A + B, and likewise, everything in B maps to something in A + B. (We would usually call p and q injections now instead of projections.) But that’s not the whole picture, because we also have to look at h.

• The existence of h means that no two elements of A or B map to the same element of A + B. If they did, then we could find an f and g that map them somewhere different, and then we couldn’t write that f and g as compositions with h.
• The uniqueness of h means that there’s nothing else in A + B except these elements that are mapped from A and B. If there were, then there would be a choice of where h maps those extra elements.

If you’re familiar with basic ideas about sets, you might want to say that A + B is the union of A and B. But that’s not quite right, because if A and B have elements in common, A + B still needs to contain an element for each one (because f and g could map that same value to different elements of some S.) So it’s actually called the disjoint union. It’s a set that contains a copy of everything in A and everything in B, keeping two copies if A and B have elements in common.

In some sense, both the limit and the colimit of this diagram are about combining the elements of A and B, but they just combine them in different ways: the limit with a cartesian product that describes ways to choose one element from each, and the colimit with the disjoint union that describes ways to choose one elements from either one. In general, even though it was this time, the limit isn’t necessarily different from the colimit. For example, diagram with just one set has the same limit and colimit: both of them are just a set and a one-to-one correspondence between that set and the original set.

Colimits and dynamical systems

Let’s return to the earlier diagram of a dynamical system:

It’s now natural to ask what the colimit would be for this diagram. So let’s work that out with this picture.

Here’s what the definition of the colimit works out to this time: A colimit of this diagram is a set U together with a function k : A → U for which k = k ∘ f. Furthermore, for any other set S and function g : A → S where g = g ∘ f, there is a unique function h : U → S such that g = h ∘ k.

Let’s break down the meaning one piece at a time.

• First, k = k ∘ f. What this tells us is that for any x in A, k(f(x)) = k(x). But that’s true for anything at all in A, including f(x), and f(f(x)) and so on, so we can write a chain of equalities: k(x) = k(f(x)) = k(f(f(x))) = k(f(f(f(x)))) = …, forever and ever. This brings us to another idea in dynamical systems: the orbit. An orbit (or sometimes trajectory) is a set of values that eventually map to the same things when iterating the transition function. So this says that k maps everything in the same orbit of f to the same result. (So do all valid choices of g, which has the same condition.)
• The existence of h tells us that k maps distinct orbits of f to different places. (Otherwise, if g mapped them to different places, then g couldn’t be written as a composition with k.)
• The uniqueness of h tells us that there’s nothing else in U other than one element for each orbit of f. (Otherwise, h would have a choice where to map these extra elements, so it wouldn’t be unique.)

Summing it all up, U is effectively the set of all orbits of the function f. An orbit can be thought of an an “eventual” behavior of f when applied over and over if you just ignore differences at the beginning of the process. In fact, a fixed point is one type of orbit! If x is a fixed point of f, then anything that ever reaches x will stay there forever since applying f more often doesn’t change the value. But it’s not the only kind of orbit. You can also have a longer cycle of repeating values. Or, despite what the name implies, an orbit need not be cyclic at all. For example, the function f(n) = n + 1 on the natural numbers has only one orbit: the one that counts off toward positive infinity increasing one number at a time.

Orbits come up all the time when one looks at iterated functions. The famous Collatz conjecture, for example, is just the statement that the function f on the positive integers defined by

has only one orbit. If the Collatz conjecture is true, then that one orbit cycles through the sequence 4, 2, 1, 4, 2, 1, … forever, and every possible starting point eventually ends up in that cycle. If the Collatz conjecture is false, then there is some other orbit, whether it’s another cycle or a sequence that ends up growing larger and larger forever.

Just like disjoint unions and cartesian products were two different takes on combining two sets, fixed points and orbits are related but different takes on understanding the eventual behaviors of a dynamical system. One is the limit, and one is the colimit, but both start from the same simple diagram.

What’s next?

This was just one example of a fundamental idea from a branch of mathematics that just pops out of a very abstract and general construction, fully defined as if by magic. Even though the diagram involved is trivial, I haven’t actually seen this mentioned in standard lists of examples of limits and colimits in textbooks! This is surprising, but I’m also glad, because I think I’d find this a little less exciting if it had just been example 2 in a textbook.

• I would strongly encourage you to explore limits and colimits on your own by considering other simple diagrams you can draw, and checking whether there’s some natural characterization of the limit and colimit.
• I’ve also stuck to sets and functions in this article, but the “game” where we didn’t talk about elements or membership did have a point. When you play that game with sets, you get an alternative kind of set theory for mathematics called the “Elementary Theory of the Category of Sets”, or ETCS for short. In the traditional ZF set theory, you assume there’s some notion of membership, and then work to build up ordered pairs, then relations, then functions. But in ETCS, you assume there’s a notion of functions, and work backward to recover ordered pairs and such. You can even recover an idea analogous to set membership: an element of a set is analogous to a function from some other one-element set, which we defined without reference to elements, into that set.
• But because there was no direct reference to elements, the same definitions work in any other category; that is, a collection of things and arrows between them that compose in a manner like function composition. You can, for example, consider any algebraic structure (groups, rings, etc.) and the homomorphisms between them, or topological spaces and continuous functions between them, or even fundamentally non-function-like things such as partial orders (or any other reflexive transitive relation).
• Although the same definitions work for any category, but they can mean very different things, and they may or may not even exist. One example: if you work out what sums and products of two things (that just means the colimit and limit of a diagram with two objects and no arrows) look like for the category of abelian groups, you’ll discover that they are the same thing! Both correspond to a notion that’s usually called a direct sum or direct product, which are the same thing for any finite number of groups. That’s very different from sets, where one was the cartesian product and the other the disjoint union.

Please do play around with your own diagrams, your own categories, and so on, and see where it takes you. If you find another interesting limit or colimit that isn’t a common example, please comment and let me know about it.