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\colon T \rightarrow 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 $Clique(C)$ whose objects are cliques of $C$, and whose morphisms and compositions are given as follows: Given two such cliques $(T_0, A_0)$ and $(T_1, A_1)$ in $C$, say that a morphism between them is a natural transformation from $T_0 \times T_1 \stackrel{\pi}{\to} T_0 \stackrel{A_0}{\to} C$ to $T_0 \times T_1 \stackrel{\pi}{\to} T_1 \stackrel{A_1}{\to} C$, where the $\pi$ are the appropriate projections. Given such morphisms $m : (T_0, A_0) \rightarrow (T_1, A_1)$ and $n : (T_1, A_1) \rightarrow (T_2, A_2)$, and $(t_0, t_2) \in Ob(T_0 \times T_2)$, note that the composite $n_{(t_1, t_2)} m_{(t_0, t_1)}$ of corresponding components has the same value no matter what the choice of $t_1 \in Ob(T_1)$, and there is at least one such choice. Accordingly, we can take this to give a well-defined component $(n m)_{(t_0, t_2)}$, thus defining binary composition of morphisms of cliques. Similarly, we can take the identity on a clique $(T, A)$ to be the natural transformation whose component on $(t, t') \in Ob(T \times T)$ is the value of $A$ on the unique morphism from $t$ to $t'$ 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 \overset{\leftarrow}{p} c \overset{\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 $Clique(C)$ into $C$, through which every other anafunctor into $C$ factors in an essentially unique way into a genuine functor. This induces for $Clique(-)$ the structure of a (2-)monad on $Str Cat$ (the (2-)category of “genuine” functors between categories), such that the Kleisli category for this monad will be $Cat_{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 Clique(C)$ takes each object $c\in C$ to the corresponding clique $c\colon 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 $Clique(D)$. (With composition of these defined in a straightforward way, and natural transformations between these being simply natural transformations of the corresponding genuine functors into $Clique(D)$). Accordingly, $Clique(-)$ is itself the same as $Cat_{ana}(1, -)$, 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[1]$, is monoidally equivalent to the discrete monoidal category $(\mathbb{N}, +, 0)$. Thus each connected component $C_n$ of $F[1]$ 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 $Oper(M)$ whose objects are functors

$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 $Oper(M)$ is the composite

$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 $Oper(M)$ is inherited from the monoidal structure on $M$.

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

$\kappa: F[1] \to Oper(M)$

uniquely determined as the one which sends the generator $1$ of $F[1]$ to $Id_M$. On each connected component $C_n$ of $F[1]$, this restricts to a functor

$C_n \stackrel{\kappa|}{\to} Cat(M^n, M)$
3. Then, for each $n$-tuple of objects $(x_1, \ldots, x_n)$ of objects of $M$, there is an associated clique $\kappa_{x_1, \ldots, x_n}$ in $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^{st}$ are $n$-tuples $(x_1, \ldots, x_n)$ of objects of $M$. A morphism

$(x_1, \ldots, x_m) \to (y_1, \ldots, y_n)$

is by definition a clique morphism $\kappa_{x_1, \ldots, x_m} \to \kappa_{y_1, \ldots, y_n}$. There is an evident strict monoidal category structure on $M^{st}$ which at the object level is just concatenation of tuples.

It is straightforward to check that the natural inclusion

$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

$(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)