There are various ways, in mathematics, that we combine values to produce
values. The conventional idiom for describing this is a binary operator
- which combines two values to produce a third. An example I'll be using
extensively is the composition of relations: r&on;s relates x to z iff r relates
x to some y which s relates to z; &on; is thus a binary operator which combines
relations to yield relations. However:
To deal with the former, it is conventional to specify a property,
called associativity
, which says that: combining many values can be done
by taking (adjacent) pairs from among the many, combining those, thus reducing
how many remain to be combined, ultimately down to a single value; and that the
result doesn't depend on the various choices (which pair to combine at each
stage) we made. The slogan for associativity is: (a*b)*c = a*(b*c).
One then deals exclusively with associative binary operators: rather begging
the question of why we didn't start out with associativity built into the notion
of binary operator to begin with. The natural mechanism for doing this is
simply to replace the binary operator with a mechanism for reducing a list of
values to a single value: a*b is then bulk(*, [a,b]) and a*...*z is bulk(*,
[a,...,z]). [I think this approach corresponds to what some folk mean when they
talk about monads
but you'd have to check The Literature for that.]
Now, list-reduction is but one of the other ways of describing how we
combine values
alluded to above. Given a binary operator * and a left
operand, a, we can infer a mapping (: a*b ←b :) which we can describe as
combine a to the right of
; we can then characterise * by the mapping (:
(: a*b ←b :) ←a :); call this mapping star. Since the outputs (left
values) of star are all relations, we can compose them: star(a)&on;star(b) = (:
a*(b*c) ←c :). We can ask whether the composite is an output of star -
associativity is then phrased as star(a)&on;star(b) = star(a*b) and, equally, we
can induce a binary operator from * which combines a and b to produce that d for
which star(a)&on;star(b) is star(d), whenever there is such a d; because &on;
is associative, this induced binary operator will necessarily be
associative; and when * is associative, the induced binary operator
is *.
Conversely, any relation whose left values are relations can be used in the rôle of star: given ({relations}: star :), we can define a list-reduction operation (whose action on lists of length two we can construe as a binary operator) by reverse(star)&on;bulk(&on;)&on;(: star&on;h ←h :), the inputs to which are lists of star's right values. Such a list will only actually be a right value of the list-reducer given when: replacing each item in the list with a corresponding left value of star gives a list which, when composed, using bulk(&on;), yields a left value of star (so that reverse(star) will relate it to some right value of star). Furthermore, the list-reducer given will in general be a relation (unless star is a monic mapping). However, when star is the mapping (: (: a*b ←b :) ←a :) induced from some (unambiguous) associative binary operator, the list-reducer thus obtained coincides with a*...*z ← [a,...,z], so it's just the same thing we always played with.
Thus, in place of binary operators
I shall discuss relations whose
left values are relations, using composition to combine left values, thereby
providing, implicitly, for combination of right values. This covers all
conventional binary operators while leaving enough generality to express various
kindred notions in the same terms.
With conventional binary operators, one needs to be able to build up the
structures orthodoxy calls group
, ring
and field
;
naturally, I must indicate which details of relations whose left values are
relations
correspond to the relevant characteristics of binary operators.
Given that I'm never interested in non-associative binary operators, I'll
describe what each property of an associative binary operator becomes when
expressed as above.
In so doing, I'll re-arrange the notions which make a group: in place of
has an identity and inverses
, I'll discuss cancellation and the existence
of solutions to simple equations. If a*b = a*c implies b=c
, we can
describe * as left-cancellable; likewise right-cancellable if a*c = b*c
implies a=b
; and just plain cancellable iff both. If, for every a and b,
there's some x for which a*x=b and some y for which y*a=b, we can describe * as
complete
. Left-completeness (i.e. y*a=b for some y) combined with
right-cancellation (whence y*a=b=z*a implies y=z) makes completeness' solutions
to equations unique; likewise with left and right swapped.
A cancellable, complete binary operator other than empty necessarily forms a
group (and I am inclined to like the view of empty as the trivialest group;
albeit the familiar group {i} under binary operator i*i=i is also trivial - and
conveniently has {} as a sub-group). Given that one cannot specify the
existence of inverses without specifying the existence of an identity, the two
properties conventionally making up a group aren't orthogonal
(much as I
argue above that associativity isn't really a separate matter from binary
operator
); while cancellability and completeness are.
For example, the addition on positive integers is cancellable, even though
no inverses - nor even an identity - are available by which to describe the
operation orthodoxly; yet cancellation in this context works just the same way
as it does in a group (albeit because we can embed the positive
integers in the group of integers). Likewise, various constrained forms of
completeness are available when combining linear maps on a vector space (even
though cancellation isn't reliable) and when combining linear maps on various
vector spaces (for which no universal identity is available, yet some of the
linear maps do have inverses). It thus seems more appropriate to discuss
cancellation and equation-solving (which are, in any case, the jobs we wanted
inverses to deliver for us), subject to straightforward constraints, than to
discuss the various replacements for identity and inverses
that
proliferate and multiply when one tries to describe general mathematical
structures.
A ring is then an additive group with a multiplication which distributes over addition and is cancellable except when the value to be cancelled is the additive identity; a field is a ring whose multiplication is, furthermore, complete subject to an exception for the additive identity (a mustn't be 0 unless b is). Meanwhile, the positive rationals (or the positive reals) form a multiplicative group with a (fully) cancellable addition (over which the multiplication distributes), which does somewhat incline me to discuss this combination of properties, rather than the ring and field - although addition's completeness is constrained, the constraint is exactly the specification of the order on the rationals (or reals).
In the following, I'll suppose we have ({relations}: star :) from which we've induced
with join([a,b]) filling the rôle of a*b and the archetype for star being (: (: a*b ←b :) ←a :).
What does cancellation mean when we're dealing with a binary operator
obtained, as above, from a relation ? For left-cancellation, a*b = a*c implies
b=c, we're effectively insisting that star(a) is monic. For right cancellation,
a*c = b*c implies a=b, we need: if star(a) and star(b) agree anywhere, they must
agree everywhere. (Note that I'm here tolerating star(a)=star(b) as good
enough
in place of a=b, given that we can always read the discussion modulo
star's right-equivalence which treats star(a)=star(b) as if it really said a=b.)
We can express the right-cancellation property by saying transpose(star)'s
left values are all monic, analogously with the left-cancellation property;
however, the given if they agree anywhere they agree everywhere
description of right-cancellation is instructive. It'll also fit in (once I get
to playing with some generalisations) with cases where if two left values of
star have non-empty intersection, their union is a mapping and (|star:) relates
them to one another (and to this union)
.
So cancellation (modulo star's left and/or right equivalence, as appropriate) becomes the requirement that star's left values be monic and any two of them are either (|star:)-equivalent or disjoint.
Exceptions to cancellation, e.g. 0×b = 0×c doesn't imply b=c, will involve (|star:) having an exceptional member (well, equivalence class); indeed, in the easy cases, star has a constant left value and all star's left values agree on one of their right values but no two (unless (|star:)-equivalent to one another) agree about any other right value. [There are messier cases; if we consider multiplication on the integers reduced modulo some composite, p.q, then we get distinct star(i.q) for i in p but all of these agree on p, mapping it to 0.]
When star is in its archetypical form:
epic- the notion dual to monic.]
More generally, however, a*x=b says star(a)&on;star(x) = star(b); likewise left completeness involves star(y)&on;star(a) = star(b). This gives a much neater expression of completeness: every left value of star (e.g. star(b)) can be factorised via any left value (e.g. star(a)) of star, either as the left or right factor, with the other factors all being left values (e.g. star(x), star(y)) of star.
Again, exceptions will naturally arise as left values of star for which this doesn't work: and the cases that come to mind are more specific - the exceptional left value, z, satisfies z&on;f = z = f&on;z for every left value, f.
The simplest thing we can do with a binary operator is to swap its operands:
for any binary operator, *, there is an associated binary operator, call it @,
defined by a@b = b*a and known as the transpose of * (because,
when we construct the associated relations, they are indeed one another's images
under the transposition natural to relations whose left values are relations).
A binary operator, *, is described as Abelian iff it is equal
to its transpose - i.e. whenever * will combine a, b as a*b or as b*a, it will
also combine them the other way, producing the same answer in each case: a*b
= b*a whenever either makes sense
.
Describing the binary operator in terms of its action on lists,
Abelian
just says that arbitrary permutations of a list make no
difference to the result of combining its elements. When binary operators * and
@ are transpose to one another, the list-reducers bulk(*) and bulk(@) will each
be equal to the result of composing the other to the left of the natural
list-reversal mapping
which provides (for any given list) just one of the permutations
Abelian
would fail to notice. Note that I don't call this list-reverser
by the name reverse
- I use that name for the mapping for which
reverse(r) relates x to y iff r relates y to x.
When * has been obtained from star, rather than the other way round, we have reverse(star(b@a)) = reverse(star(a*b)) = reverse(star(a)&on;star(b)) = reverse(star(b))&on;reverse(star(a)) whence rats = reverse&on;star gives us rats(b)&on;rats(a) = rats(b@a); so composing reverse on the left of a relation transposes the binary operator it generates.
In particular: when star is the archetypical (: (: a*b ←b :) ←a :), its transpose, (: (: a*b ←a :) ←b :), generates the same binary operator @ as reverse&on;star = (: (: b ← a*b :) ←a :). Conversely, the binary operator induced from arts = (: (: a ← a*b :) ←b :) is *, as may be seen from arts(x)&on;arts(y) = (: a← a*x*y :) = arts(x*y).
I've claimed, above, that completeness and cancellation make a group (when non-empty): I should pause to justify the claim.
Suppose we are given a non-empty, right-complete, fully cancellable ({relations}: star :). (I only need half of completeness; the other half will follow; and it doesn't matter whether I take left or right.)
Let A be star's left-equivalence and, for brevity, read equality among star's left values modulo A. Right completeness says that, for any a, b in A, there's an x in A for which a&on;x is b. Since A is non-empty, there is some a in A; for which (as both a and b) we can ask (as x) for an i in A giving a&on;i = a; right-complete guarantees the existence of such an i, left cancellation implies it is unique (for given a).
For any b in A, we now have a&on;i&on;b = a&on;b so left cancellation says that i&on;b = b. This was true for arbitrary b in A, so i is a left identity for A under composition; and right cancellation says it is unique in this rôle. Running round the loop again, we now know i&on;a = a so, for arbitrary b in A, b&on;i&on;a = b&on;a and right cancellation gives us b&on;i = b so i is a right identity as well.
Existence of right inverses now follows trivially from right completeness; for any b in A, there's some p in A with b&on;p = i. We can then compose p&on;b&on;p = p&on;i = p = i&on;p and right cancel to obtain p&on;b = i, so our right inverses are left inverses. QED.
Furthermore, any associative binary operator with unique identity and inverses is complete and cancellable (so where I specified right-complete, left-complete would have done just as well). Proof:
Given a*b = a*d, obtain a's inverse, c: then b = c*a*b = c*a*d = d; likewise but with b*a = d*a given, b = b*a*c = d*a*c = d.
Given v, w, obtain v's inverse n and observe that u=n*w will solve v*u=w while u=w*n will solve u*v=w.
Note that, while identity and inverses work well together, identity
alone is of little use and inverses aren't defined without identity: while
cancellability and completeness each provide useful properties which work
independently. In short, I view them as a more orthogonal
decomposition
of the properties of groups: others' tastes may differ.