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,

- Whenever g o h is epic, so is g. [Proof: For any a, b in Post(g) with equal composite, we have (a, g, h) and (b, g, h) as composable lists with equal composite, since (a o g) o h = (b o g) o h: thus a o (g o h) = b o (g o h): but g o h is epic, so a = b. QED.]
- Whenever g o h is monic, so is h. Thus the first (right-most) factor in any factorisation of a monic is also monic.
- When discussing factorisation of one arrow, e,
*via*another, i, we can shorten the implied list in which i appears by replacing the sub-lists preceding and following (some particular instance, in the list, of) i with their composites. Consequently, we need never consider factorisations of length greater than three (but never forget shorter ones). - In any factorisation of an iso (
*eg*any identity), the first factor must be monic and the last (left-most) epic.

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.

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.

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.)

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