A composition, o, on an arrow world, W, is said to be associative precisely if the composites of any composable list are all equal. Note that the dual of an associative composition is associative.

Consequently, in an arrow world with associative composition,

Further Reading

Associativity allows us, at last, to define a category. It also shows up in the discussion of binary operators. As it's the basic tool which makes non-trivial proofs practical, I've begun collecting a few results below.


If a composition makes the two composites of each composable 3-list equal (ie it achieves associativity's restriction to 3-lists), then we can show (by induction on length of list) that all composites of finite composable lists are equal: so the definition could as readilly have resricted itself to composable 3-lists. I'm happy enough, by the way, to work within a restriction that only finite lists can be deemed composable: I'm somewhat shy of considering the composite of an infinite list. I suppose, if I ever need such a composite, and it can sensibly be evaluated, that there must be some other way of describing the matter which evades the inifinity.

Consider a product, a = i o e, of monics. We have Prior(e) contained in Prior(a): parallel arrows in Prior(e), thus composable before a, have equal composites before a precisely if they are equal. [Proof: for p, q in Prior(e) with a o p = a o q, we have i in Post(e), thus composable after e o p and e o q: associativity now lets us turn (i o e) o p = (i o e) o q into i o (e o p) = i o (e o q). As i is monic, this implies e o p = e o q; e being monic as well, we find p = q.] Thus, if the Prior of the first in a composable list of monics subsumes (and so is equal to) the Prior of the list's composite, then this composite is itself monic; the dual of this relates epics and Post.

[Reminder: composition is robust ⇔ the conditions on Prior and Post just required are always satisfied.] Thus, under a robust associative composition, composable iso arrows have iso composite, monics compose to monic and epics compose to epic. This makes the collections of monic, epic and iso arrows in the arrow world into sub-worlds.

Any two mutually inverse arrows, f and g, are isomorphic: fog and gof are the identities at either end; whence f = fogof is a factorisation of f via g and g = gofog factorises g via f. Two parallel iso arrows, e and f, if they have inverses, d and g respectively, factorise via one another via: eod=fog and doe=gof are the identities at either end, giving fogoe = e and fodoe = f as factorisations, so that iso (with inverse) and parallel imply isomorphic. Since, from above, mutually inverse arrows are isomorphic, so also are anti-parallel arrows with inverses.

Relate Zero to Null via Associativity.

Before going on to combine associativity and identifiability to obtain a category, pause to consider something associativity alone allows us to say about null identities in an arrow land. We were previously able to show that two null identities, a and b, were necessarily isomorphic via the unique elements of Hom(a,b)={c} and Hom(b,a)={d}: c and d are null, zero and mutually inverse. Now, for any arrows p and x, we name some unique arrows connecting them to a and b via Hom(p,a)={q}, Hom(p,b)={r}, Hom(a,x)={y} and Hom(b,x)={z}: as a and b are identities, we find (y,q) and (z,r) composable, with composites in Hom(p,x). We also obtain (y,d) and (d,r) composable, via a and b respectively, with composites in Hom(p,b)={z} and Hom(p,a)={q} respectively. Thus y o d = z and d o r = q, so our two composites, z o r and y o q, are (y o d) o r and y o (d o r). Associativity is just the property needed to ensure that these are equal. This implies uniqueness of zero arrows, within each homset, for any associative composition.

A zero identity, z, is the composite of an initial, i, and a terminal, t: z = i o t. Provided it is composable after i and before t (as, for instance, when our associative arrow land is identifiable) we have z o i = i so Post(i) subsumes Post(z), which includes t, so (t, i) is composable. The composite's Prior(t o i) then subsumes Prior(i), which includes t, and Post(t o i) subsumes Post(t), which includes i, so (t o i) is in Hom(t,i): it is composable after a terminal and before an initial. It is therefore unique in its homset, as are the members of its Post and Prior. Because we can form i o (t o i) as well as (i o t) o i = z o i = i, we find i o (t o i) = i; likewise, (t o i) o t = t. Write u = (t o i): so z o i = i = i o u and t o z = t = u o t. Thus u is in Post(t) which is contained in Post(u), so u is self-composable. Its composite is in its homset, therefore equal to it: it is self-square.

For any f in Post(u), the latter is contained in Post(u o t) and u o t = t, so f is in Post(t). Now, for any g in Post(f), we have t composable before initial i, whence Hom(t,g) has only one member, which must then be f. As Post(t) is contained in Post(t o i), we can form f o u = f o (t o i). As i is in Prior(t) contained in Prior(f o t), we can form (f o t) o i, which must then be equal to f o u. Now g in Post(f) contained in Post(f o t) contained in post((f o t) o i) says that f o u is in Prior(g): so t in Prior(i) contained in Prior(u) contained in Prior(f o u) tells us that f o u is in Hom(t,g)={f} so f o u = f. Likewise, for any f in Prior(u), thus in Prior(i), t o (i o f) is in Parallel(f), so equal to it; whence u o f = f. Thus u is an identity. It is composable before an initial, so anything composable after it, including itself, is initial: likewise, anything composable before it, including itself, is terminal. Thus, finally, do we prove that any zero arrow of an associative composition implies the presence of a null identity.

Refugee fragment from discussion on binary operators

an arrow world is just a way of describing a relation. a transformation from U to V is a mapping, (U|T:V), for which `(|U:{f}) subsumes (|U:{g})' implies `(|V:{T(f)}) subsumes (|V:{T(g)})' and `({f}:U|) subsumes ({g}:U|)' implies `({T(f)}:V|) subsumes ({T(g)}:V|)' and it may help to remember that `subsumes' can often be replaced by `='.

two transformations, S and T, from U to V are preconjoinable iff `U relates f to g' implies `V relates S(f) to T(g)'.

arrow-composability is a relation, U: an actual composition (for U) is a binary operator, *, for which `U relates a to b' implies `a*b in (|U:) or (:U|)' but where is it really ? a*b in intersect((|U:{a}): z-> ({z}:U|) |) and a*b in intersect(({b}:U|): c-> (|U:{c}) |) note that if b isn't an initial value of U, or if a isn't final, the relevant intersection is intersect({}) which is the all-relation; saying that a*b is in it imposes no constraint. If b isn't initial and a isn't final, a*b is hopelessly undefined. One may thus assert that it's a bad idea to have U relate a to b unless either a in (:U|) or b in (|U:). Any resemblance this may have to logic is someone else's province.

A transformation, T, from U to V is practical for compositions * on U and % on V iff for every factorisation f = w*...*a in U, there are arrows p, q in V with q % T(a) = T(f) = T(w) % p (So the image of a composite can be factorised via the images of its first and last components.)

Written by Eddy.
$Id: associate.html,v 1.4 2010-08-09 04:18:01 eddy Exp $