]> Flat Binary Operators

Flat Binary Operators

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.

Group Properties

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.

Equivalence of the definitions of Group

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.

Interactions with homomorphism

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.

Kernel and Image

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:

Ker(f) = {v in V: f(v) is an identity for @ in U}

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.

Image(f) = {f(v): v in V}

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.

Inducing completeness

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.

Impact of heterodoxy

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.

Valid CSSValid XHTML 1.1 Written by Eddy.