An application of monadicity

Now we have seen the basic ideas of monadicity, and Beck’s monadicity theorem, it’s time to look at an important application. Although the result in question belongs to the area of topos theory, to avoid pulling in too much additional theory we will consider a concrete example, and then sketch how this extends to the abstract setting.

Subsets and the contravariant powerset

For our motivating example, we are going to consider the category \mathsf{Set} of sets and functions. The set

\{ \mathsf{true}, \mathsf{false} \}

which we shall denote 2 will play an important role. For any set X, a function \chi : X \rightarrow 2 corresponds to a subset of X:

\{ x \mid x \in X \;\text{and}\; \chi(x) = \mathsf{true} \}

and given any subset U \subseteq X, we can define a function:

x \mapsto \begin{cases} \mathsf{true} & \text{ if } x \in U \\ \mathsf{false} & \text{otherwise} \end{cases}

In this way, we can go back and forth between subsets and what are known as their characteristic functions. For a fixed set X, we can consider the set 2^X of characteristic functions of subsets of X. The mapping

X \mapsto 2^X

extends to a functor. For f : X \rightarrow Y we get a function in the opposite direction 2^f : 2^Y \rightarrow 2^X with action:

\chi \mapsto \chi \circ f

It is straightforward to check that this satisfies the functor axioms, so we have a functor:

2^{(-)} : \mathsf{Set}^{op} \rightarrow \mathsf{Set},

sometimes referred to as the contravariant powerset functor. This functor has a left adjoint, which we shall also denote

2^{(-)} : \mathsf{Set} \rightarrow \mathsf{Set}^{op}.

Notice the only difference here is whether we choose to put the “op” on the domain or codomain. Establishing that these two functors form an adjunction is straightforward, as we have natural bijections between:

  • Functions 2^X \rightarrow Y in \mathsf{Set}^{op}
  • Functions Y \rightarrow 2^X in \mathsf{Set}
  • Functions Y \times X \rightarrow 2 in \mathsf{Set}
  • Functions X \times Y \rightarrow 2 in \mathsf{Set}
  • Functions X \rightarrow 2^Y in \mathsf{Set}

We have seen a more abstract version of this proof before, as this is a special case of the adjunction that induces the continuation monad, in this case for the endofunctor:

2^{2^{(-)}} : \mathsf{Set} \rightarrow \mathsf{Set}

The perhaps surprising observation is that the functor

2^{(-)} : \mathsf{Set}^{op} \rightarrow \mathsf{Set}

is monadic, meaning the Eilenberg-Moore category of 2^{2^{(-)}} is equivalent to \mathsf{Set}^{op}. Put another way, \mathsf{Set}^{op} is monadic over \mathsf{Set}. Aside from being a rather startling fact, this gives a concrete description of the Eilenberg-Moore category of this special case of the continuation monad. Some duality theory tells us that the category of complete atomic Boolean algebras is equivalent to \mathsf{Set}^{op}, and this gives us an even more concrete description of the algebras of this monad.

Generalising

At first glance, the argument above looks very specific to the category of sets and functions. Fortunately, there is a very large class of categories that look sufficiently like the category of sets to carry out this argument in the abstract.

As a first step, we look at the important role of the set 2. It allowed us to connect subsets and characteristic functions. To generalise this, we first adopt a more categorical perspective, and consider subobjects rather than subsets. A subobject of object X, is isomorphism class of monomorphisms U \rightarrowtail X. Spelling this out a bit more, two monomorphisms m : U \rightarrowtail X and m' : U' \rightarrowtail X are isomorphic if there exists an isomorphism i : U \rightarrow U' such that m = m' \circ i.

A subobject classifier is a categorical abstraction of the correspondence between subsets (subobjects) and characteristic morphisms. Writing \mathsf{Sub}(X) for the collection of subobjects of X, a category \mathcal{C} with finite limits is said to have a subject classifier if and only if there is an object \Omega and natural isomorphism:

\mathsf{Sub}(X) \cong \mathcal{C}(X,\Omega)

There are several equivalent definitions of subobject classifiers. The typical statement involves a generic subobject and a pullback condition, but as we won’t delve into the details, the statement above emphasises the relationship between subobjects and classifying morphisms.

Example: The set 2 is the subobject classifier in \mathsf{Set}. Subobjects correspond to subsets which correspond to characteristic functions.

The class of categories that look sufficiently like the category of sets for our purposes are known as toposes. A topos is a finitely complete, Cartesian closed category with a subobject classifier. (There are almost as many equivalent definitions of a topos as there are books on the subject, depending on the perspective the author wishes to emphasize. We choose this one as it is reasonably straightforward.). There are many examples of toposes that crop up in mathematical practice.

Example: The category \mathsf{Set} is a topos, and in many ways the motivating example for the abstraction. The full subcategory of finite sets is also a topos.

Example: For any small category \mathcal{C}, the category of presheaves over \mathcal{C} is a topos. This is simply the category with objects functors \mathcal{C}^{op} \rightarrow \mathsf{Set} and morphisms natural transformations between them. This construction can be generalised greatly to various notions of categories of sheaves, but we avoid entering into what would be a sizeable technical detour.

For a topos \mathcal{C}, by analogy with the set theoretic situation, as we have exponentials and a subobject classifier, it is natural to consider the functor:

\Omega^{(-)} : \mathcal{C}^{op} \rightarrow \mathcal{C}

It is a non-trivial observation that this functor is monadic. As a concrete argument is no longer possible, this is typically established using a monadicity theorem. Interested readers that are prepared for a bit of topos theory can find the details in any good book on topos theory. Slightly confusingly, topos theorists also refer to this result as the (topos theoretic) monadicity theorem.

This result has an immediate pay-off. As a topos is finitely complete, \mathcal{C}^{op} is also finitely complete. In other words, \mathcal{C} is finitely cocomplete. Finite cocompleteness was actually included in the original definition of a topos, until it was shown that it followed from the other axioms. Monadicity is a particularly elegant way of establishing this fact.

Conclusion

Our discussion of topos theory has been deliberately somewhat sketchy, to avoid pulling in too many technical details. Topos theory is a vast subject, with connections to many parts of mathematics, and would probably warrant a blog of its own.

Further reading: Readers interested in filling in some of the topos theoretic technical details could look at one of the standard sources, such as volume 1 of Johnstone’s “Sketches of an Elephant”, Moerdijk and MacLane’s “Sheaves in Geometry and Logic” or volume 3 of Borceux’s “Handbook of Categorical Algebra”.

Leave a comment