Groupoid

dablink|This article is about groupoids in category theory. For the algebraic structure with a single binary operation see magma (algebra).

In mathematics, especially in category theory and homotopy theory, a groupoid is a simultaneous generalisation of a group, a setoid (a set equipped with an equivalence relation), and a $G$-set (a set equipped with an action of a group $G$).Groupoids are often used to capture information about geometrical objects such as manifolds.

Groupoids were first developed by Heinrich Brandt in 1926.

Definitions

Algebraic definition

A groupoid is a set $G$ with two operations: a partially defined binary operation $ast$ and a total (everywhere defined) function $^\{-1\}$, which satisfy the following three conditions on elements $f$ and $g$ of $G$:
* "Associativity": For all $a$, $b$ and $c$ in $G$, $(a\; ast\; b)\; ast\; c\; =\; a\; ast\; (b\; ast\; c)$, if either product is defined.
* "Identity": Where $fast\; g$ is defined $fast\; gast\; g^\{-1\}\; =\; f$ and $f^\{-1\}ast\; fast\; g\; =\; g$, uniquely.
* "Inverse": $f^\{-1\}ast\; f$ and $fast\; f^\{-1\}$ are always defined.

Category theory definition

From a more abstract point of view, a groupoid is simply a small category in which every morphism is an isomorphism (that is, invertible).To be explicit, a groupoid $G$ is:
* a set $G\_0$ of "objects";
* for each pair of objects $x$ and $y$ in $G\_0$, a set $G(x,y)$ of "morphisms" (or "arrows") from $x$ to $y$ — we write $f\; :\; x\; o\; y$ to indicate that $f$ is an element of $G(x,y)$;equipped with:
* an element $mathrm\{id\}\_x$ of $G(x,x)$;
* for each triple of objects $x$, $y$, and $z$, a binary function $mathrm\{comp\}\_\{x,y,z\}$ from $G(x,y)$$imes$$G(y,z)$ to $G(x,z)$ — we write $gf$ for $mathrm\{comp\}\_\{x,y,z\}(f,g)$, where $f$$in$$G(x,y)$, $g$$in$$G(y,z)$;
* a function $mathrm\{inv\}\_\{x,y\}$ from $G(x,y)$ to $G(y,x)$;such that:
* if $f\; :\; x\; o\; y$, then $f\; mathrm\{id\}\_x\; =\; f$ and $mathrm\{id\}\_y\; f\; =\; f$;
* if $f\; :\; x\; o\; y$, $g\; :\; y\; o\; z$, and $h\; :\; z\; o\; w$, then $(hg)f\; =\; h(gf)$;
* if $f\; :\; x\; o\; y$, then $f\; mathrm\{inv\}(f)\; =\; mathrm\{id\}\_y$ and $mathrm\{inv\}(f)f\; =\; mathrm\{id\}\_x$.

Comparison of the definitions

The relation between these definitions is as follows:Given a groupoid in the category-theoretic sense, let $G$ be the disjoint union of all of the sets $G(x,y)$, then $mathrm\{comp\}$ and $mathrm\{inv\}$ become partially defined operations on $G$, and $mathrm\{inv\}$ will in fact be defined everywhere; so we define $ast$ to be $mathrm\{comp\}$ and $^\{-1\}$ to be $mathrm\{inv\}$. This gives a groupoid in the algebraic definition. Explicit reference to $G\_0$ (and hence to $mathrm\{id\}$) can be dropped.

On the other hand, given a groupoid in the algebraic sense, let $G\_0$ be the set of all elements of the form $fast\; f^\{-1\}$ for elements $f$ of $G$.In other words, the objects are identified with the identity morphisms, and $mathrm\{id\}\_x$ is just $x$.Let $G(x,y)$ be the set of all elements $f$ such that $yfx$ is defined.Then $^\{-1\}$ and $ast$ break up into several functions on the various $G(x,y)$, which may be called $mathrm\{inv\}$ and $mathrm\{comp\}$, respectively.

While we have referred to "sets" in the definitions above, one may instead want to use classes, in the same way as for other categories.

Groupoid Category

The category whose objects are groupoids and whose morphisms are groupoidhomomorphisms is called the groupoid category, or the category of groupoids.

Examples

Linear algebra

Given a field $K$, the general linear groupoid $GL\_ast\; (K)$ consists of all invertible matrices with entries from $K$, with composition given by matrix multiplication.If $G\; =\; GL\_ast\; (K)$, then $G\_0$ contains a copy of the set of natural numbers, since there is one identity matrix of dimension $n$ for each natural number $n$, although $G\_0$ contains other matrices.$G(m,n)$ is empty unless $m\; =\; n$, in which case it is the set of $n$ by $n$ invertible matrices.

Topology

Start with a topological space $X$ and let $G\_0$ be the set $X$.The morphisms from the point $p$ to the point $q$ are equivalence classes of continuous paths from $p$ to $q$, with two paths being considered equivalent if they are homotopic.Two such morphisms are composed by first following the first path, then the second; the homotopy equivalence guarantees that this composition is associative.This groupoid is called the "fundamental groupoid" of $X$, denoted $pi\_1(X)$.

An important extension of this idea is to consider the fundamental groupoid $pi\_1(X,A)$ where $A$ is a subset of $X$. Here, one considers only paths whose endpoints belong to $A$. It is a sub-groupoid of $pi\_1(X)$. The set $A$ of base points may be chosen according to the geometry of the situation at hand.

Equivalence relation

If $X$ is a set and $sim$ is an equivalence relation on $X$, then we can form a groupoid representing this equivalence relation as follows:The objects are the elements of $X$, and for any two elements $x$ and $y$ in $X$, there is a single morphism from $x$ to $y$ if and only if $xsim\; y$.

Group action

If the group $G$ acts on the set $X$, then we can form a groupoid representing this group action as follows:The objects are the elements of $X$, and for any two elements $x$ and $y$ in $X$, there is a morphism from $x$ to $y$ for every element $g$ of $G$ such that $g.x\; =\; y$.Composition of morphisms is given by the group operation in $G$. Another way to describe $G$-sets is the functor category $[mathrm\{Gr\},mathrm\{Set\}]$, where $mathrm\{Gr\}$ is the groupoid (category) with one element and isomorphic to the group $G$. Indeed, every functor $F$ of this category defines a set $X=F(mathrm\{Gr\})$ and for every $g$ in $G$ (i.e. morphism in $mathrm\{Gr\}$) induces a bijection $F\_g:X\; o\; X$. The categorical structure of the functor $F$ assures us that $F$ defines a $G$-action on the set $X$. The (unique) representable functor $F:mathrm\{Gr\}\; o\; mathrm\{Set\}$ is the Cayley Representation of $G$. In fact, this functor is isomorphic to $mathrm\{Hom\}(mathrm\{Gr\},-)$ and so sends $mathrm\{ob\}(mathrm\{Gr\})$ to the set $mathrm\{Hom\}(mathrm\{Gr\},mathrm\{Gr\})$ which is by definition the "set" $G$ and the morphism $g$ of $mathrm\{Gr\}$ (i.e. the element $g$ of $G$) to the permutation $F\_g$ of the set $G$. We deduce from the Yoneda Embedding that the group $G$ is isomorphic to the group $\{F\_g\; mid\; g\; in\; G\}$ which is a subgroup of the group of permutations of $G$.

Fifteen puzzle

The symmetries of the Fifteen puzzle form a groupoid (not a group, as not all moves can be composed).This groupoid acts on configurations.

Relation to groups

If a groupoid has only one object, then the set of its morphisms forms a group.Using the algebraic definition, such a groupoid is literally just a group.Many concepts of group theory can be generalized to groupoids, with the notion of group homomorphism being replaced by that of functor.

If $x$ is an object of the groupoid $G$, then the set of all morphisms from $x$ to $x$ forms a group $G(x)$.If there is a morphism $f$ from $x$ to $y$, then the groups $G(x)$ and $G(y)$ are isomorphic, with an isomorphism given by mapping $g$ to $fgf^\{-1\}$.

Every connected groupoid (that is, one in which any two objects are connected by at least one morphism) is isomorphic to a groupoid of the following form:Pick a group $G$ and a set (or class) $X$.Let the objects of the groupoid be the elements of $X$.For elements $x$ and $y$ of $X$, let the set of morphisms from $x$ to $y$ be $G$.Composition of morphisms is the group operation of $G$.If the groupoid is not connected, then it is isomorphic to a disjoint union of groupoids of the above type (possibly with different groups $G$ per connected component).Thus, any groupoid may be given (up to isomorphism) by a set of ordered pairs $(X,G)$.

Note that the isomorphism described above is not unique, and there is no natural choice.Choosing such an isomorphism for a connected groupoid essentially amounts to picking one object $x\_0$, a group isomorphism $h$ from $G(x\_0)$ to $G$, and for each $x$ other than $x\_0$ a morphism in $G$ from $x\_0$ to $x$.

In category-theoretic terms, each connected component of a groupoid is equivalent (but not isomorphic) to a groupoid with a single object, that is, a single group.Thus any groupoid is equivalent to a multiset of unrelated groups.In other words, for equivalence instead of isomorphism, you don’t have to specify the sets $X$, only the groups $G$.

Consider the examples in the previous section.The general linear groupoid is both equivalent and isomorphic to the disjoint union of the various general linear groups $GL\_n(F)$.On the other hand, the fundamental groupoid of $X$ is equivalent to the collection of the fundamental groups of each path-connected component of $X$, but for an isomorphism you must also specify the set of points in each component.The set $X$ with the equivalence relation $sim$ is equivalent (as a groupoid) to one copy of the trivial group for each equivalence class, but for an isomorphism you must also specify what each equivalence class is.Finally, the set $X$ equipped with an action of the group $G$ is equivalent (as a groupoid) to one copy of $G$ for each orbit of the action, but for an isomorphism you must also specify what set each orbit is.

The collapse of a groupoid into a mere collection of groups loses some information, even from a category-theoretic point of view, because it’s not natural.Thus when groupoids arise in terms of other structures, as in the above examples, it can be helpful to maintain the full groupoid.If you don’t, then you must choose a way to view each $G(x)$ in terms of a single group, and this can be rather arbitrary.In our example from topology, you would have to make a coherent choice of paths (or equivalence classes of paths) from each point $p$ to each point $q$ in the same path-connected component.

As a more illuminating example, the classification of groupoids with one endomorphism does not reduce to purely group theoretic considerations. This is analogous to the fact that the classification of vector spaces with one endomorphism is non trivial.

Morphisms of groupoids come in more kinds than those of groups: we have, for example, fibrations, covering morphisms, universal morphisms, quotient morphisms. Thus a subgroup $H$ of a group $G$ yields an action of $G$ on the set of cosets of $H$ in $G$ and hence a covering morphism $p$ from say $K$ to $G$ where $K$ is a groupoid with vertex groups isomorphic to $H$. In this way, presentations of the group $G$ can be lifted to presentations of the groupoid $K$, and this is a useful way of obtaining information on presentations of the subgroup $H$. For further information, see the books by Higgins and by Brown listed below.

Another useful fact is that the category of groupoids, unlike that of groups, is cartesian closed.

Lie groupoids and Lie algebroids

When studying geometrical objects, the arising groupoids often carry some differentiable structure, turning them into Lie groupoids.These can be studied in terms of Lie algebroids, in analogy to the relation between Lie groups and Lie algebras.

References

*Ronald Brown, From groups to groupoids: a brief survey, Bull. LMS, 19 (1987) 113-134, gives some of the history of groupoids, namely the origins in work of Brandt on quadratic forms, and an indication of later work up to 1987, with 160 references. These have been updated slightly in the downloadable version, available as [http://www.bangor.ac.uk/r.brown/groupoidsurvey.pdf]

*Alan Weinstein, Groupoids: unifying internal and external symmetry, available as [http://math.berkeley.edu/~alanw/Groupoids.ps Groupoids.ps] or [http://www.ams.org/notices/199607/weinstein.pdf weinstein.pdf]
* Part VI of Geometric Models for Noncommutative Algebras, "by A. Cannas da Silva and A. Weinstein" [http://www.math.ist.utl.pt/~acannas/Books/models_final.pdf PDF file.]
* [http://www.bangor.ac.uk/r.brown/hdaweb2.htm Higher dimensional group theory ] is a web article with lots of references explaining how the groupoid concept has to led to notions of higher dimensional groupoids, not available in group theory, with applications in homotopy theory and in group cohomology.

* [http://www.shef.ac.uk/~pm1kchm/gt.html General theory of Lie groupoids and Lie algebroids, K.C.H. Mackenzie, CUP, 2005]

* [http://www.bangor.ac.uk/r.brown/topgpds.html Topology and groupoids, Ronald Brown, Booksurge 2006] revised and extended edition of a book previously published in 1968 and 1988. e-version available.

* [http://138.73.27.39/tac/reprints/articles/7/tr7abs.html Categories and groupoids, P.J. Higgins] , downloadable reprint of van Nostrand Notes in Mathematics, 1971, which deal with applications of groupoids in group theory and topology.

* [http://www.cup.cam.ac.uk/catalogue/catalogue.asp?isbn=9780521803090 Galois theories, F. Borceux, G. Janelidze, CUP, 2001 ] shows how generalisations of Galois theory lead to Galois groupoids.

*M. Golubitsky, I. Stewart, `Nonlinear dynamics of networks: the groupoid formalism', Bull. Amer. Math. Soc. 43 (2006), 305-364