Most of the previous posts have focussed on -monads and their algebraic presentations. This was done to avoid pulling in lots of abstract machinery, whilst allowing us to still build up good intuitions about what is going on.
Unfortunately, some phenomena only truly reveal themselves when we move away from the category of sets and functions. To develop our understanding, we need additional proving grounds for the ideas we discuss. In the current post, we shall beginning discussing monads on ordered structures. This is a baby step away from , where new possibilities emerge, but we still work with simple mathematical objects that are relatively easy to describe and visualise.
Basics of Posets and Preorders
Posets and preorders are two related mathematical structures that abstract the idea of an ordered collection of objects. A preorder consists of a set, which we shall also denote , and a reflexive, transitive binary relation on . That is, a relation satisfying both:
- Reflexivity: .
- Transitivity: and implies .
A poset is a preorder for which the relation is also irreflexive. That is:
Example: The set of natural numbers is a poset, with their usual ordering.
Example: For any set , the powerset is a poset, with the subset inclusion relation.
Example: For any set , the the finite powerset can be ordered with if the number of elements of is less than equal to the number of elements of . This gives the finite powerset of the structure of a preorder, but not a poset, as both and are finite subsets of with the same number of elements, but they are not equal.
A morphism of preorders or posets is a function such that:
Such functions are referred to a monotone. The categories of preorders and monotone maps, and partial orders and monotone maps will be denoted and respectively.
As well as considering the categories of preorders and posets, it is worth thinking about these objects as special sorts of categories themselves. From this perspective:
- A preorder is a category in which there is at most one morphism between a pair of objects. Such as category is sometimes described as being thin.
- A poset is a thin category in which the only isomorphisms are the identities.
(Strictly speaking we should say that preorders and posets are small categories, but we’ll steer clear of discussing size issues.)
Remark: The fact that preorders and posets are “baby” categories is a useful tool for studying category theory. Such examples are often introduced very early in introductory category theory courses, but are nevertheless powerful aides to understanding. If a categorical construction is proving hard to grasp in full generality, considering it on preorders will mean that any valid diagrams will automatically commute. This means that any equational axioms will be satisfied, once you’ve identified morphisms of the right type. Even simpler, if you consider the special case of posets, any structural isomorphisms, for example those that occur in the definition of a monoidal category, will collapse to being equalities, so again lots of things become trivial. These simplifications can remove a lot of distractions whilst playing around with unfamiliar constructions, or trying to tease out the correct abstraction of a phenomenon of interest.
Relatives of the Maybe Monad
Previously, we introduced the maybe monad on sets and functions. Recall the functor action maps a set to the set , with an extra element added. Concretely, this operation is the coproduct with (a choice of) terminal object, so up to isomorphism the monad action is the disjoint union:
If we think of this as a construction involving binary coproducts and terminal objects, we can define a maybe monad in any category where this structure exists. In the category the coproduct has underlying set , and order relation if and only if either:
- and and .
- and and .
That is, we just glue together the two components, and inherit the order from the two parts.
The terminal object in is also similar to that in . The underlying set is , and the order relation is the inevitable .
With these concrete constructions in place, on objects the maybe monad in simply adds an extra element to a poset, unrelated with respect to the elements of the original structure.
From a computational point of view, it is sometime useful to interpret an order relation on a structure as an information or approximation ordering. In this way, is interpreted as being less informative than .
If we adopt this point of view, the maybe monad is not entirely satisfactory when interpreting as computation failure or divergence. This should yield no information, and therefore be a minimal element, rather than simply incomparable with everything else.
This suggests considering a construction on poset with universe as before. The order relation extends that of the maybe monad with the additional relations:
for all . That is, is now placed at the bottom of the resulting structure. In fact, this yields a new monad on , often termed the lift monad. The name is derived from the idea that the original structure is lifted up above the new element. Notice how this additional construction doesn’t even make sense on mere sets, so the presence of order allows us to introduce new features – this will be a recurring theme.
Relatives of the List Monad
The list monad is such a standard example that we should investigate list like constructions in our new setting. For a set , we shall write for the set of lists of elements from .
For a poset , we would like to build a monad such that has underlying set . We shall also require the unit morphism
to map elements to singleton lists as usual, and the multiplication to be list concatenation.
As the unit morphism must be a monotone map, we then must have for all such that :
in . We shall call this the singleton axiom. By reflexivity, we also need for every list that . In fact, these are all the relations we need, and the resulting construction yields a monad, which we shall denote for convenience.
So we have found a list monad structure on , but it’s a bit ugly. If we think of these lists as data structures, why would we only order singleton lists, this seems a bit unnatural? Instead, it might be more natural for list of the same length and to have
We shall call this the pointwise ordering axiom. Adding pointwise ordering to the construction yields a second monad, which we shall denote .
We could order lists based on their endpoints. So implies:
We shall call this the endpoints axiom. Adding this axiom to the constructions for or yields two more monads and .
Varying things in another direction, we could restrict our attention to lists
such that for all consecutive elements
Clearly, we must still require the singleton axiom, and the relations implied by reflexivity. In fact, this construction yields another monad, which we shall denote . Adding the endpoint axiom to this construction yields a further monad .
Notice that we do have to be careful about these variations though. Adding in the pointwise ordering axiom to or does not result in a valid monad, as list concatenation won’t be monotone so the multiplication is not well-defined. For example, for natural numbers with their usual ordering, pointwise ordering yields
but the concatenation of the ordered list
which is not correctly ordered.
Moving to categories of ordered structures, even whilst restricting our attention to constructions originating with the maybe and list monads, we found a plethora of new possibilities. This newfound freedom all felt slightly wild, with many options for extending and varying constructions that were more straightforward in . Not all the combinations of features yielded valid monads, so care was needed to (hopefully!) avoid mistakes. It is natural to wonder if we can make things more systematic? For example, where did the six monads come from? Are there more? What goes on with other constructions such as the multiset monad?
We shall look at further examples, and the question of whether there are more instructive methods we can bring to bear, in later posts.
One thought on “Getting Our Examples In Order”