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.
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.
Given a categoric combiner *, describe a morphism f of * as
f*a = f*bimplies
a = b
i.e. f* distinguishes distinct right operands
a*f = b*fimplies
a = b
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.
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.
Written by Eddy.