Operations on the class of linear orderings from a categorical perspective

82 Views Asked by At

Delaying the question for now, I will henceforth use $\mathcal{L}$ to represent the class of (strict) linear orderings and elements of $\mathcal{L}$ will be denoted using lowercase Greek letters (possibly subscripted) from $\alpha$ to $\epsilon$. I will refer to the category whose object class is $\mathcal{L}$ as $\mathbf{Lin}$ where $\mathrm{Mor(\mathbf{Lin})}$ consists of all isotone maps i.e. maps $f\colon\alpha\to\beta$ such that \begin{equation} a<b\quad\Longrightarrow\quad f(a)\leq f(b). \end{equation}

The three operations I wish to inquire about will now be defined. If $\alpha,\beta,\alpha_i\in\mathcal{L}$, with respective universes $A,B,A_i$, for each $i\in B$ then:

  1. $\alpha+\beta$ is inverse (of the) lexicographical ordering on $(A\times\{0\})\cup (B\times\{1\})$ (intuitively: the concatenation of $\alpha$ and $\beta$)
  2. $\sum_{\gamma\in\beta}\alpha_i$ is (analogously to (1.)) the inverse lexicographical ordering (w.r.t. $\beta$) of $\bigcup_{i\in\beta}(A_i\times\{i\})$ (intuitively: one takes $\beta$ and then substitutes each point $i\in B$ with $\alpha_i$).
  3. The product is defined $\alpha\cdot\beta=\sum_{i\in\beta}\alpha$ (informally: $\beta$ copies of $\alpha$).

I am a novice when it comes to the theory of categories but essentially I'm hoping to see if the above operations can be extended to related structures (e.g. semi-linear orderings a.k.a trees) using their categorical descriptions (given they exist) as a guide.

The question is thus how can we relate (if at all possible), within $\mathbf{Lin}$, each of these constructions (operations) to their constituents (arguments/operands) using categorical language. It would be appreciated if as far possible, only concepts encountered within a first course in category theory are utilised in the answer (I hope this is not asking too much).

1

There are 1 best solutions below

3
On BEST ANSWER

We can indeed express these concepts categorically, although it's pretty messy. (For simplicity I'll conflate isomorphic linear orders.)

The key point is that we can "see" the structure of an object in Lin in a purely categorical way, and so the order-theoretic definitions wind up with purely categorical rephrasings.


The first thing to do is dig into the internal structure of linear orders in a purely categorical manner. First, we observe that Lin has a terminal object (the one-element linear order $\bf 1$), and elements of a linear order $L$ correspond exactly to morphisms from $\bf 1$ to $L$. This also lets us identify injective and surjective morphisms:

  • $i:L_1\rightarrow L_2$ is injective iff there are no distinct morphisms $m_1,m_2:{\bf 1}\rightarrow L_2$ such that $im_1=im_2$.

  • $i:L_1\rightarrow L_2$ is surjective iff for every $m:{\bf 1}\rightarrow L_2$ there is some $n:{\bf 1}\rightarrow L_1$ such that $in=m$.

(In fact, unsurprisingly injectivity and surjectivity correspond to monicity and epicity. But I'm going to use the terms injective/surjective to emphasize the success we've had pinning down the more set theoretic operations.)


The next step is to recover the linear order structure - that is, we want a purely categorical way to compare morphisms ${\bf 1}\rightarrow L$ (for each $L$) which recovers the linear order structure. Let ${\bf 2}$ be the linear order with two elements, let $a:{\bf 1}\rightarrow{\bf 2}$ be the morphism corresponding to the least element of $\bf 2$, and let $z:{\bf 1}\rightarrow {\bf 2}$ be the morphism corresponding to the greatest element of ${\bf 2}$. Then given any $L\in \mathcal{L}$ and morphisms $p_1,p_2:{\bf 1}\rightarrow L$, we say $p_1\le p_2$ iff $p_1=p_2$ or there is a morphism $q:L\rightarrow {\bf 2}$ such that $qp_1=a$ and $qp_2=z$. Similarly, we'll say $p_1<p_2$ if $p_1\le p_2$ and $p_1\not=p_2$.

We can also compare more general morphisms: given $a_1\in Hom(L_1, L_3)$ and $a_2\in Hom(L_2,L_3)$ we say $a_1<a_2$ if for every $c_1\in Hom({\bf 1}, L_1), c_2\in Hom({\bf 1}, L_2)$ we have $a_1c_1<a_2c_2$.


At this point we can define sums of linear orders: given linear orders $L_1, L_2,L_3$, we have that $L_3\cong L_1+L_2$ iff there are morphisms $m_1:L_1\rightarrow L_3$, $m_2:L_2\rightarrow L_3$ such that:

  • $m_1$ and $m_2$ are injective.

  • For every $k:{\bf 1}\rightarrow L_3$ there is an $n:{\bf 1}\rightarrow L_i$ with $m_in=k$ for some $i\in\{1,2\}$. (Covering)

  • $m_1<m_2$. (Ordering)

This leaves the problem of indexed sums. But the idea is basically the same: given a linear order $I$ and a family of linear orders $\{L_i: i\in Hom({\bf 1}, I)\}$, the key property of the indexed sum $S$ is the existence of a family of injective morphisms $m_i: L_i\rightarrow S$ satisfying the appropriate analogues of (Covering) and (Ordering) above.