§ 3. Groupoids

1. Categories

Let C be a quiver endowed with a law of composition $m$. Two arrows $f$ and $g$ such that $t(f) =o(g)$ are said to be composable; the arrow $m(f, g)$ is called their composite, or their product, and is often denoted by $f\cdot g$, or even by $f g$.

For every vertex $a$ of C, the set $C_{a,a}$ = Fl$_{a,a}(C)$, endowed with the mapping deduced from $m$ by passing to subsets, is a magma (A, I, p. 1, Def. 1).

One says that a family $(f_i)_{i\in I}$ of arrows of C, indexed by a finite nonempty totally ordered set I, is composable if, for every pair $(i, j)$ of consecutive elements of I, the arrows $f_i$ and $f_j$ are composable. The product $\prod_{i\in I}f_i$ of such a family is defined by induction on the cardinal of I in the following way (cf. A, I, p. 3):

(i) if I has a single element $\omega ,\prod_{i\in I}f_i=f_{\omega}$;

(ii) if I has at least two elements and if $\omega$ is the smallest element of I, one sets $\prod_{i\in I}f_i=f_{\omega}\cdot \prod_{i\in I-\{\omega\}}f_i$.

The law of composition $m$ is said to be associative if one has $f\cdot (g\cdot h) =$ $(f\cdot g)\cdot h$ for every composable triple $(f, g, h)$ of arrows of C. When the law $m$ is associative, the product of a sequence $(f_1, . . . , f_n)$ of $n$ composable arrows, where $n$ is an integer $\geqslant 1$, is denoted by $f_1f_2. . . f_n$.

Let $a$ be a vertex of C. One says that an arrow $e\in C_{a,a}$ is an identity element of $m$ at $a$ if one has $ef=f$ for every arrow $f$ with origin $a$ and $ge=g$ for every arrow $g$ with end $a$. There exists at most one identity element of $m$ at $a:$ if $e$ and $e'$ are two such elements, one has $e'=ee'=e$. When such an identity element exists, it is often denoted by $e_a$; it is then an identity element of the magma $C_{a,a}$ (A, I, p. 12).

2. Functors

Let C and $C'$ be categories and let $\varphi : C\rightarrow C'$ be a functor. Let $f$ be an arrow of C$,a$ its origin and $b$ its end; then, $\varphi (f)$ is an arrow of $C'$ with origin $\varphi (a)$ and end $\varphi (b)$.

Let C, $C',C''$ be categories and let $\varphi : C\rightarrow C'$ and $\varphi ': C'\rightarrow C''$ be functors. Then, $\varphi '\circ \varphi$ is a functor.

Let C be a category. Then the quiver morphism Id$_C$ is a functor.

Let $\varphi : C\rightarrow C'$ be a functor. In order that $\varphi$ be an isomorphism, it is necessary and sufficient that the mappings Som($\varphi$ ) and Fl($\varphi$ ) be bijective.

Thus, if one calls a category structure on sets S and F the data of a quiver structure on these sets and of an associative composition law for which there exists at each vertex an identity element, one can take the functors as morphisms of the category structure (E, IV, p. 11).

3. Groupoids

Let G be a groupoid and let $a$ be a vertex of G. The monoid $G_{a,a}$ is a group, denoted by $G_a$ and called the isotropy group of G at $a$.

Let $a,b$ be vertices of G and let $f\in G_{a,b}$ be an arrow joining $a$ to $b$. The mapping $g\mapsto f gf^{-1}$ is a group isomorphism of $G_b$ onto $G_a$, denoted by Int($f$). If $f$ and $f'$ are composable arrows of G, one has Int($f f'$) $=$ Int($f$)$\circ$ Int($f'$) ; the inverse of the isomorphism Int($f$) is the isomorphism Int($f^{-1}$).

A morphism of groupoids $\varphi : G\rightarrow G'$ is a morphism of categories. Moreover, $\varphi$ is an isomorphism of groupoids if and only if it is an isomorphism of categories.

Let $\varphi : G\rightarrow G'$ be a morphism of groupoids. For every vertex $a$ of G, the mapping $f\mapsto \varphi (f)$ of $G_a$ into $(G')_{\varphi(a)}$ is a group homomorphism denoted by $\varphi_a$. In particular, one has $\varphi (e_a) =e_{\varphi(a)}$.

For every arrow $f$ of G$,\varphi (f^{-1})$ is the inverse of $\varphi (f)$. If $f$ is an arrow of G joining a vertex $a$ to a vertex $b$, one thus has, for every element $g\in G_b$, the relation Int($\varphi (f)$)$(\varphi (g)) =\varphi$(Int($f$)$(g)$).

4. Orbits of a groupoid

Let G be a groupoid. The connected components of the underlying quiver of G are called the orbits of G. The set of the orbits of G is denoted by Orb(G); if $\varphi : G\rightarrow G'$ is a morphism of groupoids, the mapping $\pi_0(\varphi )$ deduced from $\varphi$ by passing to the connected components of the associated graphs is in general denoted by Orb($\varphi$ ) and called the mapping deduced from $\varphi$ by passing to the orbits.

A groupoid which has exactly one orbit is said to be transitive. If G is a transitive groupoid, the groups $G_a$, for $a\in$ Som(G), are isomorphic. One says that the groupoid G is simply transitive if it is transitive and if, moreover, the isotropy groups $G_a$ are all reduced to their identity element.

5. Examples of groupoids

1) Let G be a group. Let us denote by $\mathscr{G}$ the quiver whose set of vertices is reduced to one element and whose set of arrows is G. Endowed with the law of composition induced by that of G$,\mathscr{G}$ is a groupoid, called the groupoid associated with the group G.

2) Let X be a set. Let G be the quiver $(X,X\times X$, pr$_1$, pr$_2)$; define a law of composition in G by putting $(x, x')\cdot (x', x'') = (x, x'')$, if $x, x', x''$ are elements of X. This law is associative; for every $x\in X$, $(x, x)$ is the identity element at $x$; the inverse of the arrow $(x, x')$ is the arrow $(x', x)$. The groupoid thus defined is called the groupoid of pairs of the set X. If X is not empty, it is simply transitive.

3) Let X and S be sets and let $p: X\rightarrow S$ be a mapping. For $a\in S$, let $X_a=\overset{-1}{p}(a)$. For $a$ and $b$ in S, let $G_{a,b}$ be the set $\mathscr{B}(X_a; X_b)$ of bijections from $X_a$ onto $X_b$ and let G be the sum of the sets $G_{a,b}$. Let $o$ and $t$ be the mappings from G into S such that $o(f) =a$ and $t(f) =b$ for every element $f\in G_{a,b}$. The quadruple $(S,G, o, t)$ is a quiver. Endow it with the law of composition defined by $m(f, g) =g\circ f$ if $f\in \mathscr{B}(X_a; X_b)$ and $g\in \mathscr{B}(X_b; X_c)$, where $a, b, c$ are points of S. It is a groupoid; it is denoted by $\mathscr{B}(X, p)$ and called the groupoid of permutations of X relative to $p$.

4) Let $(G_i)_{i\in I}$ be a family of groupoids. Let us denote by G the product quiver of the family of underlying quivers; for each $i\in I$, let pr$_i: G\rightarrow G_i$ be the canonical quiver morphism. There exists a unique law of composition on G for which G is a groupoid and such that, for each $i\in I$, pr$_i$ is a groupoid morphism. Let $f= (f_i)_{i\in I}$ and $g= (g_i)_{i\in I}$ be arrows of G; they are composable if and only if the arrows $f_i$ and $g_i$ are composable, for $i\in I$. One then has $f g= (f_ig_i)_{i\in I}$.

The quiver G, endowed with this law of composition, is called the product groupoid of the family $(G_i)_{i\in I}$. It satisfies the following universal property: for every groupoid $G'$ and every family $(\varphi_i)_{i\in I}$, where $\varphi_i$ is a groupoid morphism of $G'$ into $G_i$, there exists a unique groupoid morphism $\varphi : G'\rightarrow G$ such that $\varphi_i=$ pr$_i\circ \varphi$ for each $i\in I$.

5) Let $((G_i)_{i\in I},(\varphi_{i,j})_{i\prec j})$ be an inductive system of groupoids, indexed by a right filtering preordered set $(I,\prec )$, the $\varphi_{i,j}$ being groupoid morphisms. Let G be the quiver whose set of vertices is lim$\longrightarrow_i$ Som(G$_i$), whose set of arrows is lim$\longrightarrow_i$ Fl(G$_i$), the source and target mappings being the mappings lim$\longrightarrow_io_{G_i}$ and lim$\longrightarrow_it_{G_i}$ respectively. The laws of composition of the $G_i$ induce a law of composition on G which makes it a groupoid (cf. A, I, p. 114). The canonical mappings Som(G$_i$)$\rightarrow$ Som(G) and Fl(G$_i$)$\rightarrow$ Fl(G) define a groupoid morphism $\varphi_i$ of $G_i$ into G. If $i,j$ are elements of I such that $i\prec j$, one has $\varphi_j\circ \varphi_{i,j}=\varphi_i$. The groupoid G is called the inductive limit of the family of groupoids $G_i$ and is denoted by lim$\longrightarrow_iG_i$. It satisfies the following universal property: for every groupoid H and every family $(\psi_i)_{i\in I}$, where, for $i\in I,\psi_i: G_i\rightarrow H$ is a groupoid morphism, such that $\psi_j\circ \varphi_{i,j}=\psi_i$ for every pair $(i, j)$ of elements of I such that $i\prec j$, there exists a unique groupoid morphism $\psi : G\rightarrow H$ such that $\psi_i=\psi \circ \varphi_i$.

For the existence of a groupoid satisfying this universal property when one does not suppose that the set I is right filtering, cf. II, p. 228, exerc. 3.

6. Subgroupoids

(i) For every vertex $a$ of D$,e_a$ is an arrow of D;

(ii) For every composable pair $(f, g)$ of arrows of C belonging to D, the product $f g$ is an arrow of D;

Let C be a category and let D be a subcategory of D; endowed with the law of composition deduced from that of C by passing to subsets, D is a category.

Every full subquiver of C is a subcategory of C. The intersection of a family of subcategories of C is a subcategory of C.

Let G be a groupoid. Every subgroupoid of G is a groupoid. Every full subquiver of G is a subgroupoid of G. The intersection of a family of subgroupoids of G is a subgroupoid of G.

Let H be a subquiver of G. The intersection of the subgroupoids of G of which H is a subquiver is called the subgroupoid of G generated by H. The set of its vertices is equal to that of H and its orbits are the connected components of H.

7. Operations of a groupoid

Let G be a groupoid; let S denote the set of its vertices. Let X be a set and let $p: X\rightarrow S$ be a mapping. A (right) operation $\varphi$ of the groupoid G on the set X, relative to $p$, is a morphism of groupoids $\varphi$ from G into the groupoid $\mathscr{B}(X, p)$ of permutations of the set X relative to $p($II, p. 163) which induces the identity on the set of vertices. In other words, $\varphi$ consists, for each pair $(a, b)$ of points of S and for each arrow $g\in G$ joining $a$ to $b$, of a mapping $\varphi (g): X_a\rightarrow X_b$, such that, for every pair $(f, g)$ of composable arrows of G,

and such that, for every $a\in S,\varphi (e_a)$ is the identity of $X_a$.

Let $\varphi$ and $\varphi '$ be operations of the groupoid G on a set X, relative to a mapping $p: X\rightarrow S$. In order that one have $\varphi =\varphi '$, it is enough that there exist a subquiver H of G, generating G, such that $\varphi (f) =\varphi '(f)$ for every $f\in$ Fl(H). In fact, the set of arrows $f$ of G such that $\varphi (f) =\varphi '(f)$ is the set of arrows of a subgroupoid of G, with set of vertices S.

Let G be a groupoid with set of vertices S, let X be a set, let $p: X\rightarrow S$ be a mapping, and let $\varphi$ be an operation of G on X relative to $p$. Let $G_{\varphi}$ be the subquiver of $p^*(G)$ whose set of vertices is X and whose set of arrows is the set of triples $(x, f, y)\in X\times$ Fl(G) $\times X$ such that $\varphi (f)(x) =y$. It is a subgroupoid of $p^*(G)$.

Conversely, let Γ be a subgroupoid of $p^*(G)$; suppose that the mapping $(x, f, y)\mapsto (x, f)$ of Fl(Γ) into $X\times$ Fl(G) is injective and that its image is the set of pairs $(x, f)$ such that $p(x) =o(f)$. Then there exists a unique operation $\varphi$ of the groupoid G on X such that $\Gamma = G_{\varphi}$.

The orbits of the groupoid $G_{\varphi}$ are called the orbits of the operation of G on X. By definition, they are the equivalence classes of the relation in X defined by $R\{x, y\}$ if and only if there exists $f\in$ Fl(G) such that $\varphi (f)(x) =y$.

8. Normal Subgroupoids; Quotient Groupoids

Let G be a groupoid and let H be a subgroupoid of G whose set of vertices is equal to Som(G). To verify that H is distinguished, it is enough to prove that $fH_bf^{-1}\subset H_a$ for every $a\in$ Som(G), every $b\in$ Som(G) and every $f\in G_{a,b}$. In fact, if this is so, one also has $f^{-1}H_af\subset H_b$ for every arrow $f\in G_{b,a}$, that is, $H_a\subset fH_bf^{-1}$, and consequently $fH_bf^{-1}= H_a$.

Let G be a groupoid and let H be a distinguished subgroupoid of G. For every vertex $a$ of G, the subgroup $H_a$ of $G_a$ is a distinguished subgroup of $G_a$.

Let $\varphi : G\rightarrow G'$ be a morphism of groupoids. The kernel of $\varphi ($II, p. 166, example 5) is a distinguished subgroupoid of G. In fact, let $f$ be an arrow in G joining $a$ to $b$ and let $g\in$ Ker($\varphi$ )$_b$; then one has $\varphi (f gf^{-1}) =\varphi (f)\varphi (g)\varphi (f^{-1}) =\varphi (f)e_{\varphi(b)}\varphi (f)^{-1}=e_{\varphi(a)}$, whence the inclusion $f$Ker($\varphi$ )$_bf^{-1}\subset$ Ker($\varphi$ )$_a$.

Let G be a groupoid. The groupoid G and the subgroupoid of G whose set of arrows is the set of identity elements of G are distinguished subgroupoids of G. The intersection of a family of distinguished subgroupoids of G is a distinguished subgroupoid of G. In particular, for every subset $F\subset$ Fl(G), there exists a smallest distinguished subgroupoid of G whose set of arrows contains F. It is called the distinguished subgroupoid generated by F.

Let H be a distinguished subgroupoid of G. Let $\mathscr{R}$ be the equivalence relation in Fl(G) defined by $\mathscr{R}\{f, g\}$ if and only if there exist arrows $x$ and $y$ in Fl(H) such that $f=xgy$. If $f$ and $g$ are arrows of G equivalent modulo $\mathscr{R}$, their origins (resp. their ends) belong to the same orbit of H. Put $F'=$ Fl(G)$/\mathscr{R}$ and denote by $o'$ and $t'$ the mappings of $F'$ into Orb(H) deduced from $o$ and $t$ by passing to the quotients. Denote by $G/H$ the quiver (Orb(H)$,F', o', t'$).

9. Groupoid of classes of paths of a graph

Let G be a graph. Let us denote by $\Omega_G$ the category of paths of the underlying quiver of G (II, p. 160, example 1). Consider the finest equivalence relation $\mathscr{R}$ in Ch(G) such that one has:

(i) For every pair $(a, b)$ of vertices of G and every arrow $f$ in G joining $a$ to $b$, the paths $(a, f, b,\overline{f}, a)$ and $e_a$ are equivalent modulo $\mathscr{R}$;

(ii) If $(c, d)$ and $(c', d')$ are pairs of juxtaposed paths in G such that $\mathscr{R}\{c, c'\}$ and $\mathscr{R}\{d, d'\}$, the paths $c*d$ and $c'*d'$ are equivalent modulo $\mathscr{R}$.

Two paths equivalent modulo $\mathscr{R}$ have the same origin and the same end. The mappings $o$ and $t$ from Ch(G) into Som(G) define, by passing to the quotient, mappings $o'$ and $t'$ from Ch(G)$/\mathscr{R}$ into Som(G). Let us denote by $\varpi_G$ the quiver (Som(G), Ch(G)$/\mathscr{R}, o', t'$). The pair $\varphi$ formed by the identity mapping of Som(G) and the canonical projection of Ch(G) onto Ch(G)$/\mathscr{R}$ is a morphism of quivers from $\Omega_G$ into $\varpi_G$. The juxtaposition of paths in Ch(G) defines, by passing to the quotients, a law of composition in $\varpi_G$.