permutable congruences

Let A be an algebraic system and Θ1 and Θ2 are two congruencesPlanetmathPlanetmathPlanetmathPlanetmath on A. Θ1 and Θ2 are said to be permutable if Θ1Θ2=Θ2Θ1, where is the composition of relations.

For example, let A be the direct productPlanetmathPlanetmathPlanetmathPlanetmath of A1 and A2. Define Θ1 on A as follows:

(a,b)(c,d)(modΘ1) iff a=c.

Then Θ1 is clearly an equivalence relationMathworldPlanetmath on A. For any n-ary operator f on A, let f1 and f2 be the corresponding n-ary operators on A1 and A2 respectively: f=(f1,f2). Suppose (ai,bi)(ci,di)(modΘ1), i=1,,n. Then

f((a1,b1),,(an,bn)) = (f1(a1,,an),f2(b1,,bn)) (1)
(f1(c1,,cn),f2(d1,,dn)) (2)
= f((c1,d1),,(cn,dn))(modΘ1). (3)

The equivalence of (1) and (2) follows from the assumptionPlanetmathPlanetmath that ai=ci for each i=1,,n, so that f1(a1,,an)=f1(c1,,cn). Similarly define

(a,b)(c,d)(modΘ2) iff b=d.

By a similar argument, Θ2 is a congruence on A too. Pick any (a,b),(c,d)A. Then (a,b)(a,d)(modΘ1) and (a,d)(c,d)(modΘ2) so that (a,b)(Θ1Θ2)(c,d). This implies that Θ1Θ2=A2. Similarly Θ2Θ1=A2. Therefore, Θ1 and Θ2 are permutable.

In fact, we have the following:

Proposition 1.

Let A be an algebraic system with congruenes Θ1 and Θ2. Then Θ1 and Θ2 are permutable iff Θ1Θ2=Θ1Θ2, where is the join operationMathworldPlanetmath on, Con(A), the lattice of congruences on A.


Clearly, if Θ1Θ2=Θ1Θ2, then they are permutable. Conversely, suppose they are permutable. Let C=Θ1Θ2 and D=Θ1Θ2. We want to show that C=D. If (a,b)C, then there is cA such that (a,c)Θ1 and (c,b)Θ2, so ab(modD). This shows CD. If ab(modD), then there is cA such that ac(modR) and cb(modS) with R,S{Θ1,Θ2}. If R=S, then we are done, since ΘiC (as an element (a,b) belonging to, say Θ1, can be written as (a,b)(b,b)C). If R=Θ1 and S=Θ2 then we are done too, since this is just the definition of C. If R=Θ2 and S=Θ1, then (a,b)Θ2Θ1=Θ1Θ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 Θ and Φ on A such that ΘΦ=A2 and ΘΦ=Δ, where Δ={(a,a)aA} is the diagonal relation on A, and that BA/Θ and CA/Φ. 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