Orbit-finite groupoids

Orbit-finite groups are finite, and therefore not very interesting from the perspective of sets with atoms. It turns out that orbit-finite groupoids form interesting structures. They will be useful in the study of orbit-finite semigroups in the following post.

The following lemma appears in On the use of guards for logics with data by Thomas Colcombet, Clemens Ley and Gabriele Puppis (with a different proof).

Lemma 1. Any orbit-finite group G is finite.

Proof. For simplicity, assume that G is equivariant. It follows that the neutral element of G is equivariant and also the inversion mapping is equivariant.

Observe that

    \[h\cdot( h^{-1}\cdot g)=g\]

for any g,h\in G. Fix g\in G to be of maximal support cardinality. Choose any h\in G whose support is disjoint from the support of g. It follows from the above equation that \sup{g} is contained in \sup{h}\cup\sup{h^{-1}\cdot g}. But \sup{h} is disjoint from \sup{g}, so in fact, \sup{g} is contained in \sup{h^{-1}g}. By maximality, it follows that


Assuming that G is infinite, there are infinitely many elements h whose support is disjoint from the support of g, and for each of them, the above equality holds. However, in an orbit-finite set there are only finitely many elements whose support is equal to \sup{g}. It follows that for two distinct elements h_1,h_2, we have h_1^{-1}g=h_2^{-1}g, a contradiction.\square

A groupoid is a small category whose morphisms (arrows) are isomorphisms. In other words, it is a set of objects O, a set of arrows M, together with two mappings {\textrm{source}},{\textrm{target}}:M\to O and a partial composition function M\times M\to M, such that s;t is defined if and only if {\textrm{target}}(s)={\textrm{source}}(s), and such that natural axioms are satisfied:

  • associativity: the result (or lack of thereof) of composing three arrows does not depend on the order of applying composition;
  • neutrality: for every object o there is an identity morphism 1_o which is the left identity for every morphism from o and right identity for every morphism to o;
  • invertibility: every morphism has an inverse in the other direction such that the two compositions yield the identities on the source and target.

If x,y are two objects, then by M(x,y) we denote the set of arrows with domain x and range y.

An orbit-finite groupoid is a groupoid where all the components are orbit-finite. In the rest of this post we will assume that groupoids are equivariant, i.e., all the components are equivariant.

A groupoid is connected if for every two objects there is an arrow between them, i.e., M(x,y) is nonempty for any two objects x,y.

Example. Fix a single orbit alphabet A and define the groupoid \textrm{Iso}_A whose objects are elements of A, and whose arrows are triples (a,\alpha,b) such that a,b\in A and \alpha:\sup a\to\sup b is a bijection such that \hat\alpha(a)=b for any atom permutation \hat\alpha extending \alpha. Then \textrm{Iso}_A is a connected orbit-finite groupoid. For example, if A is the set of unordered pairs of atoms, then the morphisms of \textrm{Iso}_A are bijections between two-element sets of atoms, with the natural composition in case when the domain and range agree.

Lemma 2. Let M be a connected groupoid and let G=M(u,u) for some fixed object u. Then, (G, ;) is a group, and for any two objects x,y, the set M(x,y) is in bijection with G.

Corollary. In an orbit-finite groupoid, there are finitely many arrows between any two objects.

Lemma 3. In an orbit-finite groupoid, for any object x, every arrow from x to x has the same support as x.

Proof. Let f be an arrow from x to x. Then f supports x, since x is the source of f, i.e., can be obtained from f by applying the equivariant source mapping. This shows that \sup x\subseteq\sup f.

Suppose that \sup x\subsetneq\sup f. By applying to f any permutation \pi which is the identity on \sup x we obtain an arrow \pi(f) whose source and target is equal to \pi(x)=x. If \sup x\subsetneq\sup f then we may obtain infinitely many distinct such arrows of the form \pi(f), contradicting the above corollary which states that there are finitely many arrows from x to x. \square

Question 1. Is there a structure theorem for orbit-finite groupoids? In particular, is every connected orbit-finite groupoid is equivariantly isomorphic to \textrm{Iso}_A, for some orbit-finite alphabet A? This is false – consider for instance a finite groupoid. Is every orbit-finite groupoid is equivariantly isomorphic to \textrm{Iso}_A\times G, where G is a finite groupoid? This is also false, as witnessed by the following example.

Example. The groupoid here consists of directed matchings from an unordered pair of atoms to an unordered pair of atoms, where each edge is directed and labeled by 0 or 1. Composition f;g of two such matchings is defined if the target-set of f is equal to the source-set of g; in this case, the resulting matching is obtained by composing the arrows and adding the labels modulo 2. This forms a groupoid.

Question 2. Can groupoids be straightened (see the previous post), i.e., is every groupoid a image of a straight groupoid (one whose set of objects and set of arrows is a straight set) under an equivariant groupoid homomorphism (a functor of categories)?

In the following post, we will argue that groupoids arise naturally in the study of orbit-finite semigroups.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>