What are permutable equivalence relations intuitively?

Question

What are permutable equivalence relations, and what are they used for? What is the idea behind them? Could someone give me an example and a counterexample for finite sets?

I have encountered the notion in the book Lattice Theory by Birkhoff, Chapter IV, Paragraph 9. Theorem 13 says (paraphrasing a little):

Two permutable equivalence relations on the same set form a modular pair in the dual of the partition lattice.

The problem is that, according to the index at the end of the book, the notion of permutable relations appears first on that very page.

Answer 1

EDIT: I believe the terminology is as follows: two congruences $\sigma$ and $\rho$ on an algebra $A$ are permutable if $\sigma\rho=\rho\sigma$, that is, if we have $$\{(a, b): \exists c(a\rho c, c\sigma b)\}=\{(a, b): \exists c'(a\sigma c', c'\rho b)\}.$$ See e.g. https://en.wikipedia.org/wiki/Congruence-permutable_algebra.

Let me give a somewhat degenerate example, that I hope shows how permutability can be a useful property:

Let's say I'm working with the congruence lattice $L$ of a group $G$. Then I claim every pair of elements of $L$ is permutable! That is, groups are congruence permutable. Why? Well, suppose $a\sigma\rho b$ - that is, there is some $c$ such that $a\sigma c\rho b$. Well, since congruence relations on groups correspond to normal subgroups, this means that

• $ax=c$ for some $x\in X$

and

• $cy=b$ for some $y\in Y$

where $X, Y$ are the normal subgroups corresponding to $\sigma$ and $\rho$. So we have $axy=b$. But then $ayy^{-1}xy=b$, that is, $ay(y^{-1}xy)=b$. Since $X$ is normal, we have $y^{-1}xy\in X$ - call this $x'$. So $ayx'=b$. But this means $a\rho\sigma b$!

OK, so what? Well, it's now easy to check that $\rho\sigma$ is a congruence on $G$, and in fact is the least upper bound of $\rho$ and $\sigma$; and from this we can easily show (a good exercise) that $L$ is modular (this is Dedekind's theorem).

So in general, I would say that instances of permutability in a congruence lattice correspond to places in the lattice which are "locally modular", in some informal sense.

Answer 2

The example given by Noah is rather paradigmatic. That is, algebras all of whose congruence relations permute have a lot of nice structure around.

The proof he gave that groups are congruence-permutable cam be greatly generalized to the following characterization. TFAE for an equational class of algebras $\mathcal{V}$:

1) every algebra in $\mathcal{V}$ has permutable congruences; and

2) there exists a term (derived operation) $p(x,y,z)$ such that $$ p(x,x,z)=p(z,x,x)=z $$ hold identically across $\mathcal{V}$.

In the case of groups, $$ p(x,y,z):=xy^{-1}z $$ works.

One benefit of having permutable congruences is that the join of two congruences $\theta,\delta$ (the least upper bound) is given by the relational composition $\theta\circ\delta$ of the congruences. In the general case, you should take the union of all the finite compositions, thus an infinitely expression. Another aspect of the same phenomenon is that you can which pair of congruences correspond to direct product decompositions of your algebra; in the congruence-permutable case, only they're exactly the pairs of complementary congruences (that is, you only have to look at the drawing of the lattice of congruences to decide this).

Finally, congruences of lattices usually do not permute and in general the set of all equivalence relations on a set with more than 2 elements. If you take the lattice given by the chain of 3 elements $\{0,a,1\}$ with $0<a<1$, then the congruences $\theta,\delta$ generated by the pairs $(0,a)$ and $(1,a)$, respectively, not permute (for instance, $0\theta a\delta 1$ but there is no $b$ such that $1\theta b\delta 0$).