What does associativity mean for orders?

120 Views Asked by At

I'm watching the class Category Theory for Programmers and it's said that an order (preorder, partial order, or total order) constitutes a category, and one of the conditions for this is that the relation is associative.

I understand how and why $(x+y)+z = x+(y+z)$, in the sense that the order of applying the $+$ operator doesn't matter - after doing $x+y$ I get a number $w$, then I can do $w+z$.

However I don't really understand what $(a\leq b)\leq c$ means. $(a\leq b)$ doesn't produce a number like $(x+y)$; it's just a true/false value of whether or not $a$ is less than or equal to $b$.

What does it mean to ask "is $a$ is smaller than $b$ smaller than $c$"?

What's a better interpretation of asking whether an order is associative?

1

There are 1 best solutions below

2
On BEST ANSWER

I think part of your confusion is just the notation being used. To make a poset into a category, you have precisely one morphism from $a$ to $b$ exactly if $a \leq b$, but $a \leq b$ is not (usually) the "name" of that morphism. For the purposes of this answer, we'll call such a morphism (if it exists) $l_{a, b} \in \hom(a, b)$.

The key idea that will affect everything below is that elements of $\hom(a, b)$ are unique if they exist (for this kind of category - this is not true for all categories). For any morphisms $f, g \in \hom(a, b)$, $f = g$ because both $f$ and $g$ are equal to $l_{a, b}$.

The axioms of a category then require that there is an identity morphism $\mathrm{id}_a : a \to a$, indicating that the relation $\leq$ needs to be reflexive ($a \leq a$). Since there's exactly one morphism between two objects if it exists, $\mathrm{id}_a$ must be $l_{a, a}$.

Next, we require composition: a map $\hom(b, c) \times \hom(a, b) \to \hom(a, c)$. Remembering that $\hom(a, b)$ is inhabited (by $l_{a, b}$) exactly if $a \leq b$, this translates to transitivity of the relation: $ b \leq c$ and $a \leq b$ implies $a \leq c$.

But what is $l_{b, c} \circ l_{a, b}$? We know that it's an element of $\hom(a, c)$, but that set has at most one element, and if it has any element, it's $l_{a, c}$. So $l_{b, c} \circ l_{a, b} = l_{a, c}$.

The other conditions talk about equality of morphisms. But remember that any morphisms with the same domain and codomain are equal, so these equalities are all trivial.

Left identity is $\mathrm{id}_b \circ f = f$ for all morphisms $f \in \hom(a, b)$. Both sides of the equality are morphisms from $a$ to $b$, so they're automatically equal. Similarly, right identity, $f \circ \mathrm{id}_a = f$ is trivially true.

Associativity says that for morphisms $f \in \hom(c, d)$, $g \in \hom(b, c)$ and $h \in \hom(a, b)$, $(f \circ g) \circ h = f \circ (g \circ h)$. Both sides of the equality are morphisms from $a$ to $d$, so they are trivially equal once again. Both sides would equal $l_{a, d}$ in this case.