Getting Our Examples In Order

Most of the previous posts have focussed on $\mathsf{Set}$ -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 $\mathsf{Set}$ , 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 $P$ consists of a set, which we shall also denote $P$ , and a reflexive, transitive binary relation $\leq$ on $P$ . That is, a relation satisfying both:

Reflexivity: $p_1 \leq p_1$ .
Transitivity: $p_1 \leq p_2$ and $p_2 \leq p_3$ implies $p_1 \leq p_3$ .

A poset is a preorder for which the relation $\leq$ is also irreflexive. That is:

$p_1 \leq p_2 \;\wedge\; p_2 \leq p_1 \;\Rightarrow\; p_1 = p_2$

Example: The set $\mathbb{N}$ of natural numbers is a poset, with their usual ordering.

Example: For any set $X$ , the powerset $\mathcal{P}(X)$ is a poset, with the subset inclusion relation.

Example: For any set $X$ , the the finite powerset $\mathcal{P}_\omega(X)$ can be ordered with $U \leq V$ if the number of elements of $U$ is less than equal to the number of elements of $V$ . This gives the finite powerset of $X$ the structure of a preorder, but not a poset, as both $\{x \}$ and $\{ y \}$ are finite subsets of $\{ x, y \}$ with the same number of elements, but they are not equal.

A morphism of preorders or posets $h : (P, \leq_P) \rightarrow (Q, \leq_Q)$ is a function $h : P \rightarrow Q$ such that:

$p_1 \leq_P p_2 \Rightarrow h(p_1) \leq_Q h(p_2)$

Such functions are referred to a monotone. The categories of preorders and monotone maps, and partial orders and monotone maps will be denoted $\mathsf{Pre}$ and $\mathsf{Pos}$ 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 $X$ to the set $X + 1$ , 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:

$X + 1 = X \uplus \{ \star \} = \{ (1, x) \mid x \in X \} \cup \{ (2,\star) \}$

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 $\mathsf{Pos}$ the coproduct $(P, \leq_P) + (Q, \leq_Q)$ has underlying set $P \uplus Q$ , and order relation $x \leq y$ if and only if either:

$x = (1, p_1)$ and $y = (1, p_2)$ and $p_1 \leq_P p_2$ .
$x = (2, q_1)$ and $y = (2, q_2)$ and $q_1 \leq_Q q_2$ .

That is, we just glue together the two components, and inherit the order from the two parts.

The terminal object in $\mathsf{Pos}$ is also similar to that in $\mathsf{Set}$ . The underlying set is $\{ \star \}$ , and the order relation is the inevitable $\star \leq \star$ .

With these concrete constructions in place, on objects the maybe monad in $\mathsf{Pos}$ 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, $p_1 \leq p_2$ is interpreted as $p_1$ being less informative than $p_2$ .

If we adopt this point of view, the maybe monad is not entirely satisfactory when interpreting $\star$ 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 $(P, \leq_P)$ with universe $(P, \leq_P) \uplus \{ \star \}$ as before. The order relation extends that of the maybe monad with the additional relations:

$(2, \star) \leq (1,p)$

for all $p \in P$ . That is, $\star$ is now placed at the bottom of the resulting structure. In fact, this yields a new monad on $\mathsf{Pos}$ , 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 $X$ , we shall write $L(X)$ for the set of lists of elements from $X$ .

For a poset $(P, \leq_P)$ , we would like to build a monad $\mathbb{L}$ such that $\mathbb{L}(P, \leq)$ has underlying set $L(P)$ . We shall also require the unit morphism

$\eta_{(P,\leq)} (P, \leq_P) \rightarrow \mathbb{L}(P, \leq)$

to map elements to singleton lists $p \mapsto [p]$ as usual, and the multiplication to be list concatenation.

As the unit morphism must be a monotone map, we then must have for all $p_1, p_2$ such that $p_1 \leq p_2$ :

$[p_1] \leq [p_2]$

in $\mathbb{L}(P,\leq)$ . We shall call this the singleton axiom. By reflexivity, we also need for every list $l$ that $l \leq l$ . In fact, these are all the relations we need, and the resulting construction yields a monad, which we shall denote $\mathbb{L}_1$ for convenience.

So we have found a list monad structure on $\mathsf{Pos}$ , 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 $[p_1,\ldots,p_n]$ and $[q_1,\ldots,q_n]$ to have

$[p_1,\ldots,p_n] \leq [q_1,\ldots,q_n]$

$p_1 \leq_P q_1 \; \wedge\; \ldots \; \wedge \; p_n \leq_P q_n$

We shall call this the pointwise ordering axiom. Adding pointwise ordering to the construction $\mathbb{L}_1$ yields a second monad, which we shall denote $\mathbb{L}_2$ .

We could order lists based on their endpoints. So $p_n \leq q_1$ implies:

$[p_1, \ldots, p_n] \leq [q_1,\ldots,q_m]$

We shall call this the endpoints axiom. Adding this axiom to the constructions for $\mathbb{L}_1$ or $\mathbb{L}_2$ yields two more monads $\mathbb{L}_3$ and $\mathbb{L}_4$ .

Varying things in another direction, we could restrict our attention to lists

$[p_1, \ldots p_n]$

such that for all consecutive elements $p_i, p_{i + 1}$

$p_i \leq_p p_{i + 1}$

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 $\mathbb{L}_5$ . Adding the endpoint axiom to this construction yields a further monad $\mathbb{L}_6$ .

Notice that we do have to be careful about these variations though. Adding in the pointwise ordering axiom to $\mathbb{L}_5$ or $\mathbb{L}_6$ 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

$[0,3] \leq [1,4]$

but the concatenation of the ordered list

$[[0,3],[1,4]]$

$[0,3,1,4]$

which is not correctly ordered.

Conclusion

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 $\mathsf{Set}$ . 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 $\mathbb{L}_1, \ldots \mathbb{L}_6$ 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”

Pingback: Algebra, Order and Monads – Dan Marsden

Basics of Posets and Preorders

Relatives of the Maybe Monad

Relatives of the List Monad

Conclusion

Share this:

Like this:

Related

One thought on “Getting Our Examples In Order”

Leave a Reply Cancel reply