Congruences and Quotient Algebras

Previously: Algebras

Suppose we have an algebra (X,F) where X is a set of elements and F is a set of operations. We would like to construct a smaller algebra from (X,F) that still "preserves the operations in F" in some sense.

Why would anyone do this? Think of this smaller algebra as the original algebra with some information abstracted away. In my previous post, I demonstrated how you can use certain algebras to model the integers under addition or logical propositions. You may want to examine relationships not between individual elements, but collections of elements that behave similarly under the algebra’s operations, like the relationship between even and odd integers, or logical propositions that become logically equivalent if some statement is assumed to be true. If you collapse each collection of similar elements to a single element in the new algebra, you can ignore intra-collection differences and focus on inter-collection differences.

A reasonable starting point is to consider the image of (X,F) under a homomorphism. Homomorphisms are functions between the element sets of algebras of the same type that preserve operations: for any m : (X,F) → (X′,F) and any f in F, m(f(x₀,x₁…x_n)) = f(m(x₀),m(x₁)…m(x_n)) (since (X,F) and (X′,F) are of the same type, f is an operation on both X and X′). m can map two elements of X to the same output, but can never map one element to more than one distinct output. So the image of (X,F) under m looks like (X,F) with 0 or more its points identified. Let’s describe the image in terms of a relation on (X,F): R(x,y) if and only if m(x) = m(y).

Can we identify any points we want, i. e, can we find a homomorphism m whose image corresponds to any arbitrary relation R? Not if we want equality to make sense:

• if R isn’t reflexive, then ¬R(x,x) implies m(x) ≠ m(x)

• if R isn’t symmetric, then R(x,y) and ¬R(y,x) implies m(x) = m(y), but m(y) ≠ m(x)

• if R isn’t transitive, then R(x,y), R(y,z) and ¬R(x,z) implies m(x) = m(y) and m(y) = m(x), but m(x) ≠ m(z)

So R has to be an equivalence relation. Moreover:

if R(x₀,y₀), R(x₁,y₁)…R(x_n,y_n)

and

¬R(f(x₀,x₁…x_n),f(y₀,y₁,…y_n)), then

m(f(x₀,x₁…x_n)) ≠ m(f(y₀,y₁…y_n))

which contradicts the fact that the homomorphism m preserves operations, since

m(x₀) = m(y₀), …, m(x_n) = m(y_n)

implies that

f(m(x₁),…,m(x_n)) = f(m(y₁),…,m(y_n)) = m(f(x₁,x₂,…,x_n)) = m(f(y₁,y₂,…,y_n))

So R must also "preserve operations".

This gives us the definition of a congruence: an equivalence relation on the elements of an algebra that preserves operations. Given a congruence R on an algebra (X,R), we form the quotient algebra (X,F)/R where the set of elements is the set of equivalence classes of R, and the operations are the operations of F applied to equivalence classes. The equivalence class [b]_R is the set of all elements x ∈ X such that R(b,x). The operations of F are well-defined on equivalence classes of R because R preserves operations: if R(x₀,y₀)…R(x_n,y_n) and f(x₀…x_n) = x, f(y₀…y_n) = y, then R(x,y), so:

f([x₀]_R…[x_n]_R) = f([y₀]_R…[y_n]_R) = [x]_R = [y]_R.

The fact that you can only form a quotient algebra over a congruence relation may remind you of the fact that you can only form a quotient group over a normal subgroup. In fact, congruences on groups are isomorphic to normal subgroups: for any group (X,*,i,⁻¹) and congruence R, the set of all a in X such that R(a,1) forms a normal subgroup of (X,*,i,⁻¹).

To see this, recall that a normal subgroup N ⊆ X is defined by the fact that for all b ∈ X, bNb⁻¹ = {b * n * b⁻¹|n ∈ N} = N. Let H = {a|R(a,1)}. For any b ∈ X, reflexivity of R implies that R(b,b) and R(b⁻¹,b⁻¹). The fact that R preserves operations implies that for any a such that R(a,1), R(bab⁻¹,b1b⁻¹) = R(bab⁻¹,1), which in turn implies that bHb⁻¹ = H, satisfying the definition of a normal group.

Conversely, if N is a normal subgroup of (X,*,i,⁻¹), then the relation R where R(a,b) if and only if a * b⁻¹ in N is a congruence relation. Reflexivity holds because all normal subgroups must contain b * b⁻¹ = 1. Symmetry holds because normal subgroups must be closed under inverse, and (a*b⁻¹)⁻¹ = b * a⁻¹). Transitivity holds because all subgroups must be closed under *, and (a*b⁻¹) * (b*c⁻¹) = a * c⁻1. Preservation of operation holds because normal subgroups contain the identity, are closed under inverse, and are closed under multiplication.

Congruences on lattices lack an analogue as exciting as normal subgroups. R is a lattice congruence on (X,∧,lor) if and only if for all a, b, c, d ∈ X, R(a,b) and R(c,d) imply that R(a∧c,b∧d) and R(a∨c,b∨d), which is just a straightforward application of the definition of a congruence.

References

Burris, S., & Sankappanavar, H. P. (2011). A Course in Universal Algebra (Graduate Texts in Mathematics, 78) http://www.math.uwaterloo.ca/ snburris/htdocs/ualg.html

Dummit, D. S., & Foote, R. M. (2003). Abstract Algebra, 3rd Edition (3rd ed).