In general, a binary operator, say *, takes two values, say a and b, which
it combines to give b * a. [Note: not to be confused with binary predicates
,
e.g. <, =, > and sometimes ~, which are relations denoted by infix
operators.] Mathematics commonly deals with situations where z * ... * a
makes equally good sense, which turns the binary operator into a way of reducing
a list of values, [z, ..., a], to a single value. This is equally something
that integration will do to a suitable mapping (I| f :{values}), which leads to
discussion of binary operators in terms which reduce a function to a value,
typically of the same kind as
the values the function produced as outputs.
The list [z, ..., a] is just a special kind of function (it's inputs are the
indexes into the list, each producing the appropriate entry as output: it maps 0
to a, for instance, and 25 to z if the list really has 26 entries).
With any binary operator, *, we may associate a mapping,
so that star(a,b) = a*b and star(a) is a mapping for each a. This
mapping fully describes the binary operator and may be construed as an embedding
of (|star:) in {mappings}: each value of the kind you were combining is
represented by a mapping; the structure of the binary operator may then explored
by studying the effect of composition among these mappings (see Associativity, below). This approach to binary operators
takes composition
as the model binary operator which describes all others.
Where orthodoxy gives me a structure, such as binary operators, I naturally
pause to consider what happens if I substitute relation
in some of the places
where the orthodoxy gives me mapping
or collection
. In the present case,
mappings whose outputs are mappings, it is natural to look at relations whose
final values are relations. Where, before, we had one value to look at, we may
now expect to see several. In the mapping form, a*b stood for some value to
which star(a) maps b; once the special language of mappings is stripped away,
along with the assertions of uniqueness that make that language meaningful, we
are left with a*b stands for some value c for which star relates a to some s
which relates b to c
.
If star is taken to be a relation whose final values are relations, we can
still use this reading of * as a binary operator, but a*b may now be ambiguous:
there may be several candidate values for it. I'll describe such a * as an
ambiguous binary operator
to distinguish it from the more conventional form.
With this potentially ambiguous reading of *, I can still construct
and compare it with star. Now, T is a mapping: for each a, T(a) = (:
b-> a*b :) is a relation: it relates b to c (candidate for a*b) precisely if
there is some s in ({a}: star |) which relates b to c; from the definition of
unite, this says T(a) = unite({a}: star |), except that T rejects any a for
which this would be empty. Although star may relate a to several relations, T
simply maps a to their union. Thus even an ambiguous binary operator admits of
representation by a mapping, though it now gives us a relation to represent each
of the values
that the binary operator combines. We may still have relations
among T's outputs, but at least T is a mapping and composition among its outputs
can be used to model * among its inputs.
So, instead of studying binary operators
, I'm really going to consider
what happens when we represent some population of values using some population
of relations: mayhap those relations will usually be mappings. So what happens
if I just consider a mapping whose outputs are relations without presuming that
it is the representation of a binary operator ?
So now we don't have * but we do have a mapping whose outputs are relations; call it rats and let V = (|rats:) and don't assume {(V::V)} subsumes, or even meets, (:rats|). We can presume that rats is a mapping: in any case, we can construct
which is a mapping from V to {relations (V::V)}, so we can read it as a binary operator * with associated mapping (V|star:{(V::V)}): star(a) relates b to c precisely if rats(c) = rats(a)&on;rats(b); i.e. rats(a)&on;rats(b) = rats(a*b). Note that a*b may be ambiguous, but rats(a*b) isn't. Ambiguity in * may arise from rats producing some of its outputs from several inputs (or from rats being a relation, but not a mapping, whose final values are relations). Thus any time we represent values as relations, we can transform the given representation into a binary operator: the only such representations we need to consider are thus the ones one infers from binary operators.
We can equally apply the same construction to star to get a binary operator, call it % for now, defined by star(a%b) = star(a)&on;star(b) or, considering what this relates any given c to, (a%b)*c = a*(b*c). I now proceed to explore what happens when star is induced from a binary operator, *, and coincides with the inferred %.
A binary operator * is described as associative precisely if c * (b * a) = (c * b) * a for every choice of a, b, c for which both sides are defined.
Reading * in terms of its associated mapping, star, we can compose star(b) before star(c) to get c * (b * a) as (star(c)&on;star(b))(a), at least in so far as star's outputs are mappings. Associativity asks for this to be equal to (c * b) * a which is star(c * b, a) or star(star(c, b), a). We're giving arbitrary a as input to each of two mappings and getting the same output; so in fact the two mappings star(c)&on;star(b) and star(c * b) must be equal.
When star's outputs aren't known to be mappings, but are relations, we can interpret associativity as asserting equality of { c*(b*a) } and { (c*b)*a }, the collections of values the ambiguous binary operator may yield for the given a, b, c. We can write { c*(b*a) } as ({a}: star(c)&on;star(b) |) and { (c*b)*a } as ({a}: unite({ star(c*b) }) |) and their equality for all a implies equality of star(c)&on;star(b) and unite({ star(c*b) }). Note that, for an unambiguous binary operator, unite({ star(c*b) }) is simply star(c*b): the use of unite({ ... }) is needed to account for the several values c*b may take, hence several relations to which star will map these; we need to relate a to d precisely when some value of c*b gives us star(c*b) which relates a to d, which calls for the union of the several relations star(c*b) may denote. We can also write { star(c*b) } as ({b}: star&on;star(c) |); and note that the natural way to extract a mapping from a relation, r, at least when all final values are relations, is ((|r): b-> unite({b}: r |) :), so we can express associativity as (: b-> star(c)&on;star(b) :) is the mapping to which star&on;star(c) naturally reduces (which will be itself if it is a mapping, given that we know its outputs are relations). Either way, the ambiguous case is not greatly misrepresented by the unambiguous case's handy slogan for what associativity requires:
Reading associativity as combining values with * then passing the result
through star
giving the same answer as passing each through star and combining
the results with &on;
, associativity takes the composition, &on;, of relations
as its model binary operator. The associated mapping compose is given by
which relates a to b precisely if ({a}: s |) meets (| r :{b}), i.e. there is some i (in the intersection) for which s relates a to i and r relates i to b.
Consider r&on;(s&on;t). It relates w to z precisely if there is some
member, y, of (| r :{z}) which is also in ({w}: s&on;t |); the latter arises
precisely when ({w}: t |) meets (| s :{y}). Let x be the member in which those
meet and notice that: t relates w to x, s relates x to y, r relates y to z.
Thus r&on;(s&on;t) relates w to z precisely if some x and y complete this chain.
[Pause to notice that natural language's conception of this chain contains the
implicit intuition that the logical operation and
- implicitly used to combine
the three statements in the chain - is associative.] The chain is independent
of the bracketing and, indeed, one can easily show that (r&on;s)&on;t demands
exactly the same chain. Consequently, compose(a)&on;compose(b) = ({relations}|
c-> a&on;(b&on;c) = (a&on;b)&on;c :{relations}) = compose(a&on;b), and
composition is associative.
I can define a mapping, bulk, from binary operators to list-reduction
operators as: bulk(*) maps [a]-> a, (2+n|f:)-> f(1+n)*bulk(*,(1+n:f:)).
One may think of bulk(*) as the action of * on lists of arbitrary positive
length: it gives meaning to z * ... * a
as bulk(*, [z, ..., a]) = z * (y * ...
* (b * a)...). If * has a unique right-identity (see below), bulk(*) can map []
to this, but generally bulk(*)'s only initial values are non-empty lists of
members of (|star:). We can write f(n)*bulk(*,(n:f:)) as
(star(f(n))&on;bulk(*))(n:f:) and inductively obtain
Note that this introduces f with an assertion that (|f:) = 2+n for some natural, i.e. is at least 2: it must be at least one to allow f(0) to appear on the right; the at least one more is there to ensure that (1+n| i-> star(f(1+i)) :) = star&on;(1+n| i-> f(1+i) :) = star&on;f&on;successor is non-empty (despite leaving out f(0)'s entry in star&on;f) which is the standard precondition for passing it to bulk(&on;): if (|f:) were only 1, star&on;f&on;successor would be empty; but &on; does have a right-identity, the universal identity, x-> x, which we can use as the value for bulk(&on;, []), thus extending the above to
Now, consider any associative binary operator, *, with associated mapping,
star. We have bulk(*) as a reduction from non-empty lists to values
(typically of the same kind as
the entries in the list) and there is a natural
binary operator on lists which combines [z,...,n] with [m,...,a] to give
[z,...,n,m,...,a]: write this as @ with associated mapping then
, notice that
it is associative (because addition of naturals is), and consider non-empty
lists f, g which bulk(*) accepts: we have meanings for bulk(*,f@g)
and bulk(*,f) * bulk(*,g) and we'll soon see they are equal.
First observe that when the length of f@g is at most 3 we already know that the
two are equal [Proof: as both f and g are non-empty, the shortest f@g can be is
2, making the result trivial as bulk(*,[f(0),g(0)]) = star(f(0),g(0)) by
definition; otherwise, the length is 3, one list is of length two, the other is
a singleton and we have the definition of associativity].
So, consider any natural n (e.g. 3) for which: all non-empty lists f, g for which the length of f@g is at most n satisfy; bulk(*,f@g) = bulk(*,f) * bulk(*,g). Consider some non-empty lists f, g with total length 1+n. If f is a singleton, [F], we obtain bulk(*,[F]@g) = F * bulk(*,g) = bulk(*,f) * bulk(*,g). Otherwise, f = [F]@e for some non-empty list e: and g is non-empty so f's length is at most n, so bulk(*,f) is F * bulk(*,e); while e@g is non-empty so bulk(*,e@g) = bulk(*,e) * bulk(*,g) and
but * is associative so this is
Given the required result for some given n, we have now obtained it for 1+n so, inductively, we have the given result for all n (note that it is trivial for n = 0 or 1 as no non-empty lists meet the condition).
We now know that bulk(*,f) * bulk(*,g) = bulk(*,f@g) whenever *
is associative. Using this, any bracketing of z * ... * a
(not just the one
treated as implicit, by the definition of bulk(*), when no bracketing is
given), reduces to a bracketing of [z] @ ... @ [a]
and all such are equal to
[z, ..., a], so every bracketing of z * ... * a
yields bulk(*,[z, ..., a]).
Consequently, z * ... * a
is meaningful without any bracketing provided * is
associative. In particular &on; is associative, so bulk(*,f) &on;
bulk(&on;,g) = bulk(&on;,f@g), and any bracketing of a composition of
relations will give the same composite.
Thus an associative binary operator corresponds exactly with a list-reduction operation with the same structural form as composition of lists of mappings (or, indeed, of relations).
Having construed a binary operator as a mapping whose outputs are mappings,
I naturally turn to consider relations whose final values are relations: these
provide the natural model of three-entity relations
in terms of the
two-entity
relations which I've chosen as my implementation language
; one
might also call them ternary predicates. Such a relation, r, when read as a
ternary relation, says yes to
values x, y, z precisely if r relates x to some
s which relates y to z. I can construct a mapping flatten = (: r-> ((|r:):
x-> unite({x}:r|) :):) which maps relations to mappings - and if the final
values of a relation r are all relations, r and flatten(r) read as
the same
ternary relation. So although the natural generalisation of a mapping which
produces mappings is a relation whose final values are relations, the latter
can, in practice, be reduced to a mapping which produces relations.
Given a relation, star, whose final values are relations I can associate a binary operator, *, with star: an expression of form x*y
and so may be ambiguous. One can write flatten(star) as (: x-> (: y-> x*y :):), noting that (for given x), the output (: y-> x*y :) is a relation - it won't be a mapping unless x*y is unambiguous for each y. This makes rarer the need for explicit mention of flatten.
The appropriate generalisation of associativity is now simply that, for each x, y, z, the collections of values { z*(y*x) } and { (z*y)*x } coincide. This may be written star(z)&on;star(y) = unite({ star(z * y) }) in which unite({ star(z * y) }) is equally unite({z*y}: star |) and I'm highly tempted to just write it as star(z*y), like it was when we were dealing with binary operators. We can use entirely similar arguments to those given above to extract a reading of star as a bulk action; and to express this bulk action entirely in terms of the bulk action of &on; applied to list of the relations in (: flatten(star) |).
The discussion of list-reduction needs to be separated off from that of the
binary operator (cancellability, completeness, identities, inverses,
distributivity) with associativity as the pivot. This is in line with a general
revolution needed: foundation
needs to become the ground with the naturals and
lists split off as the first structure - the skeleton. I shall, of course, need
to cross-refer between that skeleton and the discussion of binary operators, at
least in so far as list-append is a binary operator if vital importance to the
study both of lists and of binary operators (and how they beget bulk action).
pulls composition back throughstar iff,
Look at the sub-relation of composition defined by restricting the inputs to S = (:star|), namely (S: s-> (S: r-> s&on;r :):). If all composites of members of S are, in turn, members of S we can take any composite star(a)&on;star(b) and know that there is some c in A for which star(c) is the given composite; so we can define rats = (A| a -> (A: star(a)&on;star(b) = star(c), b -> c :A) :). As defined, rats is a mapping and its outputs are relations (A::A). It will be interesting to study the conditions under which they, or their reverses, are mappings; and when (:rats(a)|) or (|rats(a):) is all of A.
We can perform this construction even when star's outputs aren't (A|:A), just so long as they are relations (or mappings, or collections, of course) and S is closed under composition. subsumes is a central structure within unite and intersect.
So what can we do with binary operators, other than extend them to serve as
bulk action on non-empty lists ? We can use them to combine values; we can
examine how the composite varies in response to variation in either of the
inputs, either keeping the other fixed or varying it in some manner carefully
correllated with the first; we can form equations between expressions which use
the binary operator to combine values, and study the way such an equation
constrains the relationships among the values combined; we can use repeated
combination to induce a multiplicative
action of positive integers on the
values
One common flavour of binary operator is a mapping (A| star :{(B|:C)}) in
which each star(a) accepts the same inputs (but note that clean composition
of
relations doesn't behave like this): that is, (A| a-> (| star(a) :) :) is
constant. In such a case, especially when B is C, star is described as an
action
of A on B, producing answers in C: and (B| transpose(star) :{(A|:C)})
is an action of B on A, likewise. When B is C, each star(a) is (B|:B) so the
compositions in bulk(*,f@[a]) = bulk(&on;, star&on;f, a) are all
clean for every (natural|f:A), with bulk(&on;, star&on;f) being (B|:B) in
turn. When A, B and C are all equal, I'll describe star as a
uniform binary operator.
At the opposite extreme, we can express any binary operator star as (A: :{(A::A)}) with A = unite((|star): a-> (|star(a):)&unite;(:star(a)|) :{collections}) &unite; (|star). For example, clean composition is of this form with A = {relations} but {relation (: :a)} = {relations cleanly composable before a} depends on a.
If we take a uniform (A| star :) and some D which A subsumes, we can examine (D| d-> (D: star(d) :) :{(D|:A)}), the restriction of * to D. In principle it produces d * e in A for given d, e in D: if all such values are actually in D, we describe D as closed under *. This amounts to saying that (D| d-> (D: star(d) :) :) is, in fact, (D| :{(D|:D)}), hence uniform on D.
The definition of transpose on relations makes transpose(star) the mapping
b-> a-> a * b, where star is a-> b-> a * b. If a binary operator's
mapping is equal to its transpose, the binary operator is described as
Abelian or commutative: this says that a * b =
b * a for all a, b. Even when * isn't commutative, there may be some a, b for
which a * b = b * a: in such a case, a and b are said to commute with
one
another under star
.
Given topologies on A, B, C we can infer one on {continuous (B|:C)} and thus obtain the notion of continuity for mappings (A| :{continuous (B|:C)}). I'll describe a binary operator (A| :{(B|:C)}) as continuous if it is, indeed, continuous (A| :{continuous (B|:C)}).
I'll describe a binary operator star as left-cancellable precisely if star(a,b) = star(a,d) implies b = d: this just says that star(a) is monic or (: star |) is subsumed by {monics}. I'll describe star as right-cancellable precisely if star(a,b) = star(c,b) implies a = c: equivalently, transpose(star) is left-cancellable. Note that star can be monic without being right-cancellable (consider multiplication on the naturals, with a.0 = c.0 for any a, c), but any right-cancellable binary operator is, incidentally, monic. I'll describe a binary operator as cancellable if it is both right- and left-cancellable. Thus star is:
I'll describe an action * with associated mapping (A| star :{(B|:C)}) as right-complete precisely if each star(a) is (B||C), aka epic (B|:C). This says that for each c in C there is some b in B for which a*b = c. To put this another way, each a in A has (: star(a) |) =C. I'll describe star is left-complete precisely if its transpose is right-complete. I'll describe star as complete precisely if it is both left- and right-complete. In summary, (A| star :{(B|:C)}) is:
Note that completeness is only defined for an action: it says that it
produces all of C as a * something for each a in A and as something * b for each
b in B. Cancellation, on the other hand, is well-defined for any binary
operator. This is related to loose duality between epic and monic ... It
should be noted that, in the given loose sense, left-cancellable is dual to
right-complete and right-cancellable is dual to left-complete. Thus I now go on
to consider what happens when we combine one of these properties with its
dual
, in this loose sense.
A left-cancellable right-complete binary operator's solutions to equations of form a*x=c, for given a and c, are unique. [Proof: let b, d be two solutions: then a*b=c=a*d. Left-cancelling a from a*b=a*d yields b=d.] Likewise, a right-cancellable left-complete binary operator's solutions to x*b=c are unique and a complete cancellable binary operator solves its equations uniquely.
For a binary operator (A|star:{(B|:C)}), an element a of A is called a left-identity for star precisely if star(a) is the identity on B (in which case B is necessarily a subset of C). Likewise, for (A|star:{(B|:C)}), b in B is a right-identity if transpose(star,b) is the identity on A. For (A|star:{(B|:C)}), e is an (unqualified) identity if it is both a right-identity and a left-identity - in which case, C subsumes the union of A and B and e is in their intersection (and thus in C). Thus, for (A|star:{(B|:C)}):
If a binary operator has both a left identity and a right identity, then they must be equal (and, thus, an identity): let them be l and r, respectively. We know that: since l is a left identity, l*r=r; but since r is a right identity, l*r=l; whence l=r. Consequently, a binary operator can have at most one identity (though, in principle, it may have several left identities as long as it has no right identities: and vice versa).
Elsewhere binary operators are central players in discussions of associativity (whence groups) and distributivity, both of which show up when we come to consider scalars and vectors. Binary operators are themselves fore-shadowed in the discussion of arrow worlds and categories, in which composition appears as a binary operator on arrows or morphisms.
Written by Eddy.