From Composition to Decomposition: Coalgebras of Locally Finite Categories

Locally Finite Categories and Their Incidence Coalgebras

A category tells us how morphisms compose:

$$x\stackrel{f}{\to }y\stackrel{g}{\to }z⇝g\circ f:x\to z.$$

There is a natural way to read this operation backwards.

Given a morphism

$$h:x\to z,$$

instead of asking how two arrows compose to form $h$$h$, we ask for all possible ways of decomposing $h$$h$ into two composable arrows:

$$x\stackrel{f}{\to }y\stackrel{g}{\to }z,g\circ f=h.$$

If there are only finitely many such decompositions, we may add them together. After linearization this produces a coproduct

$$\mathrm{\Delta }(h)=\sum _{h=g\circ f}f\otimes g.$$

Thus ordinary categorical composition gives rise, in the opposite direction, to a coalgebra of decompositions.

---

Locally finite categories

Let $\mathcal{C}$$\mathcal C$ be a small category.

For a morphism

$$h:x\to z,$$

define its set of two-step factorizations by

$${\mathrm{Fact}}_2(h)=\{(f,g)|x\stackrel{f}{\to }y\stackrel{g}{\to }z,g\circ f=h\}.$$

Here the intermediate object $y$$y$ is allowed to vary.

In this note, we call $\mathcal{C}$$\mathcal C$ locally finite if

$${\mathrm{Fact}}_2(h)$$

is finite for every morphism $h$$h$.

Equivalently, if we regard composition as the map

$$\coprod _{x,y,z}\mathcal{C}(x,y)\times \mathcal{C}(y,z)⟶\mathrm{Mor}(\mathcal{C}),$$

then local finiteness says that every fibre of this map is finite.

This is the finiteness condition relevant to the coalgebra construction.

It is stronger in the relevant direction than merely asking each Hom-set to be finite. A morphism could pass through infinitely many different intermediate objects even if every individual Hom-set were finite.

---

From a category to a coalgebra

Fix a field $k$$k$ and let

$$k[\mathrm{Mor}\mathcal{C}]$$

be the free $k$$k$-vector space on the morphisms of $\mathcal{C}$$\mathcal C$.

For a basis morphism $h$$h$, define

$$\boxed{{\displaystyle \mathrm{\Delta }(h)=\sum _{h=g\circ f}f\otimes g.}}$$

Because $\mathcal{C}$$\mathcal C$ is locally finite, this is a finite sum and therefore defines an element of

$$k[\mathrm{Mor}\mathcal{C}]\otimes k[\mathrm{Mor}\mathcal{C}].$$

Extend $\mathrm{\Delta }$$\Delta$ linearly.

Define also

$$\begin{array}{c}\epsilon (h)=\{\begin{array}{ll}1,& h={\mathrm{id}}_x\text{ for some }x,\\ 0,& \text{otherwise}.\end{array}\end{array}$$

We claim that

$$(k[\mathrm{Mor}\mathcal{C}],\mathrm{\Delta },\epsilon )$$

is a coalgebra.

---

Coassociativity is associativity of factorization

Let

$$h:x\to z.$$

Applying $\mathrm{\Delta }$$\Delta$ once gives all two-step factorizations

$$h=g\circ f.$$

Applying $\mathrm{\Delta }$$\Delta$ again to the first factor gives

$$(\mathrm{\Delta }\otimes 1)\mathrm{\Delta }(h)=\sum _{h=g\circ f}\mathrm{\Delta }(f)\otimes g.$$

Expanding,

$$(\mathrm{\Delta }\otimes 1)\mathrm{\Delta }(h)=\sum _{h=g\circ b\circ a}a\otimes b\otimes g.$$

On the other hand,

$$(1\otimes \mathrm{\Delta })\mathrm{\Delta }(h)=\sum _{h=g\circ f}f\otimes \mathrm{\Delta }(g),$$

hence

$$(1\otimes \mathrm{\Delta })\mathrm{\Delta }(h)=\sum _{h=c\circ b\circ f}f\otimes b\otimes c.$$

Both expressions simply sum over all three-step factorizations

$$x\stackrel{f_1}{\to }{x}_1\stackrel{f_2}{\to }{x}_2\stackrel{f_3}{\to }z$$

such that

$$f_3{f}_2{f}_1=h.$$

Therefore

$$\boxed{{\displaystyle (\mathrm{\Delta }\otimes 1)\mathrm{\Delta }=(1\otimes \mathrm{\Delta })\mathrm{\Delta }.}}$$

The coassociativity of the coalgebra is thus nothing more than the associativity of composition in the original category.

There are two ways to cut a three-step factorization into a two-step factorization followed by another cut, but they describe exactly the same collection of three-step factorizations.

---

The counit remembers trivial factorizations

Every morphism

$$h:x\to y$$

has two distinguished factorizations:

$$h=h\circ {\mathrm{id}}_x$$

and

$$h={\mathrm{id}}_y\circ h.$$

Now consider

$$(\epsilon \otimes 1)\mathrm{\Delta }(h).$$

Among all factorizations

$$h=g\circ f,$$

the counit kills every term except those for which $f$$f$ is an identity.

The unique surviving term is

$${\mathrm{id}}_x\otimes h,$$

and hence

$$(\epsilon \otimes 1)\mathrm{\Delta }(h)=h.$$

Similarly,

$$(1\otimes \epsilon )\mathrm{\Delta }(h)=h.$$

Thus

$$\boxed{{\displaystyle (\epsilon \otimes 1)\mathrm{\Delta }=1=(1\otimes \epsilon )\mathrm{\Delta }.}}$$

So identities in the category become the counit of the coalgebra.

There is a useful dictionary:

$$\begin{array}{cc}\text{category}& \text{coalgebra}\\ \text{composition}& \text{decomposition}\\ \text{associativity}& \text{coassociativity}\\ \text{identity morphisms}& \text{counit}\end{array}$$

---

Posets as the first example

Let $P$$P$ be a poset, regarded as a category:

$$x\to y⟺x\le y.$$

There is at most one morphism between any two objects.

For $x\le z$$x\leq z$, a factorization

$$x\to y\to z$$

is therefore exactly the choice of an element

$$x\le y\le z.$$

Hence

$${\mathrm{Fact}}_2(x\to z)\cong [x,z]=\{y\mid x\le y\le z\}.$$

The categorical local-finiteness condition becomes

$$[x,z]\text{ is finite for every }x\le z,$$

which is precisely the usual definition of a locally finite poset.

Writing $[x,z]$$[x,z]$ for the basis element associated to the unique morphism $x\to z$$x\to z$, the coproduct becomes

$$\boxed{{\displaystyle \mathrm{\Delta }[x,z]=\sum _{x\le y\le z}[x,y]\otimes [y,z].}}$$

This is the classical incidence coalgebra of a locally finite poset.

Thus the categorical construction is a direct generalization of incidence coalgebras of posets.

---

The matrix coalgebra

There is another striking example.

Let $X=\{1,\dots ,n\}$$X=\{1,\dots,n\}$ and consider the category having exactly one morphism

$$c_{ij}:i\to j$$

for every ordered pair $(i,j)$$(i,j)$.

Composition is forced:

$$c_{rj}\circ c_{ir}=c_{ij}.$$

For a fixed morphism

$$c_{ij}:i\to j,$$

a two-step factorization is determined exactly by the choice of an intermediate object $r$$r$:

$$i\stackrel{c_{ir}}{\to }r\stackrel{c_{rj}}{\to }j.$$

Therefore

$$\boxed{{\displaystyle \mathrm{\Delta }(c_{ij})=\sum _{r=1}^n{c}_{ir}\otimes c_{rj}.}}$$

The counit is

$$\epsilon (c_{ij})={\delta }_{ij}.$$

This is precisely the standard matrix coalgebra.

So the familiar formula

$$\mathrm{\Delta }(c_{ij})=\sum _r{c}_{ir}\otimes c_{rj}$$

is not an artificial definition.

It simply says:

list every possible way of passing from $i$$i$ to $j$$j$ through an intermediate object.

The summation index $r$$r$ is literally the intermediate object of a factorization.

---

Why matrix multiplication appears

Now let $A$$A$ be a $k$$k$-algebra.

For two linear maps

$$f,g:k[\mathrm{Mor}\mathcal{C}]\to A,$$

the coalgebra structure defines their convolution

$$f\ast g=m_A(f\otimes g)\mathrm{\Delta }.$$

In the matrix example,

$$(f\ast g)(c_{ij})=\sum _{r}f(c_{ir})g(c_{rj}).$$

If we identify $f$$f$ and $g$$g$ with the matrices

$$F_{ij}=f(c_{ij}),G_{ij}=g(c_{ij}),$$

then

$$(f\ast g)(c_{ij})=\sum _r{F}_{ir}{G}_{rj}=(FG{)}_{ij}.$$

Hence

$$\boxed{{\displaystyle {\mathrm{Hom}}_k(C_n,A)\cong M_n(A)}}$$

as algebras, where the left-hand side carries convolution.

Matrix multiplication is therefore an incidence convolution arising from categorical factorization.

---

A broader interpretation

The construction suggests a general way of thinking about coalgebras.

A category begins with a forward operation:

$$(f,g)⟼g\circ f.$$

A coalgebra reverses the question.

Given the output $h$$h$, it asks:

$$\text{in how many ways can }h\text{ be obtained as }g\circ f?$$

After linearization, the answer is

$$\mathrm{\Delta }(h)=\sum _{h=g\circ f}f\otimes g.$$

Thus the coproduct records not merely a formal duplication, but a geometry of decompositions.

In this sense,

$$\boxed{{\displaystyle \text{composition is many-to-one, while comultiplication remembers the whole fibre of composition.}}}$$

The finiteness condition ensures that this fibre may be linearized by an ordinary finite sum.

This point of view explains at once why incidence coalgebras, matrix coalgebras, and later convolution algebras all have the same formal shape.

The coproduct tells us how an object decomposes.