Binary Operators for Categories

At the heart of any category lies a binary operator, which it construes as composition; this is the fundamental entity which defines everything about the category. Unlike the binary operators of linear algebra, number theory and various other fields, however, the binary operator 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 set out the properties a binary operator must have to be the central player of a category.

Specification

First we must define a type:

operand of binary-operator

For any binary operator *, in so far as the expression x*y is defined, the values of x and y are operands of *. In particular, in this case, x is a left operand and y is a right operand, since each appears on the indicated side of *.

and the first constraint on any binary operator, if it is to be categoric, is that whenever it does combine two values, the result is itself an operand. Furthermore – as orthodoxy forces by having an identity on either side of every operand, which combines with it to yield it – every operand must be a compound of operands; and must be both a right operand and a left operand. Define, further,

({relations}: follow :{binary operators})

= (: ({operands of *}: x←y; x*y is defined :{operands of *}) ← * :)

i.e. follow(*) relates x to y iff x*y is defined. Note that the left operand (which appears first textually) is said to follow the right operand (which appears after it); this is an entirely deliberate choice so as to have the composition, &on;, of relations, when considered applying to functions f and g, describe f as following g in f&on;g = (: f(g(x)) ←x :), since x is fed first to g, then g's output is fed to f. Aside from this, the temporal connotations of follow should be ignored.

We are now able to specify another requirement (or three, depending on how you look at them) our binary operator must satisfy:

• whenever follow(*) relates x to y and y to z: it also relates x*y to z and x to y*z; and (x*y)*z = x*(y*z).

The final part of that is the property called transitivity; the earlier parts should be viewed as a necessary precondition of it. Note that this should not be construed as forbidding * to be ambiguous: if it is, then (for example) follow(*) relates x to y*z should be read as follow(*) relates x to each value y*z may take and (x*y)*z = x*(y*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.

Given transitivity, it is practical to compose lists of operands; so define

({collections}: composable :{binary operators})

= (: {lists ({operands of *}:h|1+n): for each i in n, follow(*) relates h(i) to h(1+i)} ← * :),

and

({relations}: bulk :{binary operators})

= (: ({operands of *}: bulk(*) :composable(*)) ← * :)

defined by

• for each operand a of *, bulk(*) relates a to [a]
• h = [a,...,f,g,...,z] in composable(*) implies bulk(*) relates bulk(*,[a,...,f]) * bulk(*,[g,...,z]) to h.

Note that, when * is unambiguous, bulk(*) is a mapping, thanks to transitivity.

Duality

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. This yields operands(@) = operands(*), follow(@) = reverse(follow(*)) and

• bulk(@)&on;(composable(@)| (:h(j) ←i; i+j = 1+n |n) ← (:h|n) |composable(*)) = bulk(*)

(i.e. list-reversal transforms composable(*) into composable(@), and transforms the bulk action of each into that of 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. Where {operands of *} is considered as a category under *, the matching category under *'s transpose is described as the dual of the original. 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.

Monic and Epic

Given a categoric binary operator *, describe an operand f of * as

*-monic

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

i.e. f* distinguishes distinct right operands

*-epic

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.

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.