## You are here

Homepermutable congruences

## Primary tabs

# 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)\;\;(\mathop{{\rm mod}}\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})\;\;(\mathop{{\rm mod}}\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}))\;\;(\mathop{{\rm mod}}% \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)\;\;(\mathop{{\rm mod}}\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)\;\;(\mathop{{\rm mod}}\Theta_{1})$ and $(a,d)\equiv(c,d)\;\;(\mathop{{\rm mod}}\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\;\;(\mathop{{\rm mod}}D)$. This shows $C\subseteq D$. If $a\equiv b\;\;(\mathop{{\rm mod}}D)$, then there is $c\in A$ such that $a\equiv c\;\;(\mathop{{\rm mod}}R)$ and $c\equiv b\;\;(\mathop{{\rm mod}}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.

## Mathematics Subject Classification

08A30*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections