]> Combiners for Categories

Combiners for Categories

At the heart of any category lies combiner, which it construes as composition; this is the fundamental entity which defines everything about the category. Unlike the flat combiners of linear algebra, number theory and various other fields, however, the combiner of a category can be selective: it does not indiscriminately combine any two of its possible operands, but only combines certain of its operands. None the less, it is not entirely capricious about which operands it will combine. Here I look at what follows from being categoric.


Like every combiner, our category's composition is a binary operator, so it combines values two by two. Usually, the values a binary operator combines are termed operands of the binary operator; in the case of a category, we refer to an operand of its composition (whether it is a left operand or a right operand) as a morphism. So our combiner composes morphisms. To be categoric, our composition must have every morphism both as a left operand and as a right operand; for each morphism m, there must be some morphisms i and e for which e&on;m and m&on;e are valid compositions.

When our composition does combine some morphisms m, n as m&on;n, I describe the two morphisms as composable; in particular, I describe m as composable to the left of n and n as composable to the right of m. When (as is usual) our composition isn't flat, this composability relation is an important property of the composition, that constrains what it makes sense to ask of the composition.

Again like any combiner, our composition is closed: so the result of composing two morphisms is itself a morphism. Furthermore, a categoric combiner is also required to realise every morphism as a composite in this way. (Contrast the addition on positive naturals: it's closed, but no two operands add up to 1, which is one of its operands.) So, for each morphism m, there must be some morphisms r, s for which r&on;s = m.

The last property our composition shares with every combiner is that it's associative, so (a&on;b)&on;c = a&on;(b&on;c) and we can write a&on;b&on;c for it without needing parentheses, which is most welcome when we combine many operands. The final property that a category's composition has, that other combiner's don't, ensures that associativity does come into play; I'll come back to how it does that below, but first let me just state the property.

When two morphisms m, n are both composable to the left of some specific morphism, so m&on;c and n&on;c are valid for some c, every morphism composable to the right of either of them must be composable to the right of both; so valid m&on;d implies valid n&on;d. Likewise, if m and n are both composable to the right of some specific morphism, then any morphism comoposable to the left of either is also composable to the left of the other.

Identities (and objects)

For a categoric combiner, an identity is a morphism i that satisfies

What I've expressed as every morphism is both a left operand and a right operand and every morphism is a composite get expressed in orthodox category theory as: for every morphism m, there is an identity composable on its left and an identity composable on its right. If those are i and e respectively, we get i&on;m = m = m&on;e and, sure enough, m is both a left operand and a right operand; it's also a composite. I may end up having to fall back to this specification, but my intuition claims (after some earlier doodling) that I don't actually need identities as such (and thus don't have to give a special status to identities), as long as my two more general conditions are met.

Orthodoxy also usually characterises each identity as the identity on some object; but this merely burdens the discussion with a need to talk about these objects, where the identities serve as entirely sufficient proxies for them. (Some otherwise fairly orthodox authors have noticed this, though; so I had a lecturer who pointed out the objects were redundant.) So if you see a category theorist talking about objects, you can pretend they're talking about the identities on them, instead.

The attentive reader might notice that I haven't defined a category at all; only the categoric combiner that composes its morphisms. The reason for this is that, in fact, the category is just an object (in a category of functors between categories), so not actually interesting to talk about in its own right, like any other object. What actually matters is its composition. Orthodoxy typically refers to a category by the term for its objects, rather than for its morphisms; thus Set is the category of functions under clean composition, Group is the category of group homomorphisms under their proper composition. In each case, I discuss the composition.

If there is an identity composable to the left of some morphism, m, then that identity is composable to the right of every morphism, n, composable to the left of m, since n&on;m = n&on;(i&on;m) = (n&on;i)&on;m. Likewise, any identity composable to the right of a morphism n is necessarily composable to the left of every morphism composable to the right of n. If we have composable m&on;n and there is an identity i composable to either the right of m or the left of n, both of these composabilities hold; furthermore, any u composable to the left of n and w composable to the right of m have u&on;i&on;n and m&on;i&on;w valid, whence u&on;i&on;w = u&on;w is valid. This suffices to ensure that orthodoxy's ubiquitous identities do in fact cause my more general condition to be met.

If two identities are composable, they are necessarily equal, since i = i&on;e = e follows from each being an identity, making the composite equal to the other. If two identities are composable to the left fo some given morphism, m, each is composable to the right of the other, so they are equal; likewise, two identities composable to the right of a given morphism are necessarily equal. Thus, among the morphisms composable at either end of a given morphism, there is at most one identity. In any category of homomorphisms, we do indeed have identity morphisms composable at either end of every morphism, so orthodoxy's requirement for an identity at each end is met; and those identities are unique.


Every morphism is both a left operand and a right operand of composition; so, given a morphism v, we definitely have some morphisms u composable to the left of v and w composable to the right of v. Suppose we have u&on;v and v&on;w valid: we've just seen there are some such u, w for any given v. Since v is some composite, we have v = r&on;s for some morphisms r, s. We thus have u&on;(r&on;s) and (r&on;s)&on;w valid; and associativity then gives us (u&on;r)&on;s and r&on;(s&on;w) as valid compositions. Now, as u&on;r and r are composable to the left of s, any morphism composable to the right of r is also composable to the right of u&on;r; and we have r&on;(s&on;w) valid, so s&on;w is such a morphism and we have (u&on;r)&on;(s&on;w) valid. Associativity turns this into u&on;(r&on;s)&on;w = u&on;v&on;w. So, whenever v is composable to the left of u and the right of w, the three-way composite u&on;v&on;w is indeed valid.

Thus the bulk action of our composition accepts, as inputs, any list ({morphisms}: f |1+n), with n natural, for which, for every i in n, f(i) is composable to the left of f(1+i). The preceding result ensures, given associativity, that every such list is composable in our category. When &on; is unambiguous, bulk(&on;) is a mapping, thanks to associativity.

Note that nothing here prevents &on; from being ambiguous: if it is, then (for example) x is composable to the left of y&on;z should be read as x is composable to the left of each value y&on;z may take and (x&on;y)&on;z = x&on;(y&on;z) should be read as asserting – for given values of x, y and z – equality of the collections (possibly expanded by any equivalences implied by context) of values the two expressions may take.

Thus far, I've discussed the categoric combiner as &on; because it's normally thought of as a composition, typically of homomorphisms. However, any categoric combiner will do and, in what follows, I shall want to make mention of the composition of relations; so, hereafter, I'll use some more generic name, typically *, for the categoric combiner under study.


Any binary operator can be transposed; formally identifying * with (: (: a*b ←b :) ←a :), its transpose is @ = (: (: a*b ←a :) ←b :) or, equivalently, (: (: b*a ←b :) ←a :), so that b*a = a@b. The manifest symmetry of the specification of a categoric combiner ensures that its transpose is also categoric.

The two categories that result are described as dual or opposite to one another; they have the same morphisms (and objects) as one another. (It is common to add a suffix op on a category or its composition to denote the dual category or its transposition.) More generally, when two concepts relating to categoric operators are interchanged by transposing a relevant operator, or several related operators, those concepts are described as mutually dual (or each is described as dual to the other).

Since transposition is simply reversing the order of operands, one may reasonably wonder why it is worth discussing at all; however, various conceptions relating to categories are interchanged by it, so that it can simplify their discussion; and, once we come to consider categoric transformations, there'll be uses for considering ones that reverse the order of operands.

Monic and Epic

Given a categoric combiner *, describe a morphism f of * as

iff f*a = f*b implies a = b

i.e. f* distinguishes distinct right operands

iff a*f = b*f implies a = b
iff f is transpose(*)-monic

i.e. *f distinguishes distinct left operands.

and only include the *- prefix when not manifestly implied by context. It should be clear that monic and epic are mutually dual concepts, in the sense above. They correspond (respectively) to left- and right-cancellability in a flat combiner, adapted to accommodate the limited composability of the categoric combiner.

In the categories of sets and relations

Generally, I describe a relation, r, as monic precisely if r relates x to y and x to z implies y = z, which is exactly the condition for reverse(r) to be a mapping. In the above, if f is *-monic, then (: f*x ←x :) is indeed monic, in this sense; if f is *-epic, then (: x*f ←x :) is likewise monic.

If we take * as the clean composition of mappings (which composes f&on;g = (: f(g(x)) ←x :) precisely if (:f|) subsumes (|g:), so that (f&on;g:x←x:) = (g:x←x:), i.e. f&on;g accepts every input of g) we can let a and b be single-output maps, (:x←0:) for x in (:f|), and thus show that f is monic precisely if it never maps two inputs to the same output; if we distinguish as different mappings (A:f:) and (B:f:) for each collection A and B that subsume (:x←x:f), then consideration of single-input maps (:0←x:) for various x will reveal that (A:f:) is epic precisely if A = (:x←x:f), i.e. f produces every member of A as an output. Thus orthodoxy's examination of the category it calls Set describes surjective functions (a.k.a. epimorphisms) as epic and injective functions (a.k.a. monomorphisms) as monic.

Valid CSSValid XHTML 1.1 Written by Eddy.