Anticategories theory

Let me to share to you a toy construction, that kept me entertained recently. Without a better idea, I dubbed it "theory of anticategories".

I constructed it definition-first, starting from abstract definitions and ending with discovering examples of such objects and their relation with groupoids. I enjoyed the process of writing it, and hope someone could enjoy reading it (or glossing it over). Indeed, I understand that it is not something deep, the whole construction was done as entertainment after reading an introduction into category theory.

People on Reddit suggested that this construction resembles spans. Indeed, the resemblance is striking! However, I feel that spans theory is much deeper. Seems that I described some special kind of spans.

I wrote the original document and drew diagrams using Mathcha editor, but then semi-manually converted it to HTML with Mathjax to post it here.

Definition

Let's define an anticategory is a collection of

Objects
Arrows, each arrow having a source and a target object (domain and codomain)

Arrows are subject to the ternary composition, defined when 3 arrows match head-to-head and tail-to-tail (opposite to composition of arrows in categories, thus "anti" in the name):

In this document, ternary composition of 3 arrows is written as $f.g.h$. What properties the composition must have to be well-behaved?

Axiom 1: ternary associativity

Motivation: be able to talk about commuting diagrams in the anticategory. The most important property is associativity, which takes the following form:

$$ ( a.b.c) .d.e\ =\ a.( d.c.b) .e\ =\ a.b.( c.d.e) =\\ =a.b.c.d.e $$

In other words, in the following diagram the result of composition of five arrows on the upper path does not depend on composition order.

Associativity means that composition of any chain of odd number of arrows is well defined.

Axiom 2: rolling equalities

Motivation: to be able to say that diagram commutes without defining specific paths in it. Assume that $a.b.c\ =\ d$. It corresponds to the following diagram:

There are, however, several ways to read this diagram, one for each arrow:

$$ d.c.b\ =\ a\\ c.d.a\ =\ b\\ b.a.d\ =\ c\\ a.b.c=\ d $$

It is natural to require that all these equalities always hold simultaneously. Motivation for the name: these equalities can be obtained by "rolling" the string "abcd"

Observation: equalities are commuting loops

Every composition equality in anticategory have form

$$ f_{1} .f_{2} .f_{3} ....f_{n} =f_{n+1} .f_{n+2} ....f_{m} $$

where left and right side are compositions of an odd number of arrows (thus, n must be odd and m - even). The corresponding diagram is:

Again, unlike similar categorical diagram, it has no dedicated start and end vertices. Rolling equalities together with associativity mean that any partition of this loop in two chains of odd length gives raise to a valid equality. This idea can be further expanded, by redefining evaluation via operations on commuting loops. If two loops have a common edge of odd length, then they can be joined together, with the common edge removed.

Composition of two commuting loops, (ab) and (bc) gives new commuing loop (ac)

To prove this, cut the common edge from both loops. For the left loop, by rolling equality: $a=b$. For the right loop, $b=c$. Therefore $a=c$, and thus $ac$ is a commuting loop.

Corollary: function $x\mapsto b.b.x$ does not depend on $b$ and is an involution.

Or, restating it: let $a$ is an arrow. Then for any arrow $b$ having the same codomain,

$$ a.a.a\ =b.b.a $$

Proof

Let $a.a.b\ =\ c$. Then, by rolling equality (reading along the dashed arrow):

$$ a.a.c\ =\ b $$

Substituting the original equality into it gives:

$$ a.a.a.a.b=b $$

Writing the left part as $( a.a.a) .a.b$ and applying rolling equality again, finally obtain:

$$ a.a.a=b.b.a $$

This can be obtained easier via commuting loop operations by gluing together two copies of the (aabc) loop along the c edge, then cutting the resulting loop in 2 parts (red and black)

Derivation via commuting loop composition

Cutting the right loop in a different way gives

$$ a.a.a.a.b=b $$

for any $a,b$, which proves the involution property.

Axiom 3: identity

It is tempting to strengthen the above corollary, stating that:

$$ a.a.b=b $$

This feels natural and gives a nice analog for the categorical identity arrow, which anticategories do not have.

Bipartite anticategories

Let's call an anticategory bipartite, if any object in it is either arrow producer (domain objects), or arrow consumer (codomain objects), but never both. Here is an example: A,D are domain objects and B,C are codomain objects.

Observation: any category can be made bipartite. In anticategory, arrows of different direction sharing a common object do not interact. Precisely, they neither can be composed nor they can be compared for equality. Therefore, any object that serves as both domain and codomain, can be separated into a pair of objects: domain and codomain, and such separation does not affect arrow composition and equality:

Making anticategory bipartite by splitting objects

It seems that bipartite categories are more "natural" for definitions.

Functors

Functors between anticategories can be defined analogously to categories: a mapping of objects and arrows, preserving composition. They can be co- and contravaraint. Functors are composable in the obvious way, thus small anticategories form a category Acat (ACAT), analogously to Cat and CAT.

Examples of anticategories

Trivial examples

2-object anticategory $x\rightarrow y$ with 2 objects and a single arrow $a$ between them. The only identity is $a.a.a=a$ This anticategory is the terminal object of Acat.

Groupoids are anticategories!

Any groupoid is an anticategory, with ternary composition defined as:

$$ f.g.h=fg^{-1} h $$

Proving that this operation complies to ternary associativity, rolling equalities and identity laws is trivial. I was happy to notice this fact, because it gives the first "natural" example of a anticategory.

Hom-mapping (and anticategorical Hom-functor!)

This is an attempt to construct an analog of the hom-functor from category theory. Attempt to naively transfer the construction from category to anticategory does not give well-defined mapping of arows to functions, because product of two arrows is not defined, and thus I see no way to define mapping of arrows to functions. However, with a small modification the construction does actually work!

Let $C$ be an anticategory. Fix an arrow in it, $f:A\rightarrow B$. Then for any other arrow $x:X\rightarrow Y$, there is a function:

$$ x_{f} =a\mapsto x.a.f\\ x_{f} :C( A,Y)\rightarrow C( X,B) $$

This defines a mapping of C-arrows to functions. Resulting function $x_{f}$ is a bijectiion, its inverse is $f_{x} =a\mapsto f.a.x$. Proof is by the identity axiom. Therefore, $x_{f}$ belongs to the core of the $Set$ category, $core( Set)$ - a large groupoid where objects are sets and arrows are bijections.

What about objects?
Mapping of objects is one to two for general anticategories, and one to one for bipartite: object $X$ is mapped to the set $C( A,X)$ when it is a codomain, and when it is a domain then it is mapped to $C( X,B)$. It is easy to check that composition of 3 arrows $x.y.z$ is mapped to the function:

$$ ( x.y.z)_{f} =x_{f} \circ y^{-1}_{f} \circ z_{f} $$

which coincides with the definition of composition in groupoid-as-anticategory! Therefore, hom mapping is a functor from $C$ to the anticategory $core( Set)$. Which is a satisfying fact.

Natural transformations

I see no natural way to define an analog of natural transformation between a pair of covariant functors: $F,G:C\rightrightarrows D$ .

However, it is possible to define a natural transformation between co- and contravariant functors from C to D! The definition is essentially the same as with categories, except that arrows go in both directions. It becomes cleaner, when assuming that underlying anticategories are bipartite.

Definition
Let $F:C\rightarrow D$ is a covariant functor between two (bipartite) anticategories, and $G:C^{OP}\rightarrow D$ is a contravariant functor between them. Then a natural transformation $\alpha :F\Rightarrow G$ is a family of $C$-indexed arrows in $D$, such that $\alpha _{A} :FA\rightarrow GA$ for each domain object $A$, and $\alpha _{B} :GB\rightarrow FA$ for each codomain object $B$, and for each arrow f in $C$, the diagram on the right commutes:

Commuting square of natural transformation

By definition, natural transformation always goes from covariant to contravariant functor. Anti-categorical natural transformations are akin to natural isomorphisms in categories. By rolling equalities,

$$ \alpha _{B} =Ff.\alpha _{A} .Gf $$

therefore if source anticategory C is single-connected, then the whole natural transformation is uniquely determined by a single arrow.

Anticategory of functors

Can natural transformations be composed? Yes, and one must have 3 transformations to compose: $F\overset{\alpha }{\Rightarrow } G\overset{\beta }{\Leftarrow } H\overset{\gamma }{\Rightarrow } K$ composes to $\gamma .\beta .\alpha :F\Rightarrow I$. Composition can be defined arrow-wise, and it is easy to check that resulting family of arrows is indeed a natural transformation.

Composition of natural transformations follows the same pattern as for arrows

Therefore, a collection of co- and contravariant functors between anticategories is itself an anticategory, where objects are functors, and arrows are natural transformations! In the hindsight, this is not a big deal, since the whole natural transformation is defined by a single arrow for each connected component.

Categorical model of an anticategory

The (somewhat boring) construction below is an attempt to make a category which would encode all relations in the anticategory without introducing new ones. The idea is to "curry" ternary composition to a binary operation.

Let A be a bipartite anticategory. Then construct category $C=cat( A)$ in the following way:

Objects of C are objects of A.
For each object $X\in A$, an identity arrow $1_{X}$ is created in C.
For each arrow $f:X\rightarrow Y$ in A, two arrows are created: $f:X\rightarrow Y$ and $f^{-1} :Y\rightarrow X$, call them single arrows. Call $f$ a dom-cod arrow, and $f^{-1}$ a cod-dom arrow. (Note that -1 superscript is just a formal marker, not some kind of inversion)
For each pair of arrows in A sharing a common codomain: $X\overset{f}{\rightarrow } *\overset{g}{\leftarrow } Y$, a dom-dom arrow is created in C: $\left[ g^{-1} ,f\right] :X\rightarrow Y$
For each pair of arrows in A sharing a common domain: $X\overset{f}{\leftarrow } *\overset{g}{\rightarrow } Y$, a cod-cod arrow is created in C: $\left[ g,f^{-1}\right] :X\rightarrow Y$.These are double arrows.
No more arrows are created.

Arrow composition is defined by:

Composition with identity: $1f=f1=f$
Compositions of single arrows (only defined for a dom-cod and cod-dom pair) give double arrow:
1. $ff^{-1} =f^{-1} f=1$
2. $fg^{-1} =\left[ f,g^{-1}\right]$, a dom-dom arrow
3. $f^{-1} g=\left[ f^{-1} ,g\right]$, a cod-cod arrow
Composition of single and double arrows give single arrow:
1. $f\left[ g^{-1} ,h\right] =f.g.h$
2. $\left[ f,g^{-1}\right] h=f.g.h$
3. $f^{-1}\left[ g,h^{-1}\right] =( h.g.f)^{-1}$
4. $\left[ f^{-1} ,g\right] h^{-1} =( h.g.f)^{-1}$
Product of two double arrows of dom-dom or cod-cod type produce double arrow of the same type defined via product of two single arrows:
1. $\left[ f^{-1} ,g\right]\left[ h^{-1} ,k\right] =f^{-1}( g.h.k)$
2. $\left[ f,g^{-1}\right]\left[ h,k^{-1}\right] =( f.g.h) k^{-1}$

In short, these rules are nothing else than currying of a ternary composition. It seems that it is easy (though boring) to ensure that resulting construction is indeed a category. This category is equivalent to the original anticategory A in the following sense:

Arrows in A correspond one to one with dom-cod arrows in C.
Ternary composition in A maps to arrow composition in C. If $a.b.c=d$ in A, then $ab^{-1} c=d$ in C.
C does not contain any additional relations between dom-cod arrows (In fact, I think that it is an example of universal property: C must be initial in the appropriate category of models... But something is fishy with double arrows)

Category C is a groupoid, because every arrow it it has an inverse:

$$ ( f)^{-1} =f^{-1} ,\left( f^{-1}\right)^{-1} =f,\left[ f,g^{-1}\right]^{-1} =\left[ g,f^{-1}\right] ,\left[ f^{-1} ,g\right]^{-1} =\left[ g^{-1} ,f\right] . $$

Concluding, any anticategory appears to be equivalent to a groupoid with bipartite structure: objects are divided in two subclasses, and any arrow within class is a composition of two arrows between classes. But in a connected groupoid such decomposition is always possible regardless of the division scheme (if there are at least one object in each of the subclasses). Thus, anticategory can be thought as a groupoid, whose objects are "painted" with one of two colors (say, black and white), such that any connected component has at least one object of each color.

What's next?

By the way, my original idea was ton consider 3-ended "arrows" whose ends have 3 different colors and composition requires colors matching. However, I initially found such construction hard to make sense of and decided to consider 2-ended arrows first.

Поиск по этому блогу

Random thoughts and fancy math