# permutable congruences

Let $A$ be an algebraic system and $\Theta_{1}$ and $\Theta_{2}$ are two congruences on $A$. $\Theta_{1}$ and $\Theta_{2}$ are said to be permutable if $\Theta_{1}\circ\Theta_{2}=\Theta_{2}\circ\Theta_{1}$, where $\circ$ is the composition of relations.

For example, let $A$ be the direct product of $A_{1}$ and $A_{2}$. Define $\Theta_{1}$ on $A$ as follows:

 $(a,b)\equiv(c,d)\pmod{\Theta_{1}}\quad\mbox{ iff }\quad a=c.$

Then $\Theta_{1}$ is clearly an equivalence relation on $A$. For any $n$-ary operator $f$ on $A$, let $f_{1}$ and $f_{2}$ be the corresponding $n$-ary operators on $A_{1}$ and $A_{2}$ respectively: $f=(f_{1},f_{2})$. Suppose $(a_{i},b_{i})\equiv(c_{i},d_{i})\pmod{\Theta_{1}}$, $i=1,\ldots,n$. Then

 $\displaystyle f((a_{1},b_{1}),\ldots,(a_{n},b_{n}))$ $\displaystyle=$ $\displaystyle(f_{1}(a_{1},\ldots,a_{n}),f_{2}(b_{1},\ldots,b_{n}))$ (1) $\displaystyle\equiv$ $\displaystyle(f_{1}(c_{1},\ldots,c_{n}),f_{2}(d_{1},\ldots,d_{n}))$ (2) $\displaystyle=$ $\displaystyle f((c_{1},d_{1}),\ldots,(c_{n},d_{n}))\pmod{\Theta_{1}}.$ (3)

The equivalence of (1) and (2) follows from the assumption that $a_{i}=c_{i}$ for each $i=1,\ldots,n$, so that $f_{1}(a_{1},\ldots,a_{n})=f_{1}(c_{1},\ldots,c_{n})$. Similarly define

 $(a,b)\equiv(c,d)\pmod{\Theta_{2}}\quad\mbox{ iff }\quad b=d.$

By a similar argument, $\Theta_{2}$ is a congruence on $A$ too. Pick any $(a,b),(c,d)\in A$. Then $(a,b)\equiv(a,d)\pmod{\Theta_{1}}$ and $(a,d)\equiv(c,d)\pmod{\Theta_{2}}$ so that $(a,b)(\Theta_{1}\circ\Theta_{2})(c,d)$. This implies that $\Theta_{1}\circ\Theta_{2}=A^{2}$. Similarly $\Theta_{2}\circ\Theta_{1}=A^{2}$. Therefore, $\Theta_{1}$ and $\Theta_{2}$ are permutable.

In fact, we have the following:

###### Proposition 1.

Let $A$ be an algebraic system with congruenes $\Theta_{1}$ and $\Theta_{2}$. Then $\Theta_{1}$ and $\Theta_{2}$ are permutable iff $\Theta_{1}\circ\Theta_{2}=\Theta_{1}\vee\Theta_{2}$, where $\vee$ is the join operation on, $\operatorname{Con}(A)$, the lattice of congruences on $A$.

###### Proof.

Clearly, if $\Theta_{1}\circ\Theta_{2}=\Theta_{1}\vee\Theta_{2}$, then they are permutable. Conversely, suppose they are permutable. Let $C=\Theta_{1}\circ\Theta_{2}$ and $D=\Theta_{1}\vee\Theta_{2}$. We want to show that $C=D$. If $(a,b)\in C$, then there is $c\in A$ such that $(a,c)\in\Theta_{1}$ and $(c,b)\in\Theta_{2}$, so $a\equiv b\pmod{D}$. This shows $C\subseteq D$. If $a\equiv b\pmod{D}$, then there is $c\in A$ such that $a\equiv c\pmod{R}$ and $c\equiv b\pmod{S}$ with $R,S\in\{\Theta_{1},\Theta_{2}\}$. If $R=S$, then we are done, since $\Theta_{i}\subseteq C$ (as an element $(a,b)$ belonging to, say $\Theta_{1}$, can be written as $(a,b)\circ(b,b)\in C$). If $R=\Theta_{1}$ and $S=\Theta_{2}$ then we are done too, since this is just the definition of $C$. If $R=\Theta_{2}$ and $S=\Theta_{1}$, then $(a,b)\in\Theta_{2}\circ\Theta_{1}=\Theta_{1}\circ\Theta_{2}=C$, by permutability. ∎

Remark. From the example above, it is not hard to see that an algebraic system $A$ is the direct product of two algebraic systems $B,C$ iff there are two permutable congruences $\Theta$ and $\Phi$ on $A$ such that $\Theta\vee\Phi=A^{2}$ and $\Theta\wedge\Phi=\Delta$, where $\Delta=\{(a,a)\mid a\in A\}$ is the diagonal relation on $A$, and that $B\cong A/\Theta$ and $C\cong A/\Phi$. This result can be generalized to arbitrary direct products.

Title permutable congruences PermutableCongruences 2013-03-22 17:09:29 2013-03-22 17:09:29 CWoo (3771) CWoo (3771) 6 CWoo (3771) Definition msc 08A30 completely permutable