A mapping, f, accepts inputs and produces outputs; the outputs may,
themselves, be mappings; in such a case, let a be an input accepted by f and b
an input accepted by f(a); the resulting output is called f(a,b) which might
also be written (f(a))(b). In this sense, f combines two things, a and b, and
produces a third, f(a,b). One may continue, so long as f(a,b) is a mapping, to
f(a,b,c) combining three values; and so on ad nauseam. However, many
situations arise where f(a,b) is of the same kind as
a and b in some sense
which allows f to accept f(a,b) as an input, thus allowing f(f(a,b),c) and
similar constructions. In such situations, it is common to introduce a symbol,
e.g. *, and denote f(a,b) in the form a*b. Where a context defines such a
denotation, * is known as a binary operator.
The most familiar binary operator must surely be + in use to denote addition; however, this posesses some very strong properties not shared by all binary operators, so I'll give a moderately more ordinary example:
When I plan a journey, I break it down into parts: I
cycle from home to the railway station; I take a train from Cambridge to (say)
Peterborough; I take a different train from Peterborough to near my destination;
and so on. Each part is a journey; they are combined with one another to form a
journey; in this sense, and then
may be thought of as a binary operator
on journeys.
Like most (but perhaps not all) interesting binary operators, it's
associative: doing the first two steps, then the third
is the same
as
doing the first step, then the next two
. Unlike addition (but
like many other binary operators) the fact that I can combine two journey
fragments in one order, J and then K
, need not mean that I can combine
them in reverse order: I catch a train from Cambridge to Peterborough and
then I cycle from home to the railway station
doesn't make sense (my home
isn't in Peterborough). Even when the reverse does make sense, it need not mean
the same as the original; I ride to work and then I ride home
isn't the
same journey as I ride home and then I ride to work
; one leaves me at
home, the other at work.
My plan will only be concerned with certain overall effects - how soon must I leave, when shall I arrive, shall I have had an opportunity to do anything I must along the way (e.g. buy a present for whoever I'm visiting, or pick up the keys to where I'm going) and so on. In so far as two sequences of journey fragments have the same overall effect, I shall consider them equal, though they might involve different fragments (e.g. there are several waits in the journey during which I may have an opportunity to buy that present; this might even affect what present I end up buying, so long as the plan doesn't care about the difference - any suitable present will do).
If two equal sequences of journey fragments start or end in the same
fragment, I can leave off this common fragment of each to obtain a pair of equal
sequences, in the eyes of my plan. In this sense, and then
is
cancellable, in the same way that x+7 = 3+7 implies x=3 by cancellation.
However, journey fragments take up time (and never negative amounts of it): my
plan cares about time, so journey fragments don't have inverses
; given
J and then K
equal to J and then H
, we infer K=H without needing
the analog of -7 used in x = x+7-7 = 3+7-7 = 3; we can do cancellation, but we
don't (generally) have inverses
for journey fragments.
I chose to extend the usage of binary operators to embrace relations as well
as mappings: if f is a relation and its left values (corresponding to a
mapping's outputs) are themselves relations; context may associate f with a
binary operator, say *; then an expression of form a*b asserts that f relates
some relation, r, to a, that b is in (:r|), ensuring that r relates some value,
c, to b; and this expression a*b ambiguously denotes any such c
. Thus f
relates r to a, r relates a*b to b and a*b denotes any c for which *'s
relation relates, to a, some relation, r, which relates c to b.
When f is a mapping whose outputs are mappings, this collapses down to the conventional case and there is exactly one value a*b can denote, f(a,b). It is also possible, when f is a relation whose right values are relations, for f(a,b) to be well-defined - f may relate many r to a, so long as the union of all such r only relates one value to b (though it may relate several values (each) to some value(s) other than b).
In the fully general case of a relation whose left values are relations, consider a right value, a in (:f|), and look at unite(|f:{a}). This is a union of some of f's left values (those f relates to a) each of which is a relation; this union relates c to b iff there is some r in (|f:{a}) which relates c to b, i.e. iff c is one of a*b's possible values. Thus unite(|f:{a}) coincides with the relation a*b←b. We are thus lead to a mapping, (a*b←b)←a, whose left values are relations; if we construct the binary operator induced by this mapping it necessarily coincides with *. Thus when a relation, e.g. f, is used to define a binary operator we can reason about the binary operator as if unite(|f:{a}) ←a had been used in place of f.
For a general relation, f, transpose(f) is a mapping whose transpose is unite(|f:{a})←a, which will be f precisely if f is a mapping whose outputs are all non-empty relations. When f is used to generate a binary operator, *, we can write unite(|f:{a}) as a*b ←b, as above, so (a*b←b)←;a is transpose(transpose(f)); since transpose(f) is a mapping (and its outputs are non-empty), it is equal to transpose(transpose(transpose(f))), which is transpose((a*b←b)←a), making it (a*b←a)←b. Thus transposition of the underlying relation (whose left values are non-empty relations) corresponds directly with swapping the two values combined by the associated binary operator.
A binary operator which coincides with its transpose is described as abelian
or commutative. Addition is commutative, but (as discussed above) the and
then
binary operator on journey fragments isn't. For non-abelian binary
operators, it is often interesting to compare a*b and b*a, in so far as both are
meaningful.
What really semms to matter, for a binary operator * with associated star = (a*b←b) ←a, is when any composition of outputs of star is an output of star. That says: given a, w in (:star|), star(a)&on;star(w) is in (|star:).
As illustrated by my example with journey fragments, a binary operator may
be fussy about what it will combine. This can make for some very fiddly
definitions (see potential factors, below). On the other hand, some properties
of binary operators only make sense when less fussiness is involved. To this
end, I'll describe a binary operator, *, as uniform precisely
when, for any valid a*b, there is a collection U of which a and b are members
and for which, for every u, v in U, u*v is also in U.
If the collection U depends on our choice of a and b, I'll describe * as
layered uniform
; if not, as strictly uniform
. (For example,
addition may be defined between vector quantities, between scalars and between
linear maps; in each case it is uniform, but one cannot add scalars to vectors,
so addition is layered uniform.)
In a similar vein, I'll describe a binary operator, *, as cartesian precisely if there are collections A, B for which the associated mapping is (: (: a*b ←b |B) ←a |A), i.e. for every a in A and every b in B, a*b is valid. One can then express * as a mapping whose inputs are pairs [a,b] with a in A and b in B; the mapping maps each such [a,b] to a*b.
Given a binary operator * and its associated mapping, f =
(a*b←b)←a), I'll refer to the members of (:f|) as (valid) right
operands
of *, to the members of (: unite(|f:) |) as left operands
of
* (these are the a for which there is some b for which a*b is valid) and to the
members of (| unite(|f:) :) as the results
of *. In these terms, a
binary operator is cartesian iff it will combine any left operand with any right
operand.
Given a binary operator, *, and some values for which a*c = b*c we can guess
that a and b are equal: but, in general, we can't be sure. When * guarantees us
that we can infer a=b from a*c = b*c, this inference is described as
canceling out
the *c from both sides of the equation; the same turn of
phrase is used to describe inference of a=b from c*a = c*b. I'll distinguish
these (only slightly different) cases according to whether c, the value
cancelled, appears on the right or the left: I'll describe * as left
(respectively: right) cancellable precisely if c*a = c*b
(respectively:
a*c = b*c
) implies a=b. If it is both left- and right-cancellable, I'll
simply describe * as cancellable.
Given a binary operator, *, and two values, a and c, we may be interested in finding a value, b, for which a*b = c or b*a = c. When we can find such b, questions of cancellability will tell us whether it is the only b or whether there may be several, so the remaining question of interest is whether such b exists for every (sensible) choice of a and c. Specifying which choices of a and c are sensible is nice and easy if * is cartesian but requires slightly more care in the more general case. The case where it matters is really when a sequence of values is combined by the bulk action of the binary operator: if c appears in such a sequence, can we replace it with two entries, one of which is a, the other to be determined, b ? Thus solving for b in a*b=c is only sensible if u*a is meaningful whenever u*c is meaningful.
I'll describe a as a potential right *-factor
of c precisely if (:
c*u ←u |) subsumes (: a*u ←u |), i.e. any value you can multiply on
the right of c can equally be multiplied on a's right. I'll describe * as
left-complete iff: a is a potential right *-factor of c
implies c =
b*a for some b
. Likewise, a is a potential left *-factor of c iff
(:u*c←u|) subsumes (:u*a←|) and * is right-complete iff: a is a
potential left *-factor of c
implies c = a*b for some b
. I'll
describe * as complete iff it is both left-complete and
right-complete.