I describe a binary operator
as flat
if it isn't fussy
about which operands it combines in which order; the composite value that
results may (and usually does) depend on these things, but if it is * and a, b
are operands of * then * does know how to combine them as a*b, which thus thus
does denote some value (or possibly values).
If a flat binary operator is closed and its collection of operands is V, then its bulk action is (V: |{non-empty lists (V: :)}), i.e. it accepts any non-empty list of operands; and its representation as a mapping is star = (: (V: a*b ←b |V) ←a |V), which represents each operand as a relation (V: |V), among which we can use clean composition. If it is also associative (hence a combiner) then this bulk action introduces no ambiguity not already present in * itself and the clean composition of relations serves as a model of it among its associated mapping's representations of its operands, star(a)&on;star(b) = star(a*b).
For the most part we shall indeed be interested in flat combiners. None the less, some of the definitions below are meaningful without associativity or closure (some even have generalisations to non-flat cases), so I presume no more than flatness as their context. Other properties applicable to binary operators in general are, naturally, also applicable to flat ones.
I'll describe a flat binary operator *
as left-cancellable
precisely if, for all operands a, b, c, a*b = a*c
implies b = c
; as right-cancellable
precisely if, for all a, b,
c, b*a = c*a implies b = c
and as
simply cancellable
precisely if it is both
left-cancellable and right-cancellable. (In each case, when the binary
operator, or either operand, is ambiguous, the equality checks need to be read
in an in so far as
manner: for example, for left cancellation, in so far
as x*a may take some value that x*b takes, a takes some value that b takes; and,
if x*a agrees with x*b then a agrees with b.) Note that I here
treat cancelling as a primitive action in its own
right, as distinct from combining with an inverse (see below) to achieve the
same effect.
Given a flat binary operator * and a pair b←a of its
operands, I'll describe an operand x: as a right-completion
of b←a
precisely if b = a*x; and as a left-completion
of b←a precisely if b
= x*a. In each case I'll say the given x left- or right- completes b from
a
; and describe any left- or right- completion as, simply,
a completion
when either side will do. I'll describe *
as right-complete
precisely if it has a right-completion for every pair
of its operands; as left-complete
precisely if it has a left-completion
for every pair of its operands; and as simply complete
precisely if it is both left-complete and right-complete.
I'll describe one collection, U, of operands of a flat binary
operator * as closed under completions within
another, V, precisely if U
is closed under * and, whenever a pair in U has a left- or right- completion in
V, this completion is itself in U. When *'s restriction to V is complete and V
subsumes U, this just obliges its restriction to U to also be complete;
otherwise, it demands as much completion, in U, as its context, V, permits. One
collection may likewise be closed under left- or right- completions within
another when the condition is met for the specified flavour of completions. If
the collection within which the completions are to be found is
omitted, closed under completions within
tacitly refers to the collection
of operands.
In the context of a flat binary operator *, I'll describe an
operand e: as a left identity
precisely if, for every operand a, e*a = a;
as a right identity
precisely if, for every operand a, a*e = a; and
simply as an identity
precisely if it is both a left
identity and a right identity.
Note that the raw composition on relations is a flat binary
operator and, although I describe the (: x ←x :) mapping on each collection
(with which the collection is indeed synonymous) as the identity
on that
collection, which does indeed compose before each relation from the collection
and after each relation to the collection to give the relation in question,
these are not identities for composition in the sense just given – with
the exception of the universal identity that relates every value to every value
– because their composition with other relations does make a
difference. The sense in which these are identities is that appropriate
to category theory, arising from restricting the
composition in various ways so that it is no longer flat. Inverses are,
naturally, also affected by this distinction between flat and categoric binary
operators.
In the context of a flat binary operator *, given an operand b,
I'll describe an operand c: as a left inverse
for b precisely if c*b is a
left identity; as a right inverse
for b precisely if b*c is a right
identity; and simply as an inverse
for b precisely if it
is both a left inverse for b and a right inverse for b. Each kind of
inverse for b
may equally be described as the relevant kind of
inverse of b
.
I shall describe a flat combiner as
a group
precisely if it is
cancellable and complete. Orthodoxy describes a set of values closed under an
associative flat binary operator as a group precisely if it has an identity and,
for each operand, an inverse. These two specifications agree in their
consequences, aside from: the minor wrinkle of mine allowing an empty group, as
we'll see below; and the fact that I describe the binary operator as a
group while orthodoxy describes its set of operands as a group (under
the given binary operator).
In this section, I shall take * to be a flat combiner and study how, in that context, the properties above interact with each other, starting out with combinations insufficient to make a group.
Any intersection U, of collections closed under
completions within a given W, is necessarily itself closed under completions
within W, since any pair u←v with u and v in U has u and v in each of the
collections intersected, each of which is closed under completions within W;
thus, if W contains a completion for u←v, each of the collections
intersected contains this completion, hence so does the intersection U; and the
intersection is also closed under the binary operator in the usual way, as each
of the collections intersected is. As for closure under the binary operator, we
can thus form a closure under completions within
W for any collection S
of operands by intersecting all the U that subsume S and are closed under
completions within W.
If * has two right-completions x, y for some pair b←a of its operands, then a*x = b = a*y: if * is left-cancellable, we can then infer x = y from a*x = a*y. Thus left-cancellation makes right-completions unique; likewise, right-cancellation makes left-completions unique. The specifications of identities and inveres make left identities and left inverses left-completions, hence right-cancellation makes them unique, while right identities and right inverses are right-completions, so left-cancellation makes them unique.
Every left or right identity e has e*e = e, hence is both a left- and a right-completion for e←e. For the same reason, every left identity is its own left inverse and every right identity is its own right inverse. (Note, however, that a right identity doesn't necessarily have a left inverse – because its existence doesn't suffice to ensure that there is a right identity – and likewise with left and right swapped.)
If * has a right identity e and a left identity i, then i = i*e because e is a right identity; and i*e = e because i is a left identity; hence i = e is an identity. If an operand v has a right inverse w and a left inverse u then: u*v*w = u because v*w is a right identity; and u*v*w = w because u*v is a left identity (hence incidentally equal to v*w); so, when an operand has a left inverse and a right inverse, they are equal and hence its inverse.
If an operand v has a left inverse u and, in its turn, u has a left inverse w then v = w*u*v = w*e with e a left identity; thus v*u = w*e*u = w*u = e and v is a left inverse for u. Thus if v has a left inverse that has any left inverses, v is one of them. Likewise, if v has a right inverse that has any right inverses, v is one of them.
If every operand has a right inverse, we can trivially implement right-cancellation by combining a*x = b*x with a right inverse for x on the right, so that it collapses down to a = b. Likewise, left inverses deliver left cancellation.
If v has a left inverse u then, for any operand w, any right-completion x for w←v must satisfy w = v*x and joining with u on the left implies that u*w = x, so u*w is the only possible candidate for a right-completion of w←v; however, we are not assured that w = v*u*w unless v is also a left inverse for u. Fortunately, as proved above, if u has a left inverse, then v is indeed a left inverse of u and this works. So a binary operator for which all operands have left inverses is necessarily right-complete. Likewise, right inverses give us left-completeness.
If * is left-cancellable and has a (necessarily unique) right-completion e for some x←x then, for any operand y, we get x*e*y = x*y; cancelling the x, we are left with e*y = y; thus e is a left identity. Likewise, right-cancellation turns a left-completion of any x←x into a right identity. Since every left or right identity e is both a left- and a right-completion for e←e, right-cancellation makes any left identity an identity and left-cancellation makes any right identity an identity. When cancellable, * thus makes an identity out of a left- or right-completion of any x←x, including any left or right identity.
For a flat combiner *, I'll now show that my definition of group and the orthodox definition agree, aside from the two details mentioned above: I allow an empty group and label the binary operator as the group, where orthodoxy labels its set of values (or the combination of binary operator and set) as a group and its definition precludes an empty group.
First, suppose * is non-empty, cancellable and complete. As it is non-empty, it has some member x; as it is complete, it has left- and right-completions for x←x;, which cancellation turns into a unique identity, e. For each operand v, the left- and right-completions for e←v are left and right inverses, hence necessarily coincide and are an inverse for v. Thus being cancellable and complete suffices to ensure *, if non-empty, has an identity and, for each operand, an inverse.
Conversely, suppose we have an identity and inverses. We saw above that (a left identity and) left inverses deliver right-completeness and left-cancellation; likewise (a right identity and) right inverses deliver left-completeness and right-cancellation. Thus an identity and inverses suffice to make a binary operator cancellable and complete.
Given two binary operators * on V and @ on U, a mapping (U: f |V) is a homomorphism (of binary operators) precisely if, whenever x*y is valid, so is f(x)@f(y), with f(x*y) = f(x)@f(y).
For a composite (: f |V)&on;(V: g :) of homomorphisms of flat binary
operators to be proper, the flat binary
operator on V that f morphs from must be the one g morphs to. When we have the
same composite of relations, with g morphing to a flat binary operator subsumed
(in the sense appropriate to binary operators)
by the one f morphs from, we can interpose an inclusion embedding, whose
relation is an identity, (: V :g), used to morph between the two operators; when
this is needed, it should be made explicit. Note that, while as a
relation it is an identity, this inclusion morphism
is
between different binary operators, so is not an identity morphism. In
this case, as both operators are flat, each combines any of its values with any
of its values, so the possible differences are that g's might only act on some
of V while f's might have more ambiguity than g's. When f's is unambiguous,
this constrains g's to be unambiguous too, and flat on the values g produces, so
it is at worst a restriction of f's binary
operator.
If V has a left or right identity, e, then f(e) = f(e*e) = f(e)@f(e) is a left- and right-completion for an x←x in U; thus, if @ is cancellable (even if * is not), f(e) is an identity for @ in U. If u, v in V have u*v = e, in such a case, then f(u)@f(v) = f(e) so, if @ is cancellable, f(u) and f(v) are inverse to one another. So a homomorphism into a cancellable binary operator maps left or right identities to (full) identities and left or right inverses to (full) inverses.
When we have a right-completion x for some w←v in V, a homomorphic mapping f turns w = v*x into f(w) = f(v)@f(x), supplying us with a right-completion for f(w)←f(v) in U; so homomorphic mappings map right-comletions to right-completions and, by similar reasoning, left-completions to left-completions. Thus homomorphic mappings map completions to completions.
Suppose we have a homomorphic mapping (U: f |V) from one binary operator, * on V, to another, @ on U. If V subsumes some W closed under *, (U: f |W) is likewise a homomorphism from *'s W-restriction to @; every v, w in W have v*w in W, as it's closed under *, with v, w and v*w thus in V (as it subsumes W), hence f(v*w) = f(v)@f(w) as (U: f |V) satisfies this. Conversely, if U subsumes T closed under @, (T: f :) = (T: f |W) for some W = (T&on;f: w←w :V) subsumed by V (by specification); for any v, w in W, we have v*w in V, hence f(v*w) = f(v)@f(w) with both f(v) and f(w) in T, which is closed under @ so f(v)@f(w) is also in T and f(v*w) is in T; thus, by specification of W, v*w is also n W. Further, if U subsumes T closed under completions within U, we can construct W and show it closed as before; then, for any w, v in W, if there is a completion x of w←v in V, then w = v*x or x*v gives us f(w) = f(x)@f(v) or f(v)@f(x), with f(w) and f(v) in T by specification, making f(x) a completion of f(w)←f(v) in U, hence f(x) is in fact in T, so x is in W and W is duly closed under completions in U. Thus the homomorphic image of a closed collection is closed; and the pre-image (T: f |) of a collection T is closed or closed under completions precisely if T is; homomorphisms push closure forward and pull back both closure and closure under completions.
When f is monic, if @ has a left identity in (|f:) then this is f(e) for some e in V and, for any v in V, we have f(v) = f(e)@f(v) = f(e*v) and, as f is monic, f(v) = f(e*v) implies v = e*v, so e is a right identity for *; likewise, with f monic, if f(e) is a right identity then e is a left identity; and only an identity can be mapped to an identity. With f monic, if f(u)@f(v) is a left or right identity then so is f(u*v), so u*v is a right or left identity (respectively), making v a right inverse for u or u a left inverse for v. Thus, with a monic homomorphism, only a left inverse for v can be mapped to a left inverse of f(v) and only a right inverse of u can be mapped to a right inverse of f(u).
When we come to look at group homomorphisms, we'll be able to say a great deal more about them. The foregoing, at least, ensure that they map identities to identities and inverses to inverses. The need for cancelability to ensure identities map to identities shall make it necessary, when defining homomorphisms of structures involving a binary operator with an identity but not necessarily cancellable, to explicitly require homomorphisms to map such identities to identities.
When we have a homomorphism (U: f |V) from one binary operator, * on V, to another, @ on U, the values it produces and those it maps to identities are of particular importance, so define:
called
the kernel
of f; this is necessarily empty if U has no
identity; in this case, if @ is cancellable in U, V can have no identity. When
f is monic, every member of Ker(f) is an identity in V; if * is cancellable,
there can be at most one of these.
called
the image
of V under f or, when either V or f is implicit,
simply of
the other.
As f is a homomorphism, Ker(f) is closed within V under * and Image(f) is closed under @, at least when V is closed under *. The latter follows from Image(f) being the image of a collection closed under *; the former from Ker(f) being pulled back from {identities for @ in U}, which is necessarily closed under completions within U under @.
We can induce natural scalings both in U and
in V. Conflating each natural scaling for * in V with the matching scaling for
@ in U, each natural scaling commutes
with f in the sense: f(scale(*, n,
v)) = scale(@, n, f(v)) for every v in V and positive natural n. Consequently,
Image(f) is closed under scalings of @, i.e. every u in Image(f) has scale(@, n,
u) in Image(f) for every positive natural n. Identities are fixed points of
scalings; this being true in U, we can infer that Ker(f) is closed under
scalings in V, i.e. every v in Ker(f) has scale(*, n, v) in Ker(f) for every
positive natural n. When * has an identity, for use as scale(*, 0, v) for each
v in V, the various things said here for positive natural n do also apply for n
= 0 (albeit, when U has no identity (and @ isn't cancellable to turn f(e) into
one), making scale(@, 0) undefined, the claim that Ker(f) is closed under it
survives only because Ker(f) has no members, so we don't need scale(@, 0) to be
defined in order to apply it to them; empty is conveniently closed under
any transformation of its members, no matter how ill-defined, whimsical,
nonsensical or outright mythical it might be).
Even in so far as natural sub-division (i.e. the reverses of some scaling)
is meaningful, there is no guarantee that (binary operator) homomorphisms
respect it (in the commuting
sense just used). When we come to combine a
binary operator construed as addition with some form of scaling construed as
multiplication by scalars
(beyond naturals), we'll need to refine our
notion of homomorphism to include respect for such scaling as a constraint on
what counts as preserving the structure.
We can think of the specification of right- and left-completions as defining
right- and left- variants of a relation: x completes b←a precisely if it is
a right- or left- (as appropriate) completion of b←a; call this relation C
(whether it's right-completes or left-completes) for now; the two variants are,
of course, equal when * is abelian. The right values of C are pairs of operands
for which there is a (relevant) completion, which is the left value. When * is
appropriately cancellable (left-cancellable if C is right-completes
,
right-cancellable for left-completes
), relevant completions are unique so
C is a mapping, which makes (:C|) an equivalence. It relates b←d to
p←q precisely if (taking the right-completion case, for example) there is
some x for which b = d*x and p = q*x; whence b*q*x = p*d*x. When * is
cancellable, this implies b*q = p*d; in any case, when C is a mapping, (:C|) is
subsumed by the relation (b←d)~(p←q) ⇔ b*q = p*d
, for the
right-completion case, or (b←d)~(p←q) ⇔ q*b = d*p
for
left-completion. Once we understand C's right values modulo this equivalence, C
becomes an iso: and every operand of * does appear as a left value of C, since C
relates each x to (x*x)←x. We can now read reverse(C) as an embedding of
*'s operands in its pairs of operands, understood modulo the given
equivalence. (This is essentially the mechanism by which orthodoxy induces the
integers from the naturals; each n←m ends up being interpreted as
n−m, subject to the equivalence n−m = p−q precisely if n+q =
p+m.)
On pairs of operands, modulo the given equivalence that subsumes (:C|), define a binary operator @ by (p←q)@(b←d) = (p*b)←(q*d); when we embed two operands x, y and combine with @, we get (x*a*y*c)←a*c for some arbitrary operands a, c; if any operand commutes with y, we can use that as a and obtain (x*y*a*c)←a*c, which is (equivalent to) the image of x*y; so @ serves as a representation of * among pairs of *'s operands, at least when there is some value (e.g. an identity) with which each operand commutes. It is thus usual to use the same symbol, * in place of @, for this induced binary operator, treat each operand of * as synonymous with its image in (:C|) and interpret @'s action on the rest of the pairs of *'s operands as extending * to this larger collection of operands.
A typical pair of operands of @ is (p←q)←(b←d), for which a right-completion would be some x←y for which p←q ~ (b*x)←(d*y), i.e. p*d*y = b*x*q; when * is abelian, x = p*d and y = b*q naturally satisfy this, making x←y = (p*d)←(b*q) = (p←q)@(d←b); thus @'s right-completion for A←B is just A@reverse(B), for any pairs A, B of *'s operands. Since we needed * (hence @) to be abelian to do this, the same works for left-completions and @ is complete; at the same time, we've made the right- and left- variants of C coincide and made left- and right- cancellability (that we needed to make C a mapping, i.e. to make * unambiguous) equivalent.
So a cancellable commutative flat combiner * provides us with
a completes
relation C whose right-equivalence (:C|) can naturally be
extended to all pairs of *'s operands; the same relation's reverse can then
serve as an embedding of *'s operands in this equivalence (or, equivalently, in
its collection of equivalence classes), which naturally induces a binary
operator (on pairs) that's a homomorphic image of * under this embedding. This
induced binary operator is then complete and its restriction to C's right values
is an isomorphic representation of * acting on its operands, C's left values; it
thus inherits commutative and cancellable from *. So, any commutative
cancellable flat combiner can be embedded in another that's complete.
When I was first introduced to group theory, I was immediately struck by the lack of independence between the two axioms; having an identity buys you very little without inverses; and inverses can't even be specified without an identity. Indeed, since we can have left and right versions of each, we have to work out whether a left inverse for v left-completes a left identity (as specified above) or a right identity from v; and likewise with left and right swapped. As it happens (for an associative *), left-cancelling a factor of v from v*x = v*y requires a left inverse of v that makes a left identity (and likewise for x*v = y*v with right in place of left), so that's what I've specified above. This also (as shown above) ensures that right inverses, as long as they're not isolated, deliver left-completion and left inverses deliver right-completion.
So left identities and left inverses give us left-cancellation and right-completeness; left-cancellation makes right-completions unique and turns certain right-completions into left identities (and similar holds with left and right swapped throughout, of course). Meanwhile, left identities and left inverses are specified as left-completions, that'll be made unique by right-cancellation. So the left and right parts of the two systems interweave quite nicely. At the same time, their interplay illustrates that you need both identity and inverses to do anything, whereas completeness and cancellation do separate parts (existence and uniqueness) of each job.
Given that, in the commutative case, we can induce completeness out of cancellability, it thus seems entirely natural to study cancellation in its own right. Upon doing so, I found it to produce (with only minor tweaking) most of the benefits of ring theory's use of group structure for addition, while illuminating the incomplete multiplication of that theory far better than the simple lack of inverses could hope to. Even the treatment of such completions as are present proved illuminating, while doing so. Thus cancellation suffices to do large parts of the work, even in contexts where the other half (completeness) isn't available – as when we study the arithmetic on naturals, where we can cancel addition and (aside from factors of 0) multiplication but have no inverses.
I am thus able to express group theory in terms of a powerful basic property of a binary operator, cancellation, extended in a natural manner by a property, completeness, related to it by a natural duality (inducing uniquenesses). I find this separation vastly more satisfying than orthodoxy's.
Having an empty group should make very little difference, all of which can be dealt with by stipulating non-empty in relevant places, which shouldn't be needed all that often in any case. In the category of group-homomorphisms, the empty group shall be initial and the singleton group final; the latter is also initial for orthodoxy but won't be with my definition. The orthodox situation can, of course, be restored by restricting to the category of non-empty group homomorphisms.
While I formally specify that it's the binary operator (which knows what its
collection of operands is) that's a group, I shall none the less mirror
orthodoxy, when a specified binary operator is implcit from context, in speaking
of the collection as a group – especially of sub-collections as
sub-groups, where formally it's the restriction of the binary operator to the
sub-collection that is the sub-group – justified by taking the binary
operator's restriction to
as tacit in the mention of each collection as
such. I officially treat such usage as syntactic sugar
to make
discussions terse, with the binary operator still formally being what's
discussed, via the collection to which it's tacitly being restricted. This, in
fact, is just what orthodoxy is doing anyway, since it formally defines a group
to be a pair [*, V] of a binary operator and the set whose values it combines
(or the other way round, [V, *]); its usage of the set as the group is itself
just syntactic sugar taking the binary operator as implicit, in the same
way. So the real difference here is that I don't see the need for the formalism
to pair the binary operator with its set of operands, when the binary operator
knows its collection of operands anyway, and can be restricted to a
sub-collection as needed, so suffices on its own.
When it comes to describing, in the category Set of functions between sets under clean composition, what constitutes a group: the specification in terms of identity and inverses gets distinctly tricky (and connects poorly to that of associativity); whereas that in terms of cancellation and completeness merely requires saying that two associated mappings' outputs are monic (for cancellation) and epic (for completeness); and the mappings in question (mutually transpose to one another) arise naturally in the categoric treatment of a binary operator (their equality is what would make it commutative, for example) as they arise naturally in the expression of associativity and distributivity.
Written by Eddy.