Posets inside of categories

Posted byJoe MoellerPosted inCategory Theory, Math, SystemsTags:, , , , , ,

A poset can be thought of as a category with the property that each hom-set is either empty or singleton (technically that’s a preorder, but I’ll skip that for now). There’s also a category of posets. In my work lately, I’ve actually wanted to point at an object in a category and say “this one is a poset”. This doesn’t make complete sense in the most direct interpretation: objects in categories are not necessarily sets, so what would it mean to partially order it’s elements? I’ll tell you about two different ways to answer this, their relationship, and then ask a question.

Internal Posets

The first one I’ll tell you about is not the first one I used, even though in retrospect it seems like the more obvious one to reach for.

Definition: Let \mathcal C be a category with finite products. An internal poset is an object R equipped with a bunch of extra data:

  • another object P which I’ll call the “relation object”, and a monic map (s,t) \colon P \to R \times R (in the case of ordinary posets, this is the set of pairs (f,g) such that f \leq g)
  • a map \rho \colon R \to P (this captures the reflexive property)
  • a map \tau \colon P \times_R P \to P making some diagram commute (P \times_R P is like the set of triples such that f \leq g \leq h, so this corresponds to transitivity)
  • a monic map \alpha \colon P \times_R P^{op}\to R (this captures antisymmetry)

This definition can feel strange because everything in the original definition of poset becomes a piece of data: reflexivity, transitivity, and antisymmetry are now represented by maps instead of properties, and these maps satisfy properties.

You should have noticed that I only asked the category to have finite products, but I referred to pullbacks in the definition. For an object to carry an internal poset structure, these pullbacks in particular must exist. I did it this way instead of asking for all finite limits because I want to include the category of manifolds. Man has finite products, but only certain pullbacks exist.

Posetal Objects

Definition: Let \mathcal C be a category. A posetal object is an object R \in \mathcal C equipped with a partial order on each hom-set \mathcal C(X,R) such that precomposing is order-preserving.

I’m borrowing the term “posetal object” from Ross Street’s “Fibrations in bicategories”. There, it actually says that an object in a bicategory is posetal if all hom-categories \mathcal C(X,R) are posets. So it’s the same idea, but top-down instead of bottom-up.

This notion of poset in a category is the one I actually used in my recent papers on Lyapunov Stability:

The idea with this one is that if you’re looking at a category and an order on an object, maybe what you’re really trying to do is order maps that land in that object. That is exactly what I wanted to do: my internal semi-metrics and Lyapunov morphisms took values in a fixed object, and I wanted to be able to compare these and compose them with other maps and compare.

How are they related?

A natural question is whether these two definitions are equivalent. It’s not impossible for an internal and an external definition to pick out the same data. I told you about how this happens with monoids in Delooping, and internalization vs enrichment. I believe in this case, we do not get an equivalence, but an inclusion. Specifically, internal posets induce posetal structures, but only certain posetal structures are induced in this way.

Given an internal poset structure on R, define a posetal structure on R as follows. Say a pair of maps f_1, f_2 \colon X \to R satisfy f_1 \leq f_2 if the pairing (f_1, f_2) \colon X \to R \times R factors uniquely through (s,t). I’ll leave it to you to check that this defines a poset on \mathcal C(X,R) and that all those posets together form a posetal structure.

Here’s another way of constructing this. Notice two things: that the definition of internal poset only involves talking about finite limits, and that limits can always be pulled out of the second slot of a hom, e.g. \mathcal C(-,X \times Y) \cong \mathcal C(-,X) \times \mathcal C(-,Y). Together, these things tell us that if you have an internal poset on R with relation object P, then you automatically get a poset internal to \mathcal C-presheaves with base object \mathcal C(-,R) and relation object \mathcal C(-,P). All the structure maps are those induced by the corresponding structure maps on R via postcomposition.

Now with an internal poset structure on \mathcal C(-,R) in presheaves, each component \mathcal C(X,R) gets a poset structure internal to Set, so just an ordinary poset.

Claim: A posetal object is induced by an internal poset if and only if it is representable.

I didn’t tell you what it means for a posetal object to be representable, but maybe you can guess from the discussion above.

Definition: a posetal object R is called representable if the functor \mathcal C \to \mathsf{Set} given by

X \mapsto \{(f,g) \in \mathcal C(X,R) \times \mathcal C(X,R) \mid f \leq g\}

is representable.

One direction of the claim admits a short proof thanks to the Yoneda lemma. If a posetal object is representable, then there exists an object P such that \mathcal C(X,P) \cong \{(f,g) \in \mathcal C(X,R) \times \mathcal C(X,R) \mid f \leq g\}. So we have an obvious inclusion map \mathcal C(X,P) \to \mathcal C(X,R) \times \mathcal C(X,R) \cong \mathcal C(X,R \times R). The Yoneda lemma tells us this corresponds to a map on the representing objects P \to R \times R, and this is the relation that defines the internal poset structure on R.

The other direction is routine: assume a posetal structure is induced by an internal poset, define a map \mathcal C(X,P) \to F(X), show it’s a bijection and natural in X.

Questions

Great, so a posetal object comes from an internal poset structure on the object if and only if it’s representable. If all posetal objects are representable, we have an equivalence. If there are any posetal objects that are not representable, then it’s a one-way inclusion, and posetal objects are strictly more general than internal posets.

Can you put an order on all the maps into an object without putting an order on the object? If your category has a separating terminal object, then \mathcal C(1,R) determines what happens on all other hom-sets into R. So in that case, we get an equivalence. Are there any categories where we can find a non-representable posetal object? Maybe something like schemes where objects are not simply determined by their points. Let me know what you think!

A different question: can any parts of this story be told in a slicker way? Every element of this is basic category theory, so it feels like there is a lot of room for tweaking stuff to be a special case of some other stuff. One thing that jumps out to me is that the theory of internal posets is a (multisorted) finite limit theory. Really nothing about what I said should really change for a different limit theory. For a limit theory \mathcal T, let’s say a “homly model” of \mathcal T is an object R with a \mathcal T-model on each hom-set into R such that precomposition is a model homomorphism. Then ordinary models turn into homly models by following the same recipe as above. I just don’t currently have a use for another limit theory. Surely someone thought about this before?

Published by Joe Moeller

Mathematician

2 thoughts on “Posets inside of categories”

  1. I don’t follow your argument that a separating terminal object implies that all posetal objects are representable: how do you produce the object $P$?

    Note that if you generalize from posets to preorders, then even Set contains non-representable preorder objects. For instance, let $R=P(mathbb{N})$ be the powerset of the set of natural numbers, and for $f,g : X to R$ define $fle g$ to mean that there exists a computable function $varphi : mathbb{N} to mathbb{N}$ such that $forall x, forall nin f(x), varphi(n) in g(x)$. (This is the ur-example of a tripos, which gives rise to the effective topos.)

    (Also I think you mean “presheaves”, not “copresheaves”.)

    Like

    Reply

    1. Thanks for the comment!

      Let’s see, why did I think that? I’ve been using separable terminal object whenever I want to talk about this posetal stuff in concrete categories. I keep making this error where I think that if the category is concrete then the posetal structure has to be point-wise induced, and “point-wise induced” is very close to “induced by an internal poset”. But that’s sorta the whole point of this blog post, so not a good time to make this error!

      Your example is interesting to me as I just started getting into computability recently. I can’t immediately see the point of that ordering though.

      That “co/presheaves” error is one of those ones where I can’t even put myself in my own mind from a few hours ago to figure out why I would make it.

      Like

      Reply

Leave a reply to Joe Moeller Cancel reply