Groupoid

In mathematics, especially in category theory and homotopy theory, a groupoid (less often Brandt groupoid or virtual group) generalises the notion of group in several equivalent ways. A groupoid can be seen as a:
Group with a partial function replacing the binary operation;
Category in which every morphism is invertible. A category of this sort can be viewed as augmented with a unary operation, called inverse by analogy with group theory. A groupoid where there is only one object is a usual group.  

In the presence of dependent typing, a category in general can be viewed as a typed monoid, and similarly, a groupoid can be viewed as simply a typed group.  The morphisms take one from one object to another, and form a dependent family of types, thus morphisms might be typed ,  , say. Composition is then a total function: , so that . 

Special cases include:
Setoids: sets that come with an equivalence relation,
G-sets: sets equipped with an action of a group .

Groupoids are often used to reason about geometrical objects such as manifolds.  introduced groupoids implicitly via Brandt semigroups.

Definitions 

A groupoid is an algebraic structure  consisting of a non-empty set  and a binary partial function  ''  defined on .

Algebraic 

A groupoid is a set  with a unary operation  and a partial function  .  Here * is not a binary operation because it is not necessarily defined for all pairs of elements of .  The precise conditions under which  is defined are not articulated here and vary by situation.

 and −1 have the following axiomatic properties:  For all , , and  in ,
 Associativity: If  and  are defined, then  and  are defined and are equal.  Conversely, if one of  and  is defined, then so are both  and  as well as  = .
 Inverse:  and  are always defined.
 Identity: If  is defined, then , and .  (The previous two axioms already show that these expressions are defined and unambiguous.)

Two easy and convenient properties follow from these axioms:
 ,
 If  is defined, then .

Category theoretic
A groupoid is a small category in which every morphism is an isomorphism, i.e. invertible. More precisely, a groupoid G is:
 A set G0 of objects;
 For each pair of objects x and y in G0, there exists a (possibly empty) set G(x,y) of morphisms (or arrows) from x to y. We write f : x → y to indicate that f is an element of G(x,y).
 For every object x, a designated element  of G(x,x);
 For each triple of objects x, y, and z, a function ;
 For each pair of objects x, y a function ;

satisfying, for any f : x → y, g : y → z, and h : z → w:
  and ;
 ;
  and .

If f is an element of G(x,y) then x is called the source of f, written s(f), and y is called the target of f, written t(f).

More generally, one can consider a groupoid object in an arbitrary category admitting finite fiber products.

Comparing the definitions
The algebraic and category-theoretic definitions are equivalent, as we now show. Given a groupoid in the category-theoretic sense, let G be the disjoint union of all of the sets G(x,y) (i.e. the sets of morphisms from x to y). Then  and  become partial operations on G, and  will in fact be defined everywhere. We define ∗ to be  and −1 to be , which gives a groupoid in the algebraic sense. Explicit reference to G0 (and hence to ) can be dropped.

Conversely, given a groupoid G in the algebraic sense, define an equivalence relation  on its elements by
 iff a ∗ a−1 = b ∗ b−1. Let G0 be the set of equivalence classes of , i.e. . Denote  a ∗ a−1 by  if  with .

Now define  as the set of all elements f such that  exists. Given  and  their composite is defined as . To see that this is well defined, observe that since  and  exist, so does . The identity morphism on x is then , and the category-theoretic inverse of f is f−1.

Sets in the definitions above may be replaced with classes, as is generally the case in category theory.

Vertex groups
Given a groupoid G, the vertex groups or isotropy groups or object groups in G are the subsets of the form G(x,x), where x is any object of G.  It follows easily from the axioms above that these are indeed groups, as every pair of elements is composable and inverses are in the same vertex group.

Category of groupoids
A subgroupoid is a subcategory that is itself a groupoid. A groupoid morphism is simply a functor between two (category-theoretic) groupoids. The category whose objects are groupoids and whose morphisms are groupoid morphisms is called the groupoid category, or the category of groupoids, denoted Grpd.

It is useful that this category is, like the category of small categories,  Cartesian closed. That is, we can construct  for any groupoids  a groupoid   whose objects are the morphisms  and whose arrows are the natural equivalences  of morphisms. Thus if  are just groups, then such arrows are the conjugacies of morphisms. The main result is that for any groupoids  there is a natural bijection

This result is of interest even if all the groupoids  are just groups.

Fibrations and coverings
Particular kinds of morphisms of groupoids are of interest. A morphism  of groupoids is called a fibration if for each object  of  and each morphism  of  starting at  there is a morphism  of  starting at   such that . A fibration is called a covering morphism or covering of groupoids if further such an  is unique. The covering morphisms of groupoids are especially useful because they can be used to model covering maps of spaces.

It is also true that the category of covering morphisms of a given groupoid  is equivalent to the category of actions of the groupoid  on sets.

Examples

Topology

Given a topological space , let  be the set . The morphisms from the point  to the point  are equivalence classes of continuous paths from  to , with two paths being 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 , denoted  (or sometimes, ).  The usual fundamental group  is then the vertex group for the point .

An important extension of this idea is to consider the fundamental groupoid  where  is a chosen set of "base points". Here, one considers only paths whose endpoints belong to .  is a sub-groupoid of . The set  may be chosen according to the geometry of the situation at hand.

Equivalence relation
If  is a set with an equivalence relation denoted by infix , then a groupoid "representing" this equivalence relation can be formed as follows:
 The objects of the groupoid are the elements of ;
For any two elements  and  in , there is a single morphism from  to  if and only if .

Group action
If the group  acts on the set , then we can form the action groupoid (or transformation groupoid) representing this group action as follows:
The objects are the elements of ;
For any two elements  and  in , the morphisms from  to  correspond to the elements  of  such that ;
Composition of morphisms interprets the binary operation of .

More explicitly, the action groupoid is a small category with   and  with source and target maps  and .  It is often denoted  (or ). Multiplication (or composition) in the groupoid is then  which is defined provided .

For  in , the vertex group consists of those  with , which is just the isotropy subgroup at  for the given action (which is why vertex groups are also called isotropy groups).

Another way to describe -sets is the functor category , where  is the groupoid (category) with one element and isomorphic to the group . Indeed, every functor  of this category defines a set  and for every  in  (i.e. for every morphism in ) induces a bijection  : . The categorical structure of the functor  assures us that  defines a -action on the set . The (unique) representable functor  : → is the Cayley representation of . In fact, this functor is isomorphic to  and so sends  to the set  which is by definition the "set"  and the morphism  of  (i.e. the element  of ) to the permutation  of the set . We deduce from the Yoneda embedding that the group  is isomorphic to the group , a subgroup of the group of permutations of .

Finite set
Consider the finite set , we can form the group action  acting on  by taking each number to its negative, so  and . The quotient groupoid  is the set of equivalence classes from this group action , and  has a group action of  on it.

Quotient variety 
On , any finite group  which maps to  give a group action on  (since this is the group of automorphisms). Then, a quotient groupoid can be forms , which has one point with stabilizer  at the origin.

Fiber product of groupoids
Given a diagram of groupoids with groupoid morphisms

where  and , we can form the groupoid  whose objects are triples , where , , and  in . Morphisms can be defined as a pair of morphisms  where  and  such that for triples  , there is a commutative diagram in  of ,  and the .

Homological algebra
A two term complex

of objects in a concrete Abelian category can be used to form a groupoid. It has as objects the set  and arrows  where the source morphism is just the projection onto  while the target morphism is the addition of projection onto  composed with  and projection onto . That is, given  we have

Of course, if the abelian category is the category of coherent sheaves on a scheme, then this construction can be used to form a presheaf of groupoids.

Puzzles 

While puzzles such as the Rubik's Cube can be modeled using group theory (see Rubik's Cube group), certain puzzles are better modeled as groupoids.

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

Mathieu groupoid

The Mathieu groupoid is a groupoid introduced by John Horton Conway acting on 13 points such that the elements fixing a point form a copy of the Mathieu group M12.

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 generalize to groupoids, with the notion of functor replacing that of group homomorphism.

If  is an object of the groupoid , then the set of all morphisms from  to  forms a group  (called the vertex group, defined above). If there is a morphism  from  to , then the groups  and  are isomorphic, with an isomorphism given by the mapping .

Every connected groupoid - that is, one in which any two objects are connected by at least one morphism - is isomorphic to an action groupoid (as defined above) . By connectedness, there will only be one orbit under the action. If the groupoid is not connected, then it is isomorphic to a disjoint union of groupoids of the above type (possibly with different groups  and sets  for each connected component).

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 , a group isomorphism  from  to , and for each  other than , a morphism in  from  to .

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, one need not specify the sets , only the groups  For example,

The fundamental groupoid of  is equivalent to the collection of the fundamental groups of each path-connected component of , but an isomorphism requires specifying the set of points in each component;
The set  with the equivalence relation  is equivalent (as a groupoid) to one copy of the trivial group for each equivalence class, but an isomorphism requires specifying what each equivalence class is:
The set  equipped with an action of the group  is equivalent (as a groupoid) to one copy of  for each orbit of the action, but an isomorphism requires specifying 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 is 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. Otherwise, one must choose a way to view each  in terms of a single group, and this choice can be arbitrary. In our example from topology, you would have to make a coherent choice of paths (or equivalence classes of paths) from each point  to each point  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 nontrivial.

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

Properties of the category Grpd 

 Grpd is both complete and cocomplete
 Grpd is a cartesian closed category

Relation to Cat 

The inclusion  has both a left and a right adjoint:

Here,  denotes the localization of a category that inverts every morphism, and  denotes the subcategory of all isomorphisms.

Relation to sSet 

The nerve functor  embeds Grpd as a full subcategory of the category of simplicial sets. The nerve of a groupoid is always Kan complex.

The nerve has a left adjoint

Here,  denotes the fundamental groupoid of the simplicial set X.

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.

See also 
∞-groupoid
Homotopy type theory
Inverse category
groupoid algebra (not to be confused with algebraic groupoid)
R-algebroid

Notes

References

Brown, Ronald, 1987, "From groups to groupoids: a brief survey," Bull. London Math. Soc. 19: 113-34. Reviews the history of groupoids up to 1987, starting with the work of Brandt on quadratic forms. The downloadable version updates the many references.
 —, 2006. Topology and groupoids. Booksurge. Revised and extended edition of a book previously published in 1968 and 1988. Groupoids are introduced in the context of their topological application.
 —, Higher dimensional group theory  Explains how the groupoid concept has led to higher-dimensional homotopy groupoids, having applications in homotopy theory and in group cohomology. Many references.
 
 
F. Borceux, G. Janelidze, 2001, Galois theories. Cambridge Univ. Press. Shows how generalisations of Galois theory lead to Galois groupoids.
 Cannas da Silva, A., and A. Weinstein, Geometric Models for Noncommutative Algebras. Especially Part VI.
Golubitsky, M., Ian Stewart, 2006, "Nonlinear dynamics of networks: the groupoid formalism", Bull. Amer. Math. Soc. 43: 305-64
 
 Higgins, P. J., "The fundamental groupoid of a graph of groups", J. London Math. Soc. (2) 13 (1976) 145—149.
 Higgins, P. J. and Taylor, J., "The fundamental groupoid and the homotopy crossed complex of   an orbit space",  in Category theory (Gummersbach, 1981), Lecture Notes   in Math., Volume 962. Springer, Berlin (1982), 115—122.
Higgins, P. J., 1971.  Categories and groupoids. Van Nostrand Notes in Mathematics. Republished in Reprints in Theory and Applications of Categories, No. 7 (2005) pp. 1–195; freely downloadable. Substantial introduction to category theory with special emphasis on groupoids. Presents applications of groupoids in group theory, for example to a generalisation of Grushko's theorem, and in topology, e.g. fundamental groupoid.
Mackenzie, K. C. H., 2005. General theory of Lie groupoids and Lie algebroids. Cambridge Univ. Press.
Weinstein, Alan, "Groupoids: unifying internal and external symmetry — A tour through some examples." Also available in Postscript., Notices of the AMS, July 1996, pp. 744–752.
 Weinstein, Alan, "The Geometry of Momentum" (2002)
 R.T. Zivaljevic. "Groupoids in combinatorics—applications of a theory of local symmetries". In Algebraic and geometric combinatorics, volume 423 of  Contemp. Math., 305–324.  Amer. Math. Soc., Providence, RI (2006)
 
 

Category:Algebraic structures
Category:Category theory
Category:Homotopy theory