Recently in Measure Theory we needed the following lemma.
Lemma: Let be non-constant, right-continuous and non-decreasing, and let . Define by . Then is left-continuous and non-decreasing. Moreover, for and ,
.
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 if and only if there exists a morphism from to . 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 such that for every there exists exactly one morphism . 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 of two objects in a category, if it exists, is an object equipped with two morphisms such that for any object and pair of morphisms , there is a unique morphism making the obvious diagram (seen in the Wikipedia article) commute. In other words, it is universal among objects which map into both and . (Another way to say this is to define a category of objects equipped with pairs of maps to and , 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 of two elements is the greatest element satisfying and ; 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 . (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 is regarded as a poset in the usual way, then a function 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: is defined by the universal property that if and only if for all , and similarly is defined by the universal property that if and only if for all .
The Yoneda lemma for posets boils down to the statement that if and only if, whenever , it is also true that . In particular, if and only if . This recently came up on MO.
Let be two posets. A pair of order-preserving maps (functors) and are adjoint if there is a natural bijection
.
Since both sides are either empty or non-empty depending on whether or not or , this reduces to the statement that
.
This is precisely the condition we wanted in the lemma! (In poset-theoretic terms, form a monotone Galois connection.) One way to verify that we are on the right track is that a pair of adjoint functors is known to have the property that preserves limits (is right-continuous) and preserves colimits (is left-continuous), which also figure in the lemma. So we now know that being right-continuous is a prerequisite for to exist.
The question, therefore, is whether it is the only prerequisite. That is, suppose is an order-preserving function (i.e. a functor) between posets such that has, and preserves, infima (i.e. small limits). Does it necessarily have a left adjoint ? And the answer, by the adjoint functor theorem for posets, is yes.
Proof of the theorem
Given we want to define so that . The condition that is right-continuous in , so if for a collection , then . It follows that, in fact, must be equal to . That this choice works follows by the fact that is right-continuous.
Now, if then , hence . By the Yoneda lemma, it follows that , hence is order-preserving. Finally, if is a collection with supremum , then , hence , so again by the Yoneda lemma it follows that is left-continuous.
To prove the original lemma we need to extend 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 such that has, and preserves, small limits. But during the proof we took a limit, not in , 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 embeds into the poset of subsets of via the embedding which sends to . (This is precisely the set of such that is non-empty, and hence completely characterizes the contravariant functor 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 , 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 into the category of functors . But this category is itself a poset, and in fact it’s isomorphic to the poset of downward-closed subsets of in a pretty natural way (take the preimage of .)
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 with the usual order, one will get none other than (the two-point compactification of) the real numbers ! This is called the Dedekind completion of a poset, and it generalizes the construction of from by Dedekind cuts. (Again, who said category theory isn’t useful in analysis?)
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 has, and preserves, small limits. This implies that is a complete lattice (by the adjoint functor theorem!) but in principle needn’t be, although in practice it probably will be.
Ok thanks
[…] 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 […]
@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 .
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.