category theory

# Contents

## Definition

A clique of a category $C$ is a functor $T\to C$ from a (-2)-groupoid $T$, or equivalently an anafunctor to $C$ from the trivial category.

So this is a pair of a category $T$ which is weakly equivalent to $1$ (i.e., $T$ is the indiscrete category on an inhabited collection of objects) and a functor $A:T\to C$.

A clique is also sometimes called an anaobject, since an object of $C$ is a functor (not anafunctor) to $C$ from the trivial category.

We can form a category $\mathrm{Clique}\left(C\right)$ whose objects are cliques of $C$, and whose morphisms and compositions are given as follows: Given two such cliques $\left({T}_{0},{A}_{0}\right)$ and $\left({T}_{1},{A}_{1}\right)$ in $C$, say that a morphism between them is a natural transformation from ${T}_{0}×{T}_{1}\stackrel{\pi }{\to }{T}_{0}\stackrel{{A}_{0}}{\to }C$ to ${T}_{0}×{T}_{1}\stackrel{\pi }{\to }{T}_{1}\stackrel{{A}_{1}}{\to }C$, where the $\pi$ are the appropriate projections. Given such morphisms $m:\left({T}_{0},{A}_{0}\right)\to \left({T}_{1},{A}_{1}\right)$ and $n:\left({T}_{1},{A}_{1}\right)\to \left({T}_{2},{A}_{2}\right)$, and $\left({t}_{0},{t}_{2}\right)\in \mathrm{Ob}\left({T}_{0}×{T}_{2}\right)$, note that the composite ${n}_{\left({t}_{1},{t}_{2}\right)}{m}_{\left({t}_{0},{t}_{1}\right)}$ of corresponding components has the same value no matter what the choice of ${t}_{1}\in \mathrm{Ob}\left({T}_{1}\right)$, and there is at least one such choice. Accordingly, we can take this to give a well-defined component $\left(nm{\right)}_{\left({t}_{0},{t}_{2}\right)}$, thus defining binary composition of morphisms of cliques. Similarly, we can take the identity on a clique $\left(T,A\right)$ to be the natural transformation whose component on $\left(t,t\prime \right)\in \mathrm{Ob}\left(T×T\right)$ is the value of $A$ on the unique morphism from $t$ to $t\prime$ in $T$.

## Applications

### Objects with universal properties

Many universal properties that are commonly considered as defining “an object” actually define a clique. For example, given two objects $a$ and $b$ of a category $C$, their cartesian product can be considered as the clique $T\to C$, where $T$ is the indiscrete category whose objects are product diagrams $a\stackrel{←}{p}c\stackrel{\to }{q}b$, and where the functor $T\to C$ sends each such diagram to the object $c$ and each morphism to the unique comparison isomorphism between two cartesian products. Note that unlike “the product” of $a$ and $b$ considered as a single object, this clique is defined without making any arbitrary choices. This of course is the same philosophy which leads to anafunctors, and so cliques are closely related to anafunctors.

### Cliques and anafunctors

There is an obvious anafunctor from $\mathrm{Clique}\left(C\right)$ into $C$, through which every other anafunctor into $C$ factors in an essentially unique way into a genuine functor. This induces for $\mathrm{Clique}\left(-\right)$ the structure of a (2-)monad on $\mathrm{Str}\mathrm{Cat}$ (the (2-)category of “genuine” functors between categories), such that the Kleisli category for this monad will be ${\mathrm{Cat}}_{\mathrm{ana}}$ (the (2-)category of anafunctors between categories). This monad can also be described more explicitly; in particular the unit (a “genuine” functor) $C\to \mathrm{Clique}\left(C\right)$ takes each object $c\in C$ to the corresponding clique $c:1\to C$ defined on the domain $1$. Note that this functor is a weak equivalence, i.e. fully faithful and essentially surjective on objects, but not a strong equivalence unless one assumes the axiom of choice.

In particular, we can use cliques to define anafunctors, taking an anafunctor from $C$ into $D$ to simply be a genuine functor from $C$ into $\mathrm{Clique}\left(D\right)$. (With composition of these defined in a straightforward way, and natural transformations between these being simply natural transformations of the corresponding genuine functors into $\mathrm{Clique}\left(D\right)$). Accordingly, $\mathrm{Clique}\left(-\right)$ is itself the same as ${\mathrm{Cat}}_{\mathrm{ana}}\left(1,-\right)$, and this can also be taken as a definition of a clique (hence the alternate name anaobject).

### Monoidal strictifications

Unsurprisingly, cliques provide a useful technical device for describing strictifications of monoidal categories.

It is relevant first to recall the original form of Mac Lane’s coherence theorem: the free monoidal category on one generator, $F\left[1\right]$, is monoidally equivalent to the discrete monoidal category $\left(ℕ,+,0\right)$. Thus each connected component ${C}_{n}$ of $F\left[1\right]$ is an indiscrete category whose objects are the possible $n$-fold tensor products of the generator, possibly with instances of the unit object folded in; the indiscreteness says that “all diagrams built from associativity and unit constraints commute”.

One canonical way to strictify a monoidal category $M$ is by considering cliques in $M$ where the domains are the ${C}_{n}$ and the functors model associativity and unit constraints, in the following precise sense:

1. We may form a monoidal category $\mathrm{Oper}\left(M\right)$ whose objects are functors

$F:{M}^{j}\to M$F: M^j \to M

and whose morphisms are natural transformations between such functors. The tensor product of $F:{M}^{j}\to M$ and $G:{M}^{k}\to M$ in $\mathrm{Oper}\left(M\right)$ is the composite

${M}^{j+k}\cong {M}^{j}×{M}^{k}\stackrel{F×G}{\to }M×M\stackrel{\otimes }{\to }M$M^{j+k} \cong M^j \times M^k \stackrel{F \times G}{\to} M \times M \stackrel{\otimes}{\to} M

and the rest of the monoidal structure on $\mathrm{Oper}\left(M\right)$ is inherited from the monoidal structure on $M$.

2. By freeness of $F\left[1\right]$, we have a (strict) monoidal functor

$\kappa :F\left[1\right]\to \mathrm{Oper}\left(M\right)$\kappa: F[1] \to Oper(M)

uniquely determined as the one which sends the generator $1$ of $F\left[1\right]$ to ${\mathrm{Id}}_{M}$. On each connected component ${C}_{n}$ of $F\left[1\right]$, this restricts to a functor

${C}_{n}\stackrel{\kappa \mid }{\to }\mathrm{Cat}\left({M}^{n},M\right)$C_n \stackrel{\kappa|}{\to} Cat(M^n, M)
3. Then, for each $n$-tuple of objects $\left({x}_{1},\dots ,{x}_{n}\right)$ of objects of $M$, there is an associated clique ${\kappa }_{{x}_{1},\dots ,{x}_{n}}$ in $M$:

${C}_{n}\stackrel{\kappa \mid }{\to }\mathrm{Cat}\left({M}^{n},M\right)\stackrel{{\mathrm{eval}}_{\left({x}_{1},\dots ,{x}_{n}\right)}}{\to }M$C_n \stackrel{\kappa|}{\to} Cat(M^n, M) \stackrel{eval_{(x_1, \ldots, x_n)}}{\to} M
4. Finally, the objects of the strictification ${M}^{\mathrm{st}}$ are $n$-tuples $\left({x}_{1},\dots ,{x}_{n}\right)$ of objects of $M$. A morphism

$\left({x}_{1},\dots ,{x}_{m}\right)\to \left({y}_{1},\dots ,{y}_{n}\right)$(x_1, \ldots, x_m) \to (y_1, \ldots, y_n)

is by definition a clique morphism ${\kappa }_{{x}_{1},\dots ,{x}_{m}}\to {\kappa }_{{y}_{1},\dots ,{y}_{n}}$. There is an evident strict monoidal category structure on ${M}^{\mathrm{st}}$ which at the object level is just concatenation of tuples.

It is straightforward to check that the natural inclusion

$i:M\to {M}^{\mathrm{st}},$i: M \to M^{st},

which interprets each object as a 1-tuple and each morphism as an evident clique morphism, is a monoidal equivalence. The essential idea is that there is a canonical clique isomorphism

$\left({x}_{1},{x}_{2},\dots ,{x}_{n}\right)\to i\left(\mathrm{Bracketing}\left({x}_{1}\otimes \dots \otimes {x}_{n}\right)\right)$(x_1, x_2, \ldots, x_n) \to i(Bracketing(x_1 \otimes \ldots \otimes x_n))

for every choice of bracketing the tensor product on the right in $M$ (possibly with units thrown in).

## Etymology and relation to graph theory

There is a notion of clique in an undirected (simple) graph familiar to graph-theorists: a clique $C$ in a graph $G$ is a subgraph which is complete? as a graph, i.e., one for which any two distinct vertices are connected by an edge. Thus, a clique having $n$ vertices is isomorphic to an inclusion of a ${K}_{n}$.

A reasonable analogue for quivers (the category theorists' directed graphs) might be a subgraph $C$ which is indiscrete: there is exactly one edge in $C$ from $x$ to $y$ for any vertices $x$, $y$ of $C$.

The categorical notion of clique is one step removed from that: a clique in a category $C$ is a functor $i:K\to C$ where the underlying graph of $K$ is indiscrete. The generic “picture” of a clique in a category is reminiscent of (and no doubt the etymology derives from) the graph-theoretic notion, even if the notions are technically distinct.

Revised on August 30, 2011 19:05:47 by Stephan (188.62.32.126)