We can represent any binary operator * by the associated mapping star = (: (: a*b ←b :) ←a :), for which star(a, b) = a*b. The inputs to this mapping are left operands. The outputs are relations; when the binary operator is unambiguous, these outputs are mappings. This representation of a binary operator can thus be construed as an embedding of its left operands in {relations}; and we can consider how *, seen via that embedding, relates to &on;, the composition of relations.
Conversely, when we have any mapping ({relations}: star :), we can induce a binary operator % on its inputs by using &on; on its outputs: given inputs a, b to star for which star(a)&on;star(b) is an output of star, we can specify that each input that produces this output is a value for a%b; thus we use star(a%b) = star(a)&on;star(b) to define %. (Variations on the theme may involve each composite of outputs of star having non-trivial intersection with (or subsuming, or being subsumed by) at most one output of star, in which case one might define a%b to be any input to star that produces the relevant output for star(a)&on;star(b). I do something akin to this, for example, when developing relations to represent natural ratios.) Note that the associated mapping of % need not be star; some star(a) may relate some c to some b for which star(a)&on;star(b) isn't an output of star; or, even if it is, it might not be star(c); or it might also be star(d) for some d that star(a) doesn't relate to b. When any of these things happens for star derived from *, as above, % and * won't coincide; in the first case a%b isn't valid, in the second c is a value of a*b but not of a%b and in the third d isn't a value of a*b but is a value of a%b.
In the converse case, we explicitly only consider star(a)&on;star(b) when
the resulting composite is an output of star, thereby tacitly restricting &on;
to the outputs of star. In the prior case, we're only really interested in
composing star(a)&on;star(b) if *, from which star was induced, does in fact let
us combine a and b; and we'll then care about whether the composite actually is
an ouptut of star – in particular, whether it's star(a*b). In each case
we're thus dealing with a composition subsumed
by &on; but reduced from it; first by
restriction to the outputs of star and possibly further, either by whether *
was willing to combine the inputs that produced the outputs we're considering or
by whether the composite is another output of star. I'll refer to such a
reduced composition as a sub-composition
of &on;; when *
is flat, this shall indeed simply be a restriction of composition, but the
non-flat case may be reduced further than that.
When our binary operator is an
addition on some space V – e.g. of displacements in a Euclidean space,
or the addition between displacements and positions in such a space – star
gets called add
and a typical left value (a.k.a. output) is add(a) = (:
a+b ←b :), which can be thought of as translate through a
; so add
embeds V in the space of translations of V (or of an associated space,
e.g. embedding displacements in the space of translations of a Euclidean
space). While this example does have special properties not present for every
binary operator's associated mapping, readers may find it helpful to think in
these terms to get a grasp of the things I'll be doing with outputs of star,
below.
If star is monic, % is unambiguous. Otherwise there are some distinct a, b for which star(a) = star(b); i.e. for which a*c = b*c for all c (for which either a*c or b*c is defined). This is apt to make a and b indistinguishable as far as * and star are concerned, although there might still be some c for which c*a and c*b are distinct. When that doesn't happen, it's natural to identify a and b, for the purposes of discussing * and star, so that we end up using (: star |) as equality and effecitvely reducing star to be monic after all.
Because % is induced from composition of relations, which is associative, % is also associative, regardless of whether * was. When star is derived from associative *, star(star(a, b), c) = (a*b)*c = a*(b*c) = star(a, star(b, c)) = (star(a)&on;star(b))(c) for all c, so star(a*b) = star(star(a, b)) = star(a)&on;star(b) = star(a%b) for all a, b. This makes a*b a value of a%b for all a, b; so % subsumes * (in the sense appropriate to binary operators). When star is monic, this makes a*b = a%b for all a, b so that % is just * regenerated. In particular, when * is a combiner, there is some sub-composition of &on; on star's outputs that is closed and does induce * as % by composing star's outputs in this way.
For associative %, we can read star(a)&on;star(b) = star(a%b) as saying that
star is a homomorphism from % to &on; as binary operators; thus star represents
% by its homomorphic image as the
sub-composition of &on; on outputs of star that only lets it compose
star(a)&on;star(b) if % does combine a and b. (Even when * isn't associative, %
still is; so both star and its analogue derived from % (which needn't coincide
with star) are homomorphisms from % to &on;.) In the language of categories,
this (via the forgetful functor
which naturally embeds the
sub-composition in &on; unrestricted) makes &on; a final object of the category
of unambiguous associative binary operators under homomorphisms in the given
sense (in contrast to list-concatenation, which is
something like an initial object). In this sense, &on; serves as a universal
model for all combiners.
When star (derived from *) is a homomorphism from * to &on; (i.e. * is associative), every (allowed) composite of star's outputs is an output of star. This leads to a way to implement the bulk action of a combiner: bulk(%) = reverse(star)&on;bulk(&on;)&on;(: star&on;h ←h :) turns a list h of %'s operands into star&on;h, a list of star's outputs, which we then compose using bulk(&on;); reverse(star) then tells us which operand star maps to the composite. If star isn't monic, the result may be ambiguous, even if the naturally-defined bulk action isn't; but the conflated results are at least equivalent as far as (: star |) is concerned.
Given star = (: (: a*b ←b :) ←a :), its transpose is rats = (: (: a*b ←a :) ←b :), producing the same values but taking its operands in the reverse order, so rats(b, a) = star(a, b). When applied to mappings generated from binary operators in this way, transpose is self-inverse; transpose(rats) = star.
We could, in principle, take any relation s whose left values are relations and construe it as a binary operator * via (by analogy with how star works, above): a*b stands for any value c for which s relates some r to a and r relates c to b. (Note that s not being a mapping doesn't necessarily make * ambiguous; its left values might all be atomic relations, for example, and those related to a given right value might all have distinct left values.) We could then induce star = (: (: a*b ←b :) ←a :) from this as before; this would be a mapping, with star(a) = unite(: s :{a}) being simply the union of all relations that s relates to a. Note that empty left values of s get ignored (if s relates empty to a, this contribute no b*a candidates for any b), so star may lack some of s's right values. We still have relations as left values of star, i.e. its outputs, and any ambituity in * is expressed by these outputs not being mappings.
I mentioned above that transpose is self-inverse when applied to mappings
generated from binary operators; so now let's consider what its self-composite
does to the more general relation s of the preceding; transpose is a mapping and
each of its outputs is also a mapping; so transpose(transpose(s)) is a
mapping. Now, transpose(t, a, b) = t(b, a), so suppose transpose(transpose(s))
can accept some values a and b; it'll give us transpose(transpose(s), a, b) =
transpose(s, b, a) = s(a, b) which is just any value c for which s relates, to
a, some left value that relates c to b. Thus, in fact, transpose&on;transpose
is exactly the (: ({non-empty}: unite(: s :{a}) ←a :) ←s :) mapifying
that turned s into star. (This is, indeed, the mapping U, with the same
right-relation as transpose, that I use to
motivate collapsing mutual transpose-ness down to the
transpose.)
Any relation whose left values are relations can thus be interpreted as a binary operator; however, the mapifying via transpose&on;transpose reduces any such relation to a mapping whose outputs are non-empty relations (and any such mapping is a fixed point of the mapifying); and this mapping is the natural representation (see above) of the binary operator, so is the more usual form in which to represent any such relation, when discussed for the binary operator it generates.
When we've generated star from * as above and we read rats = transpose(star)
as a binary operator, @, this is thus specified by b@a = a*b; it is known as
the transpose
of * (extending terminology from relations
in a natural way to binary operators derived from them). Various properties a
binary operator may have can be stated directly in terms of its transpose, for
example a binary operator is commutative,
a.k.a. abelian, precisely if it is its own transpose. Other properties come in
left- and right- forms; commonly, one of these can be stated as a property of
the left values (outputs) of the binary operator's embedding and the other as a
matching property of left values of that embedding's transpose.
For example, we can specify that * is left-cancellable precisely
if star's outputs are all monic; right-cancellable precisely if
transpose(star)'s outputs are all monic; and cancellable
if both conditions hold true. This does indeed agree
with the usual specification of cancellability
on a flat binary operator; furthermore, its application to individual values
matches the corresponding properties of
a category, albeit these are named differently (an operand is monic
if it
can be left-cancelled and epic
if it can be right-cancelled).
Likewise, with V = {operands of *}, * is right-complete precisely if each left value of star is (V| :V) and left-complete if the same is true of star's transpose. A left-identity of flat * is precisely an operand that star maps to the identity on V; a right-identity is the same for star's transpose.
As noted above, when * is associative, star is a homomorphism from * to &on; as binary operators. Let's now look at r = transpose(star); we have r(a, b) = b*a, so r(a)&on;r(b) = (: r(a, r(b, c)) ←c :) = (: (c*b)*a ←c :) = (: c*(b*a) ←c :) = r(b*a), so (as should not be too surprising) we reverse the order of operands between r(a)&on;r(b) = r(b*a), making transpose(star) a cohomomorphism from * to &on;, rather than a homomorphism.
One binary operator, *, left-distributes over another, @, precisely if each left value of star is a binary operator automorphism of @; and * right-distributes over @ precisely if each left value of transpose(star) is an automorphism of @, likewise. Combining with associativity: * is asssociative and left-distributes over @ precisely if star is a homomorphism from * to composition on the automorphisms of @; and it is associative and right-distributes over @ precisely if transpose(star) is a cohomomorphism from * to this composition of @'s automorphisms.
As I describe when discussing bulk actions, we can use combination of n repeats of a value v to get bulk(*, ({v}: |n)), which scales v up by n. We can equally arrive at scalings by using repeats of the outputs of star. Thanks to the homomorphism above, star(bulk(*, ({v}: |n))) = bulk(&on;, ({star(v)}: |n)) = repeat(n, star(v)), so reverse(star)&on;repeat(n)&on;star subsumes (: bulk(*, ({v}: |n)) ←v :), with equality when star is monic.
We can use the reverse of scalings to implement scaling down
; when a
scaling is monic, this shall be a mapping; when a scaling is (V| |V) for some
collection V of operands of *, we are able to divide universally by the
scaling's natural. When both of these conditions are met for all scalings, we
can compose scalings with their reverses to obtain scaling by ratios of positive
naturals. This parallels the development
of positive ratios, so consider a positive
ratio m\n for comprime positive naturals n, m. When bulk(*, ({w}: |m)) =
bulk(*, ({v}: |n)), so repeat(m, star(w)) = repeat(n, star(v)) the definition of
m\n says that it relates star(w) to star(v). I thus define
Note that r&on;star may have some quite surprising left values, relations that may do strange things outside V, that none the less, when repeated m times (with m as r's denominator), give star(v) for some v in V. Composing reverse(star) after r&on;star weeds out these eccentricities, though.
When star isn't monic, scale(*, m\n) may relate w to v for some w, v for which bulk(*, ({w}: |m)) and bulk(*, ({v}: |n)) aren't equal; star does map these two to the same relation, though, so there's an important sense in which they're equivalent for *'s purposes. Fortunately, most interesting binary operators do have monic mappings to represent them in any case, if only because equivalence modulo (:star|), or something that subsumes it, is usually serving as equality on our operands.
Since scale(*, n) isn't guaranteed to be monic even for natural n, where it is at least a mapping if star is monic, a general positive ratio r has a relation as scale(*, r), that isn't necessarily either monic or a mapping. In particular, if any operand of * has non-zero order, there are naturals that scale it to make an identity; scaling (of values generally) by the inverse of such a natural shall then be ambiguous modulo the given operand with non-zero order (and thus by any result of scaling it), at least when * is commutative. Thus, if any operand has positive natural order i, reverse(scale(*, i.m))&on;scale(*, i.n) is ambiguous modulo scalings of that operand; however, this ambiguity is avoided even in scale(*, (i.m)\(i.n)), since the definition of positive ratios takes care to eliminate common factors; (i.m)\(i.n) = m\n and we'll only hit this ambiguity if, with m and n coprime, m is a multiple of i.
Thus, with V = {operands of *}, for any given positive ratio r, we have no guarantee that (V: scalr(*, r) :V) is (: |V), unless r is in fact (the ratio representing) some natural. If we have a second positive ratio s, the intersection of scale(*, r.s) and scale(*, r)&on;scale(*, s) shall not be empty, indeed one may subsume the other, but the two aren't necessarily equal; likewise, the intersection of scale(*, r\s) and reverse(scale(*, r))&on;scale(*, s) is non-empty and one may subsume the other, but they're not necessarily equal.
However, scale(*, r) and scale(*, 1/r) are each other's reverse; when each scalr(*, r) is (V: |V), this implies that each is in fact (V| |V). Better still, if each scale(*, r) is monic (V: |V), each must also be a mapping (V| :V), hence an iso (V| |V). In this case, we do in fact get scale(*, r.s) = scale(*, r)&on;scale(*, s) and similar for r\s; thus scale(*) is a homomorphism from the multiplication on ratios to the composition of scalings. (This is not so remarkable, though: the multiplication of natural ratios is a composition of relations, albeit with some canonicalisation after.) When * is also abelian, each scale(*, r) is furthermore a binary operator automorphism of * (thanks to this arising for each scale(*, n) for each natural n).
The important result of all of this is that we have a well-defined scaling by positive ratios for any binary operator and can then ask whether that scaling behaves nicely: when it does, our binary operator is a candidate for being the addition of a linear space over the positive ratios, using the given scaling as scalar multiplication.
Written by Eddy.