nLab
ordinal sum

Ordinal sums

Idea

In ordinal arithmetic?, the ordinal sum is a natural addition on ordered sets and so provides a useful tool when manipulating simplicial sets. In ordinal sum you ‘first put one of the two ordinals and then the other’, so that the elements of the second ordinal are all bigger than those in the first one.

The ordinal sum induces the operation of join of simplicial sets endowing sSetsSet with the structure of a monoidal category.

Ordinals as simplicial sets

The objects of the augmented simplex category Δ a\Delta_a can be identified with the finite totally ordered sets, including the empty set, which we write in this context as

[1] [-1] \coloneqq \emptyset

so that then

[0]=* [0] = *

is the singleton set, as usual and

[1]={0<1} [1] = \{ 0 \lt 1\}

and so on, so that [n]={0<<n}[n] = \{ 0 \lt \ldots \lt n\}

This counting is off by one compared to the cardinality of these sets.

Definition

The monoidal structure on Δ a\Delta_a that we are interested in now is, at the level of the sets, just the disjoint union, but we have to consider the order on that union. If we have [n][n] and [m][m], we form the union of the two sets, where we know the order on two elements we keep it, but if we have two elements one, ii, say, from the [n][n] and the other, jj, from [m][m] we put i<ji \lt j.

As an example, consider [1]={0<1}[1] = \{ 0 \lt 1\} and [2]={0¯<1¯<2¯}[2] = \{\overline{0} \lt \overline{1} \lt \overline{2}\}, where the overlines are just so that we can keep track of where the different elements come from. We form the union of the two sets and the rule says that anything without an overline is less than anything with one. This gives a linear order

[1][2]={0<1<0¯<1¯<2¯},[1] \oplus [2] = \{0 \lt 1 \lt \overline{0} \lt \overline{1} \lt \overline{2}\},

which is isomorphic as a poset to [4][4]. Similarly [1][1]=[3][1] \oplus [1] = [3], which helps explain the picture of the related join of simplicial sets given there.

We can thus think of the operation as the addition of cardinalities, but must remember that [n][n] has n+1n + 1 elements. In terms of the counting ‘off-by-one’, this reads

([n],[m])[n+m+1], ([n], [m]) \mapsto [n + m + 1] \,,

but remember there is also the order to keep track of.

This operation extends to give the ordinal sum structure on Δ a\Delta_a (for details see the discussion in the entry simplex category) making it a monoidal category, whose monoidal product is the \oplus operation described above.

Warning: this monoidal structure is not symmetric! One does have isomorphisms [i][j][i+j+1][j][i][i] \oplus [j] \simeq [i+j+1] \simeq [j] \oplus [i] for all i,ji,j, but it is easy to see that they are not bifunctorial.

Ordinal sum of categories

In “Ordinal Sums and Equational Doctrines”, Lawvere defines the ordinal sum A+ σBA +_\sigma B of two categories AA and BB as the pushout

A×|2|×B A×2×B A+B A+ σB \array{ A \times |2| \times B &\to& A \times 2 \times B \\ \downarrow & & \downarrow \\ A + B &\to & A +_\sigma B }

where A+BA+B is the coproduct of AA and BB, 2 is the interval category, |2||2| is its underlying discrete category of objects, and the left vertical arrow is defined by

a,i,b={a i=0 b i=1 \lang a,i,b\rang = \begin{cases}a & i = 0 \\ b & i = 1\end{cases}

Concretely, A+ σBA +_\sigma B may be described as the category A+BA + B together with exactly one arrow aba \to b adjoined for every object aA,bBa \in A, b \in B (in other words, as the collage of AA and BB along the terminal profunctor).

Equivalently, A+ σBA +_\sigma B may be described as the colimit of the diagram

A×B A×B π 1 i 0 i 1 π 2 A A×2×B B.\array{ & & A \times B & & & & A \times B & & \\ & \mathllap{\pi_1}\; \swarrow & & \searrow \; \mathrlap{i_0} & & \mathllap{i_1}\; \swarrow & & \searrow \; \mathrlap{\pi_2} & \\ A & & & & A \times 2 \times B & & & & B. }

References

  • William Lawvere, Ordinal sums and equational doctrines. In ‘’Seminar on Triples and Categorical Homology Theory’’, LNM 80 (1969), pp. 141-155.

Revised on June 12, 2014 12:27:14 by Adeel Khan (77.9.201.13)