# Equivalence relations not associated with a group

This is a vague question; so vague that I wonder if anyone will get it. Many, perhaps most, equivalence relations that are regularly used in mathematics correspond to the orbits of some group action that is also regularly used. Examples:

1. Congruence of integers modulo $m$ corresponds to the orbits of the action $x\mapsto x+m$ of the infinite cyclic group on the integers.
2. Similarity of matrices corresponds to the orbits of the general linear group in its action by conjugation on the set of all matrices.
3. Consider the symmetric group in its standard action on a set $V$. It also acts on the set of all graphs on $V$ by relabelling of the vertices, and the orbits of this action are the isomorphism classes of graphs.

Of course, given any equivalence relation, we can invent any number of groups whose orbits are the equivalence classes. But in each of the examples the group is not just made up but somehow arises naturally from the problem (told you this is a vague question).

My question is: what equivalence relations are in common use (not just made up now!) that do not correspond to the orbits of a group that arises naturally? I can't define phrases like "arises naturally", but most mathematicians have some intuition concerning what that means so I'm hoping this question is not totally meaningless.

• Perhaps I'm missing something in the nature of this question (e.g. algebraic/categorical examples are desired), but is there a reason no one has mentioned the almost everywhere equivalence of functions in $L^p$ spaces that everyone sees in a beginning graduate real analysis class? Sep 19, 2021 at 18:26

1. The equivalence of being in the same strong component of a digraph.
2. The equivalence associated to a preorder.
3. Morita equivalence of algebras.
4. von Neumann-Murray equivalence of projections.
5. Green's relations in semigroup theory.
6. The equivalence relation of being smashed by a mapping $f$.
7. Homotopy equivalence of maps or spaces.

Following the answer of nsrt, there are many actions of groupoids. In fact there are equivalences of categories for a groupoid $G$:

1. Functors $G \to Sets$;

2. Operations of $G$ on sets ( for an operation of $G$ on $X$ we need a function $w:X \to Ob(G)$ and if $x\in X$ and $g: wx \to p$ then $w(xg) =y$, and we have the usual axioms);

3. Covering morphisms of groupoids $\widetilde{G} \to G$ (a covering morphism . has unique lifting).

The last description is somewhat neglected in the literature, but it is often convenient (note that a covering map of spaces is modelled by a covering morphism of fundamental groupoids, which is a quite natural analogy, whereas an action, particularly of a group, is one further step away).

Grothendieck has a remark that he was trying to generalise quotienting operations and eventually realised that what he needed was a groupoid internal to a given category of interest!

Taking path components of a topological space. (And by applying this to mapping spaces: homotopy of maps).

However, the path groupoid acts.

• Of course, every equivalence relation is a groupoid... Aug 7, 2013 at 17:31
• Yes, this is more or less the point I wanted to make. And here as in many cases (see also Karol's answer), the underlying structure is an $\infty$-groupoid.
– nsrt
Aug 8, 2013 at 7:35

Since this question has been bumped to the front page, let me add Turing equivalence of subsets of $$\mathbb N$$. (Two such subsets are Turing equivalent iff each is computable by a Turing machine equipped with an oracle for the other.)

Three examples off the top of my head. (I will not bet that some group actions cannot be manufactured for these, but I can't see any natural ones.)

1. For any (small) category $\mathcal{C}$ the equivalence relation of being isomorphic on the set of objects of $\mathcal{C}$. One instance used all the time is when $\mathcal{C}$ is the category of finitely generated projective modules over a ring. (In a sense nsrt's example is also an instance: path components of a space $X$ are the "isomorphism classes" of its objects when we see $X$ as an $\infty$-groupoid.)

2. All sorts of colimits in categories of structured sets can be constructed as quotients by equivalence relations. For example, if you attach a cell to a space $X$ via a map $f : \partial D^m \to X$ you mod out an equivalence relation on $D^m \sqcup X$ that identifies $x$ with $f(x)$ for all $x \in \partial D^m$.

3. Declare two spectra $X$ and $Y$ to be equivalent if for every spectrum $Z$ we have $X \wedge Z \simeq 0$ if and only if $Y \wedge Z \simeq 0$. Equivalence classes of this relation are called Bousfield classes and the set of all such forms a lattice called the Bousfield lattice and captures all sorts of interesting information about the stable homotopy category.

1) Let a semigroup $S$ acts on a set $X$. Define relation $\rho=\{(x,y)\in X\times X\,|\, \exists\, a,b\in S \ \ ax=by\}$ and then take the least congruence containing $\rho$ (its classes are called sometimes orbits of the action).

2) If a group $G$ partially acts on $X$ (see definition in: J.Kellendonk, M.V.Lawson, Partial actions of groups, International Journal of Algebra and Computation 14 (01), 87-114) then an equvivalence arises: $x\sim y$ iff $\varnothing\ne ax=y$ for some $a\in G$.