Closure Operators and Monads

The primary difficulty in learning category theory is the need for lots of good examples; more than anything else in math, category theory is tremendously abstract, and without building intuition from examples, it’s just a bunch of arrows and dots. Besides familiar examples, like those from set theory, algebra and topology, it’s often helpful to look at minimal examples—examples which show the categorical structure, with as little “residual” structure as possible.

A wonderful source of minimal examples is order theory—since there is at most one arrow between any two objects in a preorder category, all diagrams commute in a preorder. As a result, we get to see what happens to categories (and functors) without worrying whether the morphisms in question behave nicely. But I’m getting ahead of myself—let’s look at some basic order theory from the classical perspective, and then see how it translates to category theory.

A preorder \leq on a set S is a reflexive, transitive relation. That is, for all x\in S, we have x\leq x and for all x,y,z\in S such that x\leq y and y\leq z, we have x\leq z. Observe that a preorder is not necessarily anti-symmetric: we can have x\leq y and y\leq x without having x=y. Since x\leq y \wedge y\leq x is clearly an equivalence relation, we can quotient a pre-order to arrive at a relation which is additionally anti-symmetric: if x\leq y and y\leq x, then x=y.

A (weak) partial order on a set is a reflexive, transitive, anti-symmetric relation (and a set with a partial order is called a poset). Partial orders show up basically everywhere, and I assume if you’ve read this far you already know what they are, so I won’t bore you with examples, but of course many of the most important examples are collections of sets, where the ordering relation is \subseteq. Importantly, in many of these typical examples, we will take the closure of some element with respect to some ambient structure–e.g. the closure of a subspace, or the generated subalgebra (which is “closed” under the algebraic operations in question). These closure operators all have three important properties:

  • They are monotone: if x\subseteq y then \overline{x}\subseteq \overline{y}).

  • They are extensive: x\subseteq \overline{x}.

  • They are idempotent: We always have \overline{\overline{x}}=\overline{x}. In English, the closure of a closed set is closed.

Abstracting to a general partial order, we have that a closure operator C on a poset P is a function C:P\rightarrow P which is monotone, extensive, and idempotent; we call x\in P closed when x=C(x) (equivalently, when x=C(y) for some y). If the underlying poset is \mathcal{P}(X) for some set X, we usually call it a closure operator on X. The most common (explicit) examples of closure operators come from algebra: given, say, a group (in fact, any algebraic structure will do) G, the subsets of G form a poset under \subseteq. It’s easy to see that the operation C taking a subset X\subseteq G to its generated subalgebra \langle X\rangle is a closure operator.

Let’s focus in on this group example: the subgroup generated by X is the set of all elements x_1\cdot x_2\cdot\ldots\cdot x_n\in G, for some natural number n, where each x_i is either in X, or is x^{-1} for some x\in X. In particular, each element of \langle X\rangle can be represented by some finite number of elements of X. That is, each x\in\langle X\rangle is in some \langle X'\rangle where X' is a finite subset of X. In other words, we have for all X\subseteq G

\langle X\rangle = \bigcup\{\langle X'\rangle \mid X'\subseteq X\text{ is finite}\} (*)

A closure operator C on a set S (i.e., on the powerset lattice) is called finitary or algebraic when this happens—that is, when (*) is satisfied by all subsets of S. It might be interesting to generalize this to an arbitrary poset, but I won’t do that here.

Ok. Time to look at all this from a categorical perspective. The first point is that from any pre-order P we can define a category: We take as objects the elements of P, and when x\le y, we have a unique arrow x\rightarrow y. The arrow is usually left unnamed, since there’s at most one for any pair of objects. Reflexivity ensures the existence of id_x (as the unique arrow x\rightarrow x), while transitivity ensures composites (where (x\rightarrow y)\circ (y\rightarrow z) is the unique arrow guaranteed by x\le z.) Categories with at most one arrow between any pair of objects are called, naturally enough, poset categories.

Fact: Any diagram which we can draw in a poset commutes, since any parallel arrows are equal.

A category is skeletal when isomorphic objects are equal. A skeletal precategory is a poset—That is, if P is a preorder, and whenever there are arrows x\rightarrow y and y\rightarrow x, then x=y. (Exercise: anti-parallel arrows are mutually inverse in any pre-order.)

Finally, some motivation for this whole post: one of the takeaways from a first course in (classical) universal algebra is that algebraic structures and closure operators give the same information—every (algebraic) closure operator (on a powerset lattice) gives rise to an algebraic structure, and vice versa. It’s well-known that monads capture the notion of algebra in a categorical way, and finitary monads correspond precisely to algebraic theories. So, there should be some close relationship between closure operators and monads. Besides the obvious one via algebraic theories, there’s another one:

A monad on a poset is precisely a closure operator. This result is pretty fundamental, and it shows up in just about every category theory book, but somehow I missed it until pretty recently. (I’m new at this!)

A monad on a category C is a functor T:C\rightarrow C together with natural transformations \eta:1_C\Rightarrow T and \mu:T\circ T\Rightarrow T satisfying certain diagrams—since we’ll be dealing only with posets, we don’t care what these diagrams are.

Let’s see how this plays out on a poset C:

  • T:C\rightarrow C is a functor: we must have x\le y implies T(x)\rightarrow T(y). That is, T is monotone
  • There is a natural transformation \eta: 1_C\Rightarrow T. Such a natural transformation is given by an arrow x\rightarrow T(x) for all x\in C. That is, for all x\in C we have x\le T(x). That is, T is extensive.
  • There is a natural transformation \mu:T\circ T\Rightarrow T. As in the last point, this becomes for all x\in X we have T(T(x))\le T(x). That is, T is idempotent.

So, there we have it: a monad is precisely a closure operator. But we’re not done yet: an algebra for a monad T on C is an object x\in C together with an arrow T(x)\rightarrow x satisfying diagrams (that we again don’t care about). That is, in a poset, an algebra for a monad T is an element with T(x)\le x—a closed element!

My original plan was to finish this off with some discussion of finitary monads, but I think what’s here is enough for now. Perhaps another time I’ll get back to it.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s