Eddy thinging about binary operators

When context has a commutative associative binary operator, we can treat it as `addition' and do various things, like `repetition' to it; among other things, we can define a `bulk action' which, when the binary operator is construed as addition, is described as `summation' or `adding up the entries in the list'.

A binary operator combines two values; I invariably construe it, via a process known as currie-ing (subject to spelling), as a mapping: given any a which the binary operator combines with anything, map it to the relation which relates b to c iff the binary operator combines a with b to produce c. If the binary operator combines a and b to yield a*b, the associated mapping, star, maps a to star(a) = (:x-> a*x:), which will be a relation in any case; it will be a mapping if * is unambiguous.


Among star's final values, we can perform composition: they're all relations. So pause to consider composition, which is a binary operator; construe it as the mapping ({relations}: r-> ({relations}: s-> r&on;s :) :). Composition is unambiguous, so all final values of this relation are mappings ({relations}|:{relations}).

Composition is associative. Proof: r&on;(s&on;t) relates w to z iff; s&on;t relates w to some y which r relates to z, iff; t relates w to some x which s relates to some y which r relates to z; iff t relates w to some x which r&on;s relates to z; iff (r&on;s)&on;t relates w to z: so r&on;(s&on;t) = (r&on;s)&on;t.

As composition is associative and unambiguous, its bulk action, which can be defined by: compose([]) = (:x->x:) - the universal identity - and, compose(1+n|f:) = compose(n:f:)&on;f(n), which makes compose([r]) = (:x->x:)&on;r = r (the prerequisite which enabled me to infer what compose([]) should be). This maps any list of relations to a relation - the composite of the entries in the list, `in list order'.

Note that, since compose([a,...,z]) should mean a&on;...&on;z, when (26|f:) = [a,...,z] - taking 26 as a nominal for `however many entries there are in [a,...,z]', and 25 as the nominal `one less than that' - and f = [f(0),...,f(25)], so we have a = f(0) and z = f(25), bulk(26|f:) = f(0)&on;...&on;f(25), I can define combine either via (1+n|f:) -> compose(n:f:)&on;f(n), as above, or (and this is fiddlier, which is why I used that one, above) as f(0)&on;compose(1+n:f&on;successor:). They `mean the same thing', given the value of compose([]), and compose's associativity.

This implies that the composite relates this to that iff z relates this to ..., which a relates to that; this mentions [a,...,z] in reverse order: getting used to this is the small price we must pay for retaining the familiarity of `when f is a mapping and x is one of its inputs, we write the corresponding output as f(x)' (and if we try writing it as (x)f, there's a whole dual set of complications, which haven't arisen with the present choice of ordering, to match the ones arising from the present `reversal', at least in English).

Before returning to the main thread, note also that composition is, at least nominally, `unusual' in that it can give a value to composite([]) - in general, the best bulk(*) can do, for a binary operator *, is bulk(*,[a]) = a, bulk(*,(1+n|f:)) = bulk(*,(n:f:))&on;f(n), which doesn't provide us with a value for bulk(*,[]) unless * has a unique left-identity (given a left-identity, right-cancellability (though not necessary) would suffice to imply uniqueness of the left-identity). Composition is not cancellable, either to left or to right; nor is it complete (likewise).

Written by Eddy.
$Id: scratch.html,v 1.1 2001-10-17 18:00:21 eddy Exp $