permutable congruences

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

For example, let $A$ be the direct product of $A_1$ and $A_2$. Define ${\mathrm{\Theta }}_1$ on $A$ as follows:

$$(a,b)\equiv (c,d)(mod{\mathrm{\Theta }}_1)\mathit{\hspace{1em}}\text{ iff }\mathit{\hspace{1em}}a=c.$$

Then ${\mathrm{\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)(mod{\mathrm{\Theta }}_1)$, $i=1,\mathrm{\dots },n$. Then

$f((a_1,b_1),\mathrm{\dots },(a_n,b_n))$ $=$ $(f_1(a_1,\mathrm{\dots },a_n),f_2(b_1,\mathrm{\dots },b_n))$ (1)

$\equiv$ $(f_1(c_1,\mathrm{\dots },c_n),f_2(d_1,\mathrm{\dots },d_n))$ (2)

$=$ $f((c_1,d_1),\mathrm{\dots },(c_n,d_n))(mod{\mathrm{\Theta }}_1).$ (3)

The equivalence of (1) and (2) follows from the assumption that $a_i=c_i$ for each $i=1,\mathrm{\dots },n$, so that $f_1(a_1,\mathrm{\dots },a_n)=f_1(c_1,\mathrm{\dots },c_n)$. Similarly define

$$(a,b)\equiv (c,d)(mod{\mathrm{\Theta }}_2)\mathit{\hspace{1em}}\text{ iff }\mathit{\hspace{1em}}b=d.$$

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

In fact, we have the following:

Proposition 1.

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

Proof.

Clearly, if ${\mathrm{\Theta }}_1\circ {\mathrm{\Theta }}_2={\mathrm{\Theta }}_1\vee {\mathrm{\Theta }}_2$, then they are permutable. Conversely, suppose they are permutable. Let $C={\mathrm{\Theta }}_1\circ {\mathrm{\Theta }}_2$ and $D={\mathrm{\Theta }}_1\vee {\mathrm{\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 {\mathrm{\Theta }}_1$ and $(c,b)\in {\mathrm{\Theta }}_2$, so $a\equiv b(modD)$. This shows $C\subseteq D$. If $a\equiv b(modD)$, then there is $c\in A$ such that $a\equiv c(modR)$ and $c\equiv b(modS)$ with $R,S\in \{{\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2\}$. If $R=S$, then we are done, since ${\mathrm{\Theta }}_i\subseteq C$ (as an element $(a,b)$ belonging to, say ${\mathrm{\Theta }}_1$, can be written as $(a,b)\circ (b,b)\in C$). If $R={\mathrm{\Theta }}_1$ and $S={\mathrm{\Theta }}_2$ then we are done too, since this is just the definition of $C$. If $R={\mathrm{\Theta }}_2$ and $S={\mathrm{\Theta }}_1$, then $(a,b)\in {\mathrm{\Theta }}_2\circ {\mathrm{\Theta }}_1={\mathrm{\Theta }}_1\circ {\mathrm{\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 $\mathrm{\Theta }$ and $\mathrm{\Phi }$ on $A$ such that $\mathrm{\Theta }\vee \mathrm{\Phi }=A^2$ and $\mathrm{\Theta }\wedge \mathrm{\Phi }=\mathrm{\Delta }$, where $\mathrm{\Delta }=\{(a,a)\mid a\in A\}$ is the diagonal relation on $A$, and that $B\cong A/\mathrm{\Theta }$ and $C\cong A/\mathrm{\Phi }$. This result can be generalized to arbitrary direct products.

Title	permutable congruences
Canonical name	PermutableCongruences
Date of creation	2013-03-22 17:09:29
Last modified on	2013-03-22 17:09:29
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	6
Author	CWoo (3771)
Entry type	Definition
Classification	msc 08A30
Defines	completely permutable