Feeds:
Posts

## The adjoint functor theorem for posets

Recently in Measure Theory we needed the following lemma.

Lemma: Let $g : \mathbb{R} \to \mathbb{R}$ be non-constant, right-continuous and non-decreasing, and let $I = (g(-\infty), g(\infty))$. Define $f : I \to \mathbb{R}$ by $f(x) = \text{inf} \{ y \in \mathbb{R} : x \le g(y) \}$. Then $f$ is left-continuous and non-decreasing. Moreover, for $x \in I$ and $y \in \mathbb{R}$,

$f(x) \le y \Leftrightarrow x \le g(y)$.

If you’re categorically minded, this last condition should remind you of the definition of a pair of adjoint functors. In fact it is possible to interpret the above lemma this way; it is a special case of the adjoint functor theorem for posets. Today I’d like to briefly explain this. (And who said category theory isn’t useful in analysis?)

The usual caveats regarding someone who’s never studied category talking about it apply. I welcome any corrections.

Posets as small categories

A poset can be thought of as a (small) category in which any two objects have either zero or one morphisms between them and in which isomorphic objects are equal. The convention we’ll take in this post is that $x \le y$ if and only if there exists a morphism from $x$ to $y$. This agrees with the obvious notion of morphism between two subsets of a set, which is inclusion. The non-evil version of a poset is a preorder, in which we remove the last condition. Note that one gets the two axioms defining a preorder automatically from the existence of identity morphisms and from composition, and that the skeleton of a preorder is a partial order. The opposite category of a poset is the poset in which the order relation has been reversed, and a functor between two posets is precisely an order-preserving map. These define the morphisms in the category of posets.

General constructions from category theory tend to specialize to well-known general constructions in poset theory. For example, a terminal object in a category, if it exists, is an object $T$ such that for every $X$ there exists exactly one morphism $X \to T$. In a poset, a terminal object is an object which is greater than or equal to every other object; in other words, it’s a greatest element. Dually, an initial object is a least element.

Similarly, a product $X_1 \times X_2$ of two objects in a category, if it exists, is an object $X$ equipped with two morphisms $\pi_1 : X \to X_1, \pi_2 : X \to X_2$ such that for any object $Y$ and pair of morphisms $f_1 : Y \to X_1, f_2 : Y \to X_2$, there is a unique morphism $f : Y \to X$ making the obvious diagram (seen in the Wikipedia article) commute. In other words, it is universal among objects which map into both $X_1$ and $X_2$. (Another way to say this is to define a category of objects equipped with pairs of maps to $X_1$ and $X_2$, where the morphisms are maps making the obvious diagram commute. Then a product is a terminal object in this category.) In a poset, a product $X$ of two elements is the greatest element satisfying $X \le X_1$ and $X \le X_2$; in other words, it’s equal to their meet, if it exists. Dually, a coproduct of two objects in a poset is their join, if it exists.

More generally, the limit of a collection of objects is their infimum, and the colimit of a collection of objects is their supremum. (In order for these notions to be compatible with the fact that the empty limit is the terminal object and the empty colimit is the initial object, it is necessary to specify that the empty infimum is the greatest element and the empty supremum is the least element.) This is one way to motivate the term “limit” in category theory; it’s precisely the limit in the usual sense of a monotonically decreasing sequence (when it exists), say in $\mathbb{R}$. (Note that it’s not necessary to specify the diagram when working with a limit or colimit in a poset, since morphisms, when they exist, are automatically compatible.) This means that if $\mathbb{R}$ is regarded as a poset in the usual way, then a function $f : \mathbb{R} \to \mathbb{R}$ preserves limits if and only if it’s right-continuous, and preserves colimits if and only if it’s left-continuous.

Edit, 10/23: Let me mention that I think this is by far the best way to think about the infimum and supremum, and a good concrete example of how thinking categorically can elucidate concepts in undergraduate mathematics. In particular, what really matters about the infimum and supremum is that they have universal properties: $\inf y_n$ is defined by the universal property that $x \le \inf y_n$ if and only if $x \le y_n$ for all $n$, and similarly $\sup y_n$ is defined by the universal property that $\sup y_n \le x$ if and only if $y_n \le x$ for all $n$.

The Yoneda lemma for posets boils down to the statement that $x \le y$ if and only if, whenever $z \le x$, it is also true that $z \le y$. In particular, $x = y$ if and only if $z \le x \Leftrightarrow z \le y$. This recently came up on MO.

Let $P, Q$ be two posets. A pair of order-preserving maps (functors) $f: Q \to P$ and $g : P \to Q$ are adjoint if there is a natural bijection

$\text{Hom}_P(f(x), y) \simeq \text{Hom}_Q(x, g(y))$.

Since both sides are either empty or non-empty depending on whether or not $f(x) \le y$ or $x \le g(y)$, this reduces to the statement that

$f(x) \le y \Leftrightarrow x \le g(y)$.

This is precisely the condition we wanted in the lemma! (In poset-theoretic terms, $f, g$ form a monotone Galois connection.) One way to verify that we are on the right track is that a pair $f, g$ of adjoint functors is known to have the property that $g$ preserves limits (is right-continuous) and $f$ preserves colimits (is left-continuous), which also figure in the lemma. So we now know that $g$ being right-continuous is a prerequisite for $f$ to exist.

The question, therefore, is whether it is the only prerequisite. That is, suppose $g : P \to Q$ is an order-preserving function (i.e. a functor) between posets such that $P$ has, and $g$ preserves, infima (i.e. small limits). Does it necessarily have a left adjoint $f : Q \to P$? And the answer, by the adjoint functor theorem for posets, is yes.

Proof of the theorem

Given $x \in Q$ we want to define $f(x) \in P$ so that $f(x) \le y \Leftrightarrow x \le g(y)$. The condition that $f(x) \le y$ is right-continuous in $y$, so if $f(x) \le y_n$ for a collection $y_n$, then $f(x) \le \inf_n y_n$. It follows that, in fact, $f(x)$ must be equal to $\inf \{ y : x \le g(y) \}$. That this choice works follows by the fact that $g$ is right-continuous.

Now, if $x_1 \le x_2$ then $x_2 \le g(y) \Rightarrow x_1 \le g(y)$, hence $f(x_2) \le y \Rightarrow f(x_1) \le y$. By the Yoneda lemma, it follows that $f(x_1) \le f(x_2)$, hence $f$ is order-preserving. Finally, if $x_i$ is a collection with supremum $x$, then $f(x_i) \le y \Leftrightarrow x_i \le g(y)$, hence $x \le g(y) \Leftrightarrow f(x) \le y$, so again by the Yoneda lemma it follows that $f$ is left-continuous.

To prove the original lemma we need to extend $g : \mathbb{R} \to \mathbb{R}$ to a function on the two-point compactification to ensure that all infima actually exist, but this is a minor technicality.

Why doesn’t this always work?

Since all we did was take a lot of limits above, it might seem that the above argument generalizes to any functor $g : P \to Q$ such that $P$ has, and $g$ preserves, small limits. But during the proof we took a limit, not in $P$, but in a comma category. If the comma category isn’t small, then non-small limits might not exist in it. (In this particular case the comma category was a poset itself and we were fine.) So in general, we need more assumptions.

The Yoneda lemma

Some additional thoughts. The Yoneda embedding for posets can be interpreted as saying that a poset $P$ embeds into the poset of subsets of $P$ via the embedding which sends $x \in P$ to $\{ y \in P : y \le x \}$. (This is precisely the set of $y$ such that $\text{Hom}(y, x)$ is non-empty, and hence completely characterizes the contravariant functor $\text{Hom}(-, x) : P \to \text{Set}$ up to natural transformation.) This should be thought of as a representation theorem for posets, analogous to Cayley’s theorem for groups or Stone’s representation theorem for Boolean algebras; see also Todd Trimble’s thoughts.

Another way to give such an embedding is as follows. Since posets can be viewed as categories enriched over the category $\{ 0 \to 1 \}$, which is a (closed, symmetric) monoidal category with the categorical product, not only the regular Yoneda lemma but the enriched Yoneda lemma applies, which gives an embedding of a poset $P$ into the category of functors $P \to \{ 0 \to 1 \}$. But this category is itself a poset, and in fact it’s isomorphic to the poset of downward-closed subsets of $P$ in a pretty natural way (take the preimage of $0$.)

Now, the (enriched) Yoneda embedding is more than just any old embedding of a(n enriched) category into another (enriched) category; it’s also the free (enriched) cocompletion, which roughly means that it’s what happens when one adjoins all (weighted) colimits. I don’t really understand weighted colimits yet, but for posets it can’t mean anything other than suprema. If one adjoins suprema to the poset $\mathbb{Q}$ with the usual order, one will get none other than (the two-point compactification of) the real numbers $\mathbb{R}$! This is called the Dedekind completion of a poset, and it generalizes the construction of $\mathbb{R}$ from $\mathbb{Q}$ by Dedekind cuts. (Again, who said category theory isn’t useful in analysis?)

### 7 Responses

1. Dear Qiaochu,

Thanks for your blog posts. I’m a fan of your lucid writing style. I was wondering, doesn’t any of this (in particular the main theorem) assume that these posets are complete lattices?

• The hypotheses are stated in the post: I need that $P$ has, and $g$ preserves, small limits. This implies that $P$ is a complete lattice (by the adjoint functor theorem!) but in principle $Q$ needn’t be, although in practice it probably will be.

2. […] joins. Then is cartesian closed and hence a Heyting algebra. This is a consequence of the adjoint functor theorem for posets, and in particular implies that the lattice of open subsets of any topological space is a Heyting […]

3. @Qiaochu: The direct and inverse limit are constructions of Pontryagin from 1931, and yes, they were named for the abstract notion of a limit of a sequence of ordinals, not the more common topological notion .

4. I like your remark about motivation for the term “limit” in category theory. I wonder if (but doubt that) this is also the origin of the term.

By the way, just before the Proof you say “suppose f is an order-preserving function (e.g. a functor) between posets”.
Since a functor between posets is exactly an order-preserving function, I think you should replace “e.g.” by “i.e.”.

• I think the term comes from direct and inverse limits in algebra, which themselves behave something like ordinary limits. And yes, thank you; I get i.e. and e.g. mixed up sometimes.