Category theory, or its equivalent

There is a branch of modern mathematics known as Category Theory which may fairly be caricatured as the general theory of abstractions, or as the abstract theory of generalisations. I actually rather like it, but find that it isn't general or abstract enough; ironically, my remedy to this is to make it both more concrete and more specific – my general formalisation of mathematics in terms of relations (rather than sets and functions thereon) lets it be so and yet be more general and abstract.

Prelude

Category theory generally concerns itself with composing morhpisms between objects; at least some schools of fairly orthodox category theory allow that a so-called object can be identified with the identity morphism on it, a stance which I take to the extreme of not treating objects specially at all – hence, for example, not regarding a functor as anything more special than a transformation which can be combined with itself and, when it can be combined with a transformation, yields the transformation with which it was combined.

An orthodox category can be encoded as a categoric combinator; that is, a closed associative binary operator (combinator) that satisfies certain structural (categoric) properties that make it behave enough like the compositions on various kinds of homomorphism that we can prove some general and useful properties without having to delve into the particular details of how it manages to work that way. Various results that must otherwise be proved for each type of mathematical structure separately can thus be proved once in the abstract realm of categories and then applied, via their homomorphisms, to each kind of mathematical structure.

Unlike the raw composition I define on relations, which is flat, the homomorphisms of a given type of mathematical structure know which structure they morph from and which they morph to; their composition requires its right operand to morph to the same structure that their left operand morphs from. This restricts composition, so as to ensure that a composite is always a homomorphism of the relevant kind. Categoric combinators can likewise be fussy about which operands they are willing to compose: the question of composability is thus central to much of the discussion.

I wrote quite a bit of mess about arrow worlds in which I began exploring how to do category theory another way; it is now my intent to do a tidier (and more general) job of that. My previous analysis involved a convolution called arrow lands which can largely be converted to a discussion of directed graphs; this provided the framework within which to characterise a category's composition and specify such characteristics of transformations (and functors) as don't depend on composition itself. It is arguable that analysis should have applied to the hom-sets rather than to the morphisms themselves. The analysis then moved on to considering a category's composition as a constrained binary operator – it only combines things if they are suitably linked in the directed graphs; and the composite fits into the directed graph as a substitute for its components. Having now explored what the relevant digraph theory reduces to when expressed in terms of relations, I no longer consider it worth discussing separately from the composition.

Overview

I characterise a category by the combinator that encodes its composition; indeed, my category theory is really a theory of such categoric combinators, with little actual discussion of categories other than as formal labels for a structure characterised by its combinator.

… and I have scarecely scratched the surface of the topic, as I have higher priorities.


I re-wrote this in terms of categoric binary operators in 2015. Various pages from earlier fumblings on the subject died in the process. Some fragments related to that, refugees from separating it from the flat case, may be found below.

Refugees

For a given binary operator * and any operand v of it, an operand e is described as a left identity for v precisely if e*v = v; likewise as a right identity for v precisely if v*e = v. A left operand e which is a left identity for every v for which e*v is valid is simply known as a left identity, without qualifying which operands it is for; likewise, a right operand e that is a right identity for every v with v*e valid is an unqualified right identity. A value which is both a left identity and a right identity (unqualified) is known simply as an identity. In the case of a categoric binary operator, there may be many distinct identities; these serve as the end-points of the other operands (in the sense of the ski resort metaphor; in category theory these end-points are called objects, although one can restate category theory in a form that uses the identity on each object as a surrogate for the object, thereby eliminating the objects entirely).

For a left-cancellable binary operator, right identities for any given value are necessarily unique since, for any operand v with right identities e and i, we have v*e = v = v*i and can left-cancel the v from v*e = v*i to get e = i. Likewise, left identities for given values are unique for right-cancellable binary operators. For a flat associative left-cancellable binary operator *, a right identity e for some value v gives us v*e = v whence, for every operand u, v*e*u = v*u and left-cancelling v we get e*u = u for all u; hence, for a flat associative binary operator, left-cancellability turns a right identity for any value into a left identity (unqualified); in the same case, right-cancellability turns a left identity for any value into a right identity (unqualified); so cancellability turns a left or right identity for any value into an identity.

When we have a left identity e, it is a left operand so there is some v with e*v = v; substituting this into itself we get e*(e*v) = v from which, if the binary operator is associative, we infer that e*e is valid; as e is a left identity we then get e*e = e, which makes e a right identity for itself. Thus every (unqualified) left identity of an associative binary operator is a right identity for at least itself. Likewise, every (unqualified) right identity of an associative binary operator is a left identity for at least itself.

For a categoric binary operator *, if we have a left identity e and a right identity i (both unqualified) for which there are some operands f, g for which f*i, f*g and e*g are valid, then the common end-point constraint implies e*i is also valid; as e and i are left and right identities respectively, we thus have e = e*i = i is an identity.

When a binary operator * is flat on some collection V and has, in V, both a left-identity e and a right-identity i, we have e = e*i as i is a right-identity and e*i = i as e is a left-identity, whence e = i is an identity and necessarily unique – substituting any right identity for i, or left identity for e, would lead to the same conclusion. This matches the result above for a categoric binary operator. For a binary operator that's neither flat nor categoric, it can thus be important to be clear about which values a given left or right identity can be combined with; which is one more reason to not be interested in such binary operators.

Every non-empty group has an identity – Proof: let G be a non-empty group under *. As it is non-empty, it has some member, g. By left-completeness, there is some e in G for which e*g = g. For any h in G, h*e*g = h*g so, by right-cancellation, h*e = h and e is a right-identity; in particular, g*e = g. For any h in G, g*e*h = g*h so, by left-cancellation e*h = h and e is also a left-identity, hence an identity.

Note that collections, viewed as their own identity mappings, are not identities, in the above sense, for composition, &on; (which is flat and closed on relations), with the exception of the universal identity, which is. For example, empty is an identity but its composite with any other relation is empty, not the other relation. When a relation r = (W: r :A) for some collections W, A, however, we do indeed have W&on;r = r = r&on;A. With a little care and attention it is thus usually easy to avoid confusion between these two related but distinct identity notions. When, below, I represent a binary operator by a mapping, that mapping shall indeed map every left-identity e to the identity mapping on the collection {a: e*a is valid}.

Given a binary operator *, I'll describe one value a as a left-inverse (under *) for another, b, precisely if a*b is a left-identity. (Thus, when * is associative, if we have x = b*y, we can convert it to a*x = y.) Likewise, I'll describe a as a right-inverse of b under * precisely if b*a is a right-identity; and as an inverse of b precisely if a*b and b*a are identities. (Note that an inverse thus satisfies a stronger condition than just being both a right-inverse and a left-inverse; when a is both a left-inverse for b and a right-inverse for b, we can easily obtain a*b*a = a but, with e = a*b a left-identity and i = b*a a right-identity, i*b = b*a*b = b*e isn't guaranteed to be b, unless we have: cancellability to apply to x*b = x*i*b = x*b*a*b or b*x = b*e*x = b*a*b*x; or flatness to make e = e*i = i.) In a group, each member has a unique inverse – Proof: when the group is empty, we have nothing to prove (a statement about each member is fatuously true). Otherwise, we have a non-empty group G under * and, from the preceding, an identity e. For any g in G, completeness gives us left and right inverses as the f, h in G for which f*g = e = g*h (and e is a full identity, bypassing the problem I just mentioned with a left-inverse that's a right-inverse not necessarily being an inverse); and cancellability ensures f, h are unique. Then (exploiting associativity) f = f*e = f*g*h = e*h = h so the two are equal and we have our unique inverse for g.

Categoric completeness

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←u|) 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.


Valid CSSValid HTML 4.01 Written by Eddy.