# An analogy between subgroups and equivalence relations.

I have noticed a certain analogy between subgroups of a group $G$ and equivalence relations on a set $X$. I would like to know if there's an explanation for this analogy or a common generalization of the two facts I have in mind.

Here are the facts.

Fact 1. Let $G$ be a group. Then we can multiply subsets of $G$ in a standard way. For two subgroups $R$ and $S$ of $G$, the product $RS$ is a subgroup of $G$ iff $RS=SR$. If that is the case, $RS=SR$ is the join of $R$ and $S$ in the lattice of subgroups of $G$.

Fact 2. Let $X$ be a set. Then we can compose binary relations on $X$ in a standard way. For two equivalence relations $\rho$ and $\sigma$, the composition $\rho\circ\sigma$ is an equivalence relation on $X$ iff $\rho\circ\sigma=\sigma\circ\rho$. If that is the case, $\rho\circ\sigma=\sigma\circ\rho$ is the join of $\rho$ and $\sigma$ in the lattice of equivalence relations on $X$.

-
Not a complete explanation, but: if $G$ is a group and $S$ a subset of $G$, we can associate to $S$ the relation $R_S$ defined by $$x R_S y \Leftrightarrow \exists s \in S : y = xs.$$ The composition of these relations describes composition of subsets. –  Qiaochu Yuan Jun 7 '12 at 1:17
A useful word is "congruence relation". A congruence relation is an equivalence relation that respects the operations of your structure: in this case, that $a \equiv b$ and $c \equiv d$ imply $ac \equiv bd$. –  Hurkyl Jun 7 '12 at 4:25
@QiaochuYuan Thanks! I've checked that it gives a monomorphism $\phi:(2^G,\cdot)\to(2^{G\times G},\circ),$ which also respects $\cap$ and $\cup$. Is $\phi(2^G)$ exactly the set $I_r$ of all right invariant binary relations on $G$? I've checked that $\phi(2^G)\subseteq I_r$, but I can't prove the other inclusion. –  user23211 Jun 7 '12 at 15:21

An equivalence relation $∼$ on a set $S$ with composition law is called left invariant if $x ∼ x′$ implies $yx ∼ yx′$ for all $x, x ′, y \in S$ and right invariant if $x ∼ x′$ implies $xy ∼ x′y$ for all $x, x ′ , y \in S.$ We say $∼$ is a congruence on $S$ if it is both left and right invariant.

Theorem: Suppose $∼$ is an equivalence relation on a group $G$ and let $H= [ 1 ].$ Then

1. $∼$ is left invariant iff $H$ is a subgroup of $G$ and $[x]=xH$ for all $x\in G.$
2. $∼$ is right invariant iff $H$ is a subgroup of $G$ and $[x]=Hx$ for all $x\in G.$
3. $∼$ is a congruence iff $H$ is a normal subgroup of $G$ and $[x]=Hx=xH$ for all $x\in G.$

So the reason for your analogy is due to the left/right invariance that your equivalence relation satisfies.

-
I think you've a nice idea, and here's another one on the same general line: let $\,G\,$ be any group, and take a subgroup $\,H\leq G\,$ .
We can define a relation $\,\sim_H\,$ on $\,G\,$ as follows: for $$\,x,y\in G\,,\,x\,\sim_H\,y\Longleftrightarrow y^{-1}x\in H$$
The above is an equivalence relation, and its eq. classes are just the different left cosets $\,xH\,$