Category where every morphism is invertible; generalization of a group
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 (less often Brandt groupoid or virtual group) generalises the notion of
group in several equivalent ways. A groupoid can be seen as a:
Category in which every
morphism is invertible. A category of this sort can be viewed as augmented with a
unary operation on the morphisms, called inverse by analogy with
group theory.[1] 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 .
A groupoid can be viewed as an algebraic structure consisting of a set with a binary
partial function.
Precisely, it is a non-empty 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.
The operations 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 or is defined, then they are both defined (and they are equal to each other), and and are also defined.
A groupoid is a
small category in which every
morphism is an
isomorphism, i.e., invertible.[1] More explicitly, a groupoid G is a set G0 of objects with
for each pair of objects x and y 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).
A groupoid G is sometimes denoted as , where is the set of all morphisms, and the two arrows represent the source and the target.
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 and orbits
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.
The orbit of a groupoid G at a point is given by the set containing every point that can be joined to x by a morphism in G. If two points and are in the same orbits, their vertex groups and are
isomorphic: if is any morphism from to , then the isomorphism is given by the mapping .
Orbits form a partition of the set X, and a groupoid is called transitive if it has only one orbit (equivalently, if it is
connected as a category). In that case, all the vertex groups are isomorphic (on the other hand, this is not a sufficient condition for transitivity; see the section
below for counterexamples).
Subgroupoids and morphisms
A subgroupoid of is a
subcategory that is itself a groupoid. It is called wide or full if it is
wide or
full as a subcategory, i.e., respectively, if or for every .
A groupoid morphism is simply a functor between two (category-theoretic) groupoids.
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.[4]
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.
Given a
topological space, let be the set . The morphisms from the point to the point are
equivalence classes of
continuouspaths 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, ).[5] The usual fundamental group is then the vertex group for the point .
The orbits of the fundamental groupoid are the path-connected components of . Accordingly, the fundamental groupoid of a
path-connected space is transitive, and we recover the known fact that the fundamental groups at any base point are isomorphic. Moreover, in this case, the fundamental groupoid and the fundamental groups are
equivalent as categories (see the section
below for the general theory).
An important extension of this idea is to consider the fundamental groupoid where is a chosen set of "base points". Here is a (wide) subgroupoid of , where one considers only paths whose endpoints belong to . The set may be chosen according to the geometry of the situation at hand.
Equivalence relation
If is a
setoid, i.e. a set with an
equivalence relation, 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 (denote by ) if and only if ;
The composition of and is .
The vertex groups of this groupoid are always trivial; moreover, this groupoid is in general not transitive and its orbits are precisely the equivalence classes. There are two extreme examples:
If every element of is in relation with every other element of , we obtain the pair groupoid of , which has the entire as set of arrows, and which is transitive.
If every element of is only in relation with itself, one obtains the unit groupoid, which has as set of arrows, , and which is completely intransitive (every singleton is an orbit).
Examples
If is a smooth
surjectivesubmersion of
smooth manifolds, then is an equivalence relation[6] since has a topology isomorphic to the
quotient topology of under the surjective map of topological spaces. If we write, then we get a groupoid
which is sometimes called the banal groupoid of a surjective submersion of smooth manifolds.
If we relax the reflexivity requirement and consider partial equivalence relations, then it becomes possible to consider
semidecidable notions of equivalence on computable realisers for sets. This allows groupoids to be used as a computable approximation to set theory, called PER models. Considered as a category, PER models are a cartesian closed category with natural numbers object and subobject classifier, giving rise to the
effective topos introduced by
Martin Hyland.
A Čech groupoid[6]p. 5 is a special kind of groupoid associated to an equivalence relation given by an open cover of some manifold . Its objects are given by the disjoint union
,
and its arrows are the intersections
.
The source and target maps are then given by the induced maps
and the inclusion map
giving the structure of a groupoid. In fact, this can be further extended by setting
as the -iterated fiber product where the represents -tuples of composable arrows. The structure map of the fiber product is implicitly the target map, since
is a cartesian diagram where the maps to are the target maps. This construction can be seen as a model for some
∞-groupoids. Also, another artifact of this construction is
k-cocycles
More explicitly, the action groupoid is a small category with and and with source and target maps and . It is often denoted (or for a right action). 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). Similarly, the orbits of the action groupoid are the
orbit of the group action, and the groupoid is transitive if and only if the group action is
transitive.
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 group action of on the finite set which takes 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
Any finite group that maps to gives a group action on the
affine space (since this is the group of automorphisms). Then, a quotient groupoid can be of the form , which has one point with stabilizer at the origin. Examples like these form the basis for the theory of
orbifolds. Another commonly studied family of orbifolds are
weighted projective spaces and subspaces of them, such as
Calabi–Yau orbifolds.
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 .[7]
Homological algebra
A two term complex
of objects in a
concreteAbelian category can be used to form a groupoid. It has as objects the set and as arrows the set ; 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.[8]
The transformations of the
fifteen puzzle form a groupoid (not a group, as not all moves can be composed).[9][10][11] This
groupoid acts on configurations.
^α The
closure axiom, used by many sources and defined differently, is equivalent. ^β Here, divisibility refers specifically to the
quasigroup axioms.
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.[12] Many concepts of
group theory generalize to groupoids, with the notion of
functor replacing that of
group homomorphism.
Every transitive/connected groupoid - that is, as explained above, one in which any two objects are connected by at least one morphism - is isomorphic to an action groupoid (as defined above) . By transitivity, there will only be one
orbit under the action.
Note that the isomorphism just mentioned is not unique, and there is no
natural choice. Choosing such an isomorphism for a transitive groupoid essentially amounts to picking one object , a
group isomorphism from to , and for each other than , a morphism in from to .
If a groupoid is not transitive, then it is isomorphic to a
disjoint union of groupoids of the above type, also called its connected components (possibly with different groups and sets for each connected component).
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 does not need to specify the sets , but 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 entire groupoid. Otherwise, one must choose a way to view each in terms of a single group, and this choice can be arbitrary. In the example from
topology, one 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.
Category of groupoids
The category whose objects are groupoids and whose morphisms are groupoid morphisms is called the groupoid category, or the category of groupoids, and is denoted by Grpd.
The category Grpd is, like the category of small categories,
Cartesian closed: for any groupoids we can construct 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.
Another important property of Grpd is that it is both
complete and
cocomplete.
There is an additional structure which can be derived from groupoids internal to the category of groupoids, double-groupoids.[13][14] Because Grpd is a 2-category, these objects form a 2-category instead of a 1-category since there is extra structure. Essentially, these are groupoids with functors
and an embedding given by an identity functor
One way to think about these 2-groupoids is they contain objects, morphisms, and squares which can compose together vertically and horizontally. For example, given squares
and
with the same morphism, they can be vertically conjoined giving a diagram
which can be converted into another square by composing the vertical arrows. There is a similar composition law for horizontal attachments of squares.
Groupoids arising from geometry often possess further structures which interact with the groupoid multiplication. For instance, in
Poisson geometry one has the notion of a
symplectic groupoid, which is a Lie groupoid endowed with a compatible
symplectic form. Similarly, one can have groupoids with a compatible
Riemannian metric, or
complex structure, etc.
^
Proof of first property: from 2. and 3. we obtain a−1 = a−1 * a * a−1 and (a−1)−1 = (a−1)−1 * a−1 * (a−1)−1. Substituting the first into the second and applying 3. two more times yields (a−1)−1 = (a−1)−1 * a−1 * a * a−1 * (a−1)−1 = (a−1)−1 * a−1 * a = a. ✓
Proof of second property: since a * b is defined, so is (a * b)−1 * a * b. Therefore (a * b)−1 * a * b * b−1 = (a * b)−1 * a is also defined. Moreover since a * b is defined, so is a * b * b−1 = a. Therefore a * b * b−1 * a−1 is also defined. From 3. we obtain (a * b)−1 = (a * b)−1 * a * a−1 = (a * b)−1 * a * b * b−1 * a−1 = b−1 * a−1. ✓
^J.P. May, A Concise Course in Algebraic Topology, 1999, The University of Chicago Press
ISBN0-226-51183-9 (see chapter 2)
^Mapping a group to the corresponding groupoid with one object is sometimes called delooping, especially in the context of
homotopy theory, see
"delooping in nLab". ncatlab.org. Retrieved 2017-10-31..
^Cegarra, Antonio M.; Heredia, Benjamín A.; Remedios, Josué (2010-03-19). "Double groupoids and homotopy 2-types".
arXiv:1003.3820 [
math.AT].
Brandt, H (1927), "Über eine Verallgemeinerung des Gruppenbegriffes", Mathematische Annalen, 96 (1): 360–366,
doi:
10.1007/BF01209171,
S2CID119597988
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.
Dicks, Warren; Ventura, Enric (1996), The group fixed by a family of injective endomorphisms of a free group, Mathematical Surveys and Monographs, vol. 195, AMS Bookstore,
ISBN978-0-8218-0564-0
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.
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)