Feeds:
Posts

It’s common to think of monads as generalized algebraic theories; the most familiar examples, such as the monads on $\text{Set}$ encoding groups, rings, and so forth, have this flavor. However, this intuition is really only appropriate for certain monads (e.g. finitary monads on $\text{Set}$, which are the same thing as Lawvere theories).

It’s also common to think of monads as generalized monoids; previously we discussed why this was a reasonable thing to do.

Today we’ll discuss a different intuition: monads are (loosely) categorifications of idempotents.

## The categorical exponential formula

Yesterday I described the answer to the puzzle of what the generating function

$\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots$

counts by sketching a proof of the following more general identity: if $G$ is a finitely generated group and $a_n$ is the number of subgroups of $G$ of index $n$, then

$\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right)$.

The main ingredient is the exponential formula, but the discussion of the proof involved some careful juggling to make sure we weren’t inappropriately quotienting out by various symmetries, and one might find this conceptually unsatisfying. The goal of today’s post is to state a categorical result which describes exactly how to juggle these symmetries and gives a conceptually clean proof of the above identity.

The key is to describe in exactly what sense a finite $G$-set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive $G$-sets (corresponding to the RHS), which is the following.

Claim: The symmetric monoidal groupoid of finite $G$-sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite $G$-sets.

From here, we’ll use a version of the exponential formula that comes from relating (weighted) groupoid cardinalities of a groupoid and of the free symmetric monoidal groupoid on it.

## Dualizable objects (and morphisms)

Let $R$ be a ring. Previously we characterized the finitely presented projective (right) $R$-modules as the tiny objects in $\text{Mod}(R)$: the objects $P$ such that

$\displaystyle \text{Hom}(P, -) : \text{Mod}(R) \to \text{Ab}$

preserves colimits. We also highlighted the key role that these modules play in Morita theory.

If $k$ is a commutative ring, then $\text{Mod}(k)$ has a natural symmetric monoidal structure which allows us to describe another finiteness condition called dualizability. Unlike tininess, dualizability makes no reference to colimits; instead, it is a purely equational definition involving the monoidal structure. The dualizable modules are again the finitely presented projective $k$-modules.

Dualizability implies that we can treat finitely presented projective $k$-modules like finite-dimensional vector spaces in many ways: for example, dualizability allows us to define the trace of an endomorphism. Moreover, since dualizability is defined using only a monoidal structure, it makes sense in very general settings, and we’ll look at some more exotic examples of dualizable objects as well.

Duals are also a special case of a 2-categorical notion of adjunction which, in the 2-category of categories, functors, and natural transformations, reproduces the usual notion of adjunction. In a suitable 2-category it will also reproduce another characterization of finitely presented projective modules, this time over noncommutative rings.

This post should, but will not, include diagrams, so pretend that I’ve inserted some string diagrams or globular diagrams where appropriate.

## The free cocompletion I

Let $C$ be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

$\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}$

into its presheaf category $\widehat{C} = [C^{op}, \text{Set}]$ (where we use $[C, D]$ to denote the category of functors $C \to D$). The Yoneda lemma asserts in particular that $Y$ is full and faithful, which justifies calling it an embedding.

When $C$ is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding $Y : C \to \widehat{C}$ exhibits $\widehat{C}$ as the free cocompletion of $C$ in the sense that for any cocomplete category $D$, the restriction functor

$\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]$

from the category of cocontinuous functors $\widehat{C} \to D$ to the category of functors $C \to D$ is an equivalence. In particular, any functor $C \to D$ extends (uniquely, up to natural isomorphism) to a cocontinuous functor $\widehat{C} \to D$, and all cocontinuous functors $\widehat{C} \to D$ arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that $\widehat{C}$ is the category obtained by “freely gluing together” the objects of $C$ in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

## Cartesian closed categories and the Lawvere fixed point theorem

Previously we saw that Cantor’s theorem, the halting problem, and Russell’s paradox all employ the same diagonalization argument, which takes the following form. Let $X$ be a set and let

$\displaystyle f : X \times X \to 2$

be a function. Then we can write down a function $g : X \to 2$ such that $g(x) \neq f(x, x)$. If we curry $f$ to obtain a function

$\displaystyle \text{curry}(f) : X \to 2^X$

it now follows that there cannot exist $x \in X$ such that $\text{curry}(f)(x) = g$, since $\text{curry}(f)(x)(x) = f(x, x) \neq g(x)$.

Currying is a fundamental notion. In mathematics, it is constantly implicitly used to talk about function spaces. In computer science, it is how some programming languages like Haskell describe functions which take multiple arguments: such a function is modeled as taking one argument and returning a function which takes further arguments. In type theory, it reproduces function types. In logic, it reproduces material implication.

Today we will discuss the appropriate categorical setting for understanding currying, namely that of cartesian closed categories. As an application of the formalism, we will prove the Lawvere fixed point theorem, which generalizes the argument behind Cantor’s theorem to cartesian closed categories.

## Operations, pro-objects, and Grothendieck’s Galois theory

Previously we looked at several examples of $n$-ary operations on concrete categories $(C, U)$. In every example except two, $U$ was a representable functor and $C$ had finite coproducts, which made determining the $n$-ary operations straightforward using the Yoneda lemma. The two examples where $U$ was not representable were commutative Banach algebras and commutative C*-algebras, and it is possible to construct many others. Without representability we can’t apply the Yoneda lemma, so it’s unclear how to determine the operations in these cases.

However, for both commutative Banach algebras and commutative C*-algebras, and in many other cases, there is a sense in which a sequence of objects approximates what the representing object of $U$ “ought” to be, except that it does not quite exist in the category $C$ itself. These objects will turn out to define a pro-object in $C$, and when $U$ is pro-representable in the sense that it’s described by a pro-object, we’ll attempt to describe $n$-ary operations $U^n \to U$ in terms of the pro-representing object.

The machinery developed here is relevant to understanding Grothendieck’s version of Galois theory, which among other things leads to the notion of étale fundamental group; we will briefly discuss this.

Groups are in particular sets equipped with two operations: a binary operation (the group operation) $(x_1, x_2) \mapsto x_1 x_2$ and a unary operation (inverse) $x_1 \mapsto x_1^{-1}$. Using these two operations, we can build up many other operations, such as the ternary operation $(x_1, x_2, x_3) \mapsto x_1^2 x_2^{-1} x_3 x_1$, and the axioms governing groups become rules for deciding when two expressions describe the same operation (see, for example, this previous post).
When we think of groups as objects of the category $\text{Grp}$, where do these operations go? They’re certainly not morphisms in the corresponding categories: instead, the morphisms are supposed to preserve these operations. But can we recover the operations themselves?
It turns out that the answer is yes. The rest of this post will describe a general categorical definition of $n$-ary operation and meander through some interesting examples. After discussing the general notion of a Lawvere theory, we will then prove a reconstruction theorem and then make a few additional comments.