Groupoid

From Wikipedia, the free encyclopedia

In abstract algebra, a branch of mathematics, especially in category theory and homotopy theory, a groupoid generalises the notion of group and of category 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 an isomorphism. A category of this sort can be viewed as augmented with a unary operation, called inverse by analogy with group theory.

Special cases include:

• Setoids, that is: sets which come with an equivalence relation;
• G-sets, sets equipped with an action of a group G.

Groupoids are often used to reason about geometrical objects such as manifolds. Heinrich Brandt introduced groupoids in 1926.

Contents 1 Definitions 1.1 Algebraic 1.2 Category theoretic 1.3 Comparing the definitions 1.4 Groupoid Category 2 Examples 2.1 Linear algebra 2.2 Topology 2.3 Equivalence relation 2.4 Group action 2.5 Fifteen puzzle 3 Relation to groups 4 Lie groupoids and Lie algebroids 5 References

[edit] Definitions

[edit] Algebraic

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

and ^-1 have the following axiomatic properties. Let a, b, and c be elements of G. Then:

• Associativity: If a * b and b * c are defined, then (a * b) * c and a * (b * c) are defined and equal. Conversely, if either of these last two expressions is defined, then so is the other (and again they are equal).
• Inverse: a^-1 * a and a * a^-1 are always defined.
• Identity: If a * b is defined, then a * b * b^-1 = a, and a^-1 * a * b = b. (The previous two axioms already show that these expressions are defined and unambiguous.)

In short:

• (a * b) * c = a * (b * c);
• (a * b) * b^-1 = a;
• a^-1 * (a * b) = b.

From these axioms, two easy and convenient theorems follow:

• (a^-1)^-1 = a;
• If a * b is defined, then (a * b)^-1 = b^-1 * a^-1.

[edit] Category theoretic

A groupoid is a small category in which every morphism is an isomorphism, and hence invertible. More precisely, a groupoid G is:

• A set G₀ of objects;
• For each pair of objects x and y in G₀, 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).

The objects and morphisms have the properties:

• For every object x, there exists the element id_x of G(x,x);
• For each triple of objects x, y, and z, there exists the function comp_x,y,z: G(x,y)G(y,z) → G(x,z). We write gf for comp_x,y,z(f,g), where fG(x,y), and gG(y,z);
• There exists the function inv_x,y: G(x,y) → G(y,x).

Moreover, if f : x → y, g : y → z, and h : z → w, then:

• fid_x = f and id_yf = f;
• (hg)f = h(gf);
• finv(f) = id_y and inv(f)f = id_x.

[edit] Comparing the definitions

The algebraic and category-theoretic definitions are equivalent, 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 comp and inv become partially defined operations on G, and inv will in fact be defined everywhere; so we define * to be comp and ^{− 1} to be inv. Thus we have a groupoid in the algebraic sense. Explicit reference to G₀ (and hence to id) can be dropped.

Conversely, given a groupoid G in the algebraic sense, with typical element f, let G₀ be the set of all elements of the form f*f^-1. In other words, the objects are identified with the identity morphisms, so that id_x is just x. Let G(x,y) be the set of all elements f such that yfx is defined. Then ^-1 and * break up into several functions on the various G(x,y), which may be called inv and comp, respectively.

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

[edit] Groupoid Category

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

[edit] Examples

[edit] Linear algebra

Given a field K, the corresponding general linear groupoid GL_*(K) consists of all invertible matrices whose entries range over K. Matrix multiplication interprets composition. If G = GL_*(K), then the set of natural numbers is a proper subset of G₀, since for each natural number n, there is a corresponding identity matrix of dimension n. G(m,n) is empty unless m=n, in which case it is the set of all nxn invertible matrices.

[edit] Topology

Given a topological space X, let G₀ 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 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 π₁(X).

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

[edit] Equivalence relation

If X 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 X;
• For any two elements x and y in X, there is a single morphism from x to y if and only if x~y.

[edit] 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;
• For any two elements x and y in X, there is a morphism from x to y corresponding to every element g of G such that gx = y;
• Composition of morphisms interprets the binary operation of G.

Another way to describe G-sets is the functor category [Gr,Set], where 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(Gr) and for every g in G (i.e. for every morphism in Gr) induces a bijection F_g : X→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 : Gr→Set is the Cayley representation of G. In fact, this functor is isomorphic to Hom(Gr, − ) and so sends ob(Gr) to the set Hom(Gr,Gr) which is by definition the "set" G and the morphism g of 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 | g∈G}, a subgroup of the group of permutations of G.

[edit] 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.

[edit] Relation to groups

Group-like structures
	Totality	Associativity	Identity	Inverses
Group	Yes	Yes	Yes	Yes
Monoid	Yes	Yes	Yes	No
Semigroup	Yes	Yes	No	No
Loop	Yes	No	Yes	Yes
Quasigroup	Yes	No	No	Yes
Magma	Yes	No	No	No
Groupoid	No	Yes	Yes	Yes
Category	No	Yes	Yes	No

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 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 the mapping g → fgf ⁻¹.

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 for each 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₀, a group isomorphism h from G(x₀) to G, and for each x other than x₀, a morphism in G from x₀ 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, one need not 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 an isomorphism requires specifying the set of points in each component;
• The set X 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 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 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 G(x) 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 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 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 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 about presentations of the subgroup H. For further information, see the books by Higgins and by Brown in the References.

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

[edit] 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.

[edit] References

• F. Borceux, G. Janelidze, 2001, Galois theories. Cambridge Univ. Press. Shows how generalisations of Galois theory lead to Galois groupoids.
• 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.
• --------, Higher dimensional group theory Explains how the groupoid concept has to led to higher dimensional homotopy groupoids, having applications in homotopy theory and in group cohomology. Many references.
• 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., 1971. Categories and groupoids. Van Nostrand Notes in Mathematics. Now downloadable. Applications of groupoids in group theory, for example to a generalisation of Grushko's theorem, and in topology. Good introduction to category theory.
• 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.
• Mackenzie, K. C. H., 2005. General theory of Lie groupoids and Lie algebroids. Cambridge Univ. Press.
• Weinstein, Alan, "Groupoids: unifying internal and external symmetry." Also available in Postscript.