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.
For a somewhat accessible sketch of the subject, see a
casual quickie YouTube video
(his words) by Oliver
Lugg, A Sensible
Introduction to Category Theory.
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 combiner; that is, a closed associative binary operator (combiner) 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 combiners 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.
I characterise a category by the combiner that
encodes its composition; indeed, my category theory
is really a theory of
such categoric combiners, with little actual discussion of categories other than
as formal labels for a structure characterised by its combiner.
… 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.
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.
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.
Written by Eddy.