The Gold Standard of Universal Algebra | Tracking Which Congruences Survive After Taking a Quotient

Take the additive cyclic group C24. Its elements are the residues 0 through 23, addition is modulo 24, and its signature includes addition, additive inverse and zero. Define θ by saying that a and b are related when they have the same remainder modulo 8.

There are eight θ-classes. The class represented by 0 is {0,8,16}; the class represented by 1 is {1,9,17}; and the pattern continues to the class {7,15,23}. Each class has three original elements. The quotient has eight elements, each of which is an entire class.

The quotient map sends a to its remainder modulo 8. It preserves addition because reducing a sum modulo 8 gives the same result whether you first reduce its summands or not. Reducing modulo 24 before reducing modulo 8 does not change this conclusion, because 8 divides 24. The map also preserves zero and additive inverse.

These details matter. A list of groups of elements is only a partition until it satisfies the compatibility requirements of the declared operations. Here those requirements follow from ordinary divisibility: if a−a′ and b−b′ are multiples of 8, then their sum is a multiple of 8, and so is the negative of either difference.

Our first quotient is therefore isomorphic to C8. You may use the shorter residue labels for calculations, provided you remember what they stand for. The label 0 in C8 represents three elements of C24. It does not mean that the other two elements were literally deleted.

Contents · Next chapter

Now work inside C8 and identify residues that agree modulo 4. Its new classes are {0,4}, {1,5}, {2,6} and {3,7}. This is another compatible identification. Adding corresponding representatives preserves their differences modulo 4.

What does the class {0,4} mean when translated back to C24? The label 0 represented {0,8,16}; the label 4 represented {4,12,20}. Their union is {0,4,8,12,16,20}. This is exactly the class of all original residues congruent to 0 modulo 4.

The other three classes have the same form, shifted by 1, 2 and 3. The two-stage quotient is isomorphic to C4. The direct route sends each original element straight to its remainder modulo 4.

Check an actual sum. Start with 17 and 22 in C24. Their sum is 15 modulo 24. Reducing that result modulo 4 gives 3. Through the two-stage route, 17 and 22 first become 1 and 6 in C8; their sum is 7, and 7 becomes 3 modulo 4. Both routes give the same answer.

This check is useful evidence about the example, but it is not the general proof. The general proof comes from the definitions of the maps and the divisibility relations between 24, 8 and 4. The calculation helps you see which object each number belongs to while you develop that proof.

Contents · Previous chapter · Next chapter

Let q be the quotient map from A to A/θ. Suppose ψ is a congruence on A/θ. Define a relation φ on the original elements by:

a φ b precisely when q(a) ψ q(b).

This is the inverse image of ψ along the map that sends a pair (a,b) to (q(a),q(b)). It says that two original elements count as equivalent when their already-formed quotient classes become equivalent at the second stage.

Every pair in θ lies in φ. If a θ b, then q(a)=q(b). Since ψ is reflexive, that one quotient element is ψ-related to itself. Therefore a φ b.

This is the source of the containment condition θ ⊆ φ. A second quotient cannot distinguish two original elements whose first quotient images are already equal. No choice of second-stage representatives can restore that distinction.

The relation φ is an equivalence relation because ψ is one. Reflexivity, symmetry and transitivity each transfer through q. It also respects every basic operation. Apply an operation to φ-related input pairs, use preservation by q, and then apply compatibility of ψ in the quotient. The resulting outputs are φ-related.

Notice the direction of the argument. We started with a genuine congruence on the quotient and obtained a genuine congruence on the original algebra. This direction always produces a relation containing θ. It does not ask us to guess which original partitions might work.

Contents · Previous chapter · Next chapter

For the reverse direction, suppose φ is a congruence on A and θ ⊆ φ. Define a relation on the θ-classes by:

[a]θ is related to [b]θ precisely when a φ b.

At first this looks like an instruction involving representatives. We must show that it gives the same answer if different representatives are chosen.

Suppose a′ θ a and b θ b′. Containment gives a′ φ a and b φ b′. If a φ b, transitivity gives a′ φ b′. Reversing this reasoning shows that the answer is unchanged in both directions.

Without that argument, the proposed relation would not yet be a relation on quotient elements. A quotient element can have many names. A definition on the quotient must not change its answer when the name changes.

Call the resulting relation φ/θ. Its equivalence properties follow from those of φ. For compatibility, choose representatives of the input classes, use compatibility of φ in A, and then take the θ-class of the output. The quotient operations were defined in exactly this representative-independent way.

The formula therefore constructs a congruence on A/θ. Both ingredients are necessary: φ must already be compatible with the operations, and it must contain the identifications θ has already imposed.

Contents · Previous chapter · Next chapter

Return to C24 and θ given by congruence modulo 8. Consider β given by congruence modulo 6. Both θ and β are valid group congruences on C24.

However, θ is not contained in β. The pair (0,8) lies in θ, because both numbers have remainder 0 modulo 8. It does not lie in β, because 8 is not a multiple of 6.

Try to use the representative formula anyway. The quotient element [0]θ can be represented by 0 or by 8. If you compare this element with itself using representatives 0 and 0, the condition 0 β 0 is true. If you compare the very same quotient element with itself using representatives 8 and 0, the condition 8 β 0 is false.

The formula has assigned two answers to the same proposed input pair. That is more serious than a failed algebraic law: it has not defined a relation on the quotient at all.

This example separates two checks that are easily confused. β is a perfectly good congruence upstairs. The failure occurs because it is incompatible with the information already forgotten downstairs. Validity on the original algebra does not automatically permit descent through an arbitrary quotient.

You could instead ask for the least congruence containing both θ and β, then descend that larger relation. That is a different construction. It adds identifications until the containment condition becomes true, so it must be explained as a repair that changes the proposed relation.

Contents · Previous chapter · Next chapter

Start with ψ on A/θ, pull it back to φ on A, and then descend φ again. Two quotient classes [a]θ and [b]θ are related by φ/θ exactly when a φ b. By the definition of the pullback, this means q(a) ψ q(b). Since q(a)=[a]θ and q(b)=[b]θ, we have recovered ψ.

Start instead with φ containing θ. Descend it to φ/θ and pull that relation back along q. The resulting relation holds between a and b exactly when [a]θ and [b]θ are related by φ/θ. That is exactly the original condition a φ b. We have recovered φ.

These are two different checks. Showing that each direction produces a legitimate congruence establishes that the constructions make sense. Showing that their composites return the starting relations establishes that nothing has been lost or duplicated in the correspondence.

There is no need to count congruences to prove the correspondence. In a finite example, counting gives a useful audit. In a general algebra, the same inverse-construction argument works even when the congruence sets are infinite.

The correspondence concerns all congruences containing θ, not all congruences of A. The failed modulo-six example sits outside the permitted interval. Leaving it out is part of the theorem, not an exception to it.

Contents · Previous chapter · Next chapter

For an additive cyclic group Cn, a subgroup is determined by a divisor of n. The corresponding congruence can be written as agreement modulo d, where d divides n. The quotient has d elements.

In C24, the possible divisors are 1, 2, 3, 4, 6, 8, 12 and 24. Which of their congruences contain agreement modulo 8? Precisely those with d dividing 8: d=1,2,4,8.

The answer is a four-element chain. Agreement modulo 8 makes the fewest identifications among these four relations. Agreement modulo 4 makes more; agreement modulo 2 makes still more; agreement modulo 1 identifies every element.

Downstairs, C8 has exactly the same four possibilities. Its equality relation corresponds to θ itself upstairs. Its universal relation corresponds to the universal relation upstairs. The two intermediate relations correspond to agreement modulo 4 and modulo 2.

This is a useful place to check the direction of inclusion. A smaller modulus gives a coarser partition and therefore a larger relation when relations are viewed as sets of pairs. There are fewer classes but more related pairs.

The theorem preserves the inclusion order of relations. It does not preserve the numerical value of a modulus as an increasing measure of coarseness. Mixing those two orders can reverse a correct diagram.

Contents · Previous chapter · Next chapter

Replace C24 with C30 and replace agreement modulo 8 with agreement modulo 10. The first quotient is C10. Which congruences upstairs contain the first one?

The relevant moduli are the divisors of 10: 1,2,5,10. Unlike the earlier example, the intermediate congruences modulo 2 and modulo 5 are incomparable.

To verify incomparability, use explicit pairs. The pair (0,2) is related modulo 2 but not modulo 5. The pair (0,5) is related modulo 5 but not modulo 2. Neither relation contains the other.

The correspondence still works. It gives a diamond-shaped four-element order rather than a chain. The theorem promises an isomorphism between the appropriate congruence orders; it does not promise that those orders are linear.

Now take the second quotient by agreement modulo 5 in C10. Pulling it back gives agreement modulo 5 in C30. Each final class has six original elements, while each first-stage class had three. The second-stage quotient combines two first-stage classes into each final class.

For a self-check, trace the original element 27. Its first image is 7 in C10; its second image is 2 in C5. Direct reduction of 27 modulo 5 is also 2. Then repeat the check with a sum, stating the group in which each addition takes place.

Contents · Previous chapter · Next chapter

The correspondence does more than pair up two lists. Suppose φ and χ both contain θ. If φ is contained in χ, every pair related by φ is related by χ. Applying the definitions to representatives shows that φ/θ is contained in χ/θ. Conversely, if the downstairs relations are contained in that order, testing the classes of any original pair gives φ ⊆ χ.

Thus inclusion is both preserved and reflected. This matters because a lattice operation is characterised by its position in an order. A meet is the greatest relation below both inputs. A join is the least congruence above both inputs. An order isomorphism carries those characterisations across.

For meets, the formula is particularly direct. A pair of quotient classes lies in both φ/θ and χ/θ exactly when its representatives lie in both φ and χ. Therefore the downstairs intersection is (φ ∩ χ)/θ. The intersection upstairs still contains θ, so it is an allowed input to the correspondence.

For joins, do not simply replace the word “intersection” with “union”. The union of two congruences need not be transitive. The join is the least congruence containing their union. Because the correspondence preserves and reflects upper bounds, the least upper bound upstairs corresponds to the least upper bound downstairs.

You can prove that last statement without assuming a special formula for joins. An upper bound downstairs pulls back to an upper bound upstairs; minimality upstairs puts the upstairs join below that pullback; descending again puts its image below the original downstairs upper bound. This is the required leastness.

The argument works for arbitrary families too, with the usual complete-lattice conventions. For this lesson, the two-input case is enough to show why the theorem is stronger than a coincidence between finite counts.

Contents · Previous chapter · Next chapter

Use C30 with θ given by agreement modulo 10. Let φ be agreement modulo 2 and χ agreement modulo 5. Both contain θ. Their intersection requires a difference divisible by both 2 and 5. That means a difference divisible by 10, so their meet is θ.

Their join identifies everything. To see why, φ relates 0 to 2, while χ relates 2 to 7. Therefore the join relates 0 to 7. In this group, closure under addition and inverse then relates 0 to every multiple of 7. Since 7 generates C30, every residue is connected to 0.

There is an even shorter witness using differences. The subgroup generated by 2 and 5 contains 5−2−2=1. A subgroup containing 1 is the whole cyclic group. Consequently the smallest group congruence containing both relations is universal.

Downstairs, C10 has the same pattern. Agreement modulo 2 and agreement modulo 5 meet in equality and join in the universal relation. Equality downstairs corresponds to θ upstairs, rather than to equality upstairs.

This last sentence catches a common diagram error. When you pass to a quotient, the bottom of the new congruence lattice represents all identifications already made. It is new equality, not a claim that the original algebra had no identifications.

Try a different pair in C24. Agreement modulo 4 is contained in agreement modulo 2. Their meet is the finer relation modulo 4, and their join is the coarser relation modulo 2. When two relations are comparable, no additional closure calculation is required.

Contents · Previous chapter · Next chapter

Suppose θ ⊆ φ. We have the first quotient A/θ and its congruence φ/θ. The second quotient has elements that are classes of θ-classes. Define a map to A/φ by sending the second-stage class containing [a]θ to [a]φ.

The expression contains three levels, so read it slowly. The symbol a denotes an original element. The symbol [a]θ denotes its first-stage class. The second-stage class groups together first-stage classes that are related by φ/θ.

Why is the proposed map well defined? If two first-stage classes belong to the same second-stage class, their representatives are φ-related by definition. They therefore determine the same φ-class. The answer cannot change with the representative of the second-stage class.

The map is onto because every φ-class has an original representative a. It is one-to-one because equal φ-classes mean that their representatives are φ-related, which means that their θ-classes were already identified at the second stage.

It preserves every operation because each operation in each quotient is computed by applying the original operation to representatives and then taking the relevant class. Both routes therefore send the same tuple to the φ-class of the same original output.

A bijective homomorphism of algebras in the same signature is an isomorphism: its inverse preserves operations by choosing the unique preimages of the inputs and using preservation of the forward map. Thus the two-stage and one-stage quotients have the same algebraic structure.

They need not be literally the same sets. One consists of classes of classes; the other consists of classes of original elements. The explicit isomorphism explains the relationship without pretending that these differently constructed sets are identical.

Contents · Previous chapter · Next chapter

The same containment condition controls whether an existing homomorphism can use the quotient as its input. Let f:A→B be a homomorphism. We want a map from A/θ to B that sends [a]θ to f(a).

This prescription works exactly when θ is contained in the kernel of f. If a θ b, the quotient treats their classes as equal; therefore a well-defined prescription must give f(a)=f(b). Conversely, if every θ-pair has equal f-values, the prescription is independent of the representative.

The induced map preserves operations because f does. Its composite with the quotient map is f. It is unique with this property because every quotient class has a representative. A competing induced map would have to agree on the image of every original element, and those images cover A/θ.

In our C24 example, reduction modulo 4 factors through reduction modulo 8. Elements with the same remainder modulo 8 necessarily have the same remainder modulo 4. Reduction modulo 6 does not factor through reduction modulo 8: 0 and 8 have the same first image but different remainders modulo 6.

This is not a problem caused by the chosen labels 0 through 7. Any relabelling of the eight quotient classes still leaves 0 and 8 in one class. The obstruction lies in the kernel relation, so changing notation cannot repair it.

A practical way to diagnose a failed factorisation is therefore to search for one pair that the first map identifies and the proposed later output distinguishes. Such a pair gives a complete disproof. To prove a factorisation, however, you need the containment for every pair.

Contents · Previous chapter · Next chapter

There is a tempting alternative when θ is not contained in β. Instead of demanding that any representatives give the same answer, one could declare two quotient classes related whenever some representatives are β-related.

That is an existential image of a relation. It is a genuine set of pairs of quotient classes, because existence does not depend on which representatives happen to be written down. But it is not the representative-independent descent used in the correspondence theorem.

In the C24 example, let β be agreement modulo 6 and θ agreement modulo 8. The existential image relates quotient residues exactly when their difference is even. A difference between suitable original representatives is divisible by 6 precisely when the difference of the quotient labels can be adjusted by a multiple of 8 to become divisible by 6.

The common divisor of 6 and 8 is 2. It supplies the obstruction: an odd difference cannot become divisible by 6 after adding a multiple of 8. An even difference can. In this example the existential image is therefore a congruence on C8, namely agreement modulo 2.

Pull it back and you obtain agreement modulo 2 on C24. You have not recovered β. You have enlarged it to include θ as well. For example, 0 and 2 are now related even though they were not related modulo 6.

This example explains why a construction that happens to produce a useful relation does not automatically establish the stated correspondence. The inverse test is essential. If descending and pulling back changes your starting relation, you are doing something other than the inverse pairing on the permitted interval.

Do not infer from this group example that every existential image of a congruence under every surjective homomorphism is a congruence. The next example shows precisely what can fail.

Contents · Previous chapter · Next chapter

Take a set A={a,b,c,d} with one unary operation, the identity operation. Every equivalence relation on A is a congruence, because applying the identity operation changes no input or output.

Let θ have classes X={a}, Y={b,c} and Z={d}. Let β have classes {a,b} and {c,d}. The quotient A/θ has three elements X,Y,Z, and its unary operation is again the identity.

The existential image of β relates X to Y, witnessed by a β b. It also relates Y to Z, witnessed by c β d. But it does not relate X to Z: the only possible representatives of those two singleton classes are a and d, which lie in different β-classes.

Thus the image is not transitive. It is reflexive and symmetric, but those properties alone do not make it an equivalence relation. Consequently it is not a congruence on the quotient.

The failure comes from the middle class Y. The first link uses its representative b and the second link uses c. Those representatives have been identified by θ, but β does not identify them. You cannot splice the two β-witnesses into one β-chain without adding an identification that β did not contain.

If you first replace β by the join θ∨β, all four original elements become connected: a to b through β, b to c through θ, and c to d through β. The repaired relation descends to the universal relation on the three-element quotient.

This is an original small diagnostic example, not a claim that group congruences behave the same way. It illustrates why a theorem about arbitrary algebras must state its assumptions rather than rely on behaviour observed in a convenient group family.

Contents · Previous chapter · Next chapter

A useful finite audit begins with the signature and the operation tables. Without them, checking that a proposed partition is an equivalence relation says nothing about compatibility. Record every basic operation, including constants where present.

Next verify θ and the proposed upstairs congruence φ. Test equivalence properties and operation preservation. Then test containment. A failure at this stage should return an explicit pair a θ b with a not φ b; that pair explains why representative-independent descent fails.

When containment passes, list the θ-classes and compute the descended relation using representatives. Repeat the computation with alternative representatives for at least a few illustrative cases, while keeping the general containment proof as the reason all choices agree.

Pull the result back and compare it with the original φ pair by pair. This inverse check catches indexing errors, accidental reversal of containment and mistaken treatment of quotient labels as original elements. For a finite carrier, it is straightforward to automate.

Finally verify the two-stage map against the direct quotient. Check that it is well defined, onto, one-to-one and operation-preserving. A matching number of classes proves none of these properties on its own. Two finite algebras can have the same number of elements and different operation tables.

Computer checks establish the specific finite instances you encoded. They do not replace the proof for arbitrary algebras. Use the calculations to expose mistakes and make the construction tangible, then identify the general argument that explains why the checks succeed.

Contents · Previous chapter · Next chapter

Try C36 with θ given by agreement modulo 12. Before calculating any second-stage quotient, name the first quotient and count its elements. It is C12, with twelve classes of three original elements each.

Which congruences of C36 contain θ? Their moduli are exactly the divisors of 12: 1,2,3,4,6,12. There are six of them. The divisor 9 of 36 does not belong on this list because agreement modulo 12 does not imply agreement modulo 9.

Produce the failure pair yourself: 0 and 12 are θ-related, but not related modulo 9. This one pair rules out descending agreement modulo 9 by the representative formula.

Now combine agreement modulo 4 and agreement modulo 6. Their intersection is agreement modulo 12, since a difference must be divisible by both 4 and 6. Their join is agreement modulo 2, because the subgroup generated by differences 4 and 6 contains 2 and consists entirely of even residues.

Downstairs in C12, those operations give equality as the meet and agreement modulo 2 as the join. Translate both answers upstairs and verify that you obtain the same relations. This exercise tests the correspondence, the direction of containment and the distinction between a join and a union.

For an extra check, identify C12 further modulo 3. Trace the original elements 17 and 29 through both routes from C36 to C3. They have the same first image, 5, and the same final image, 2. Explain why no later map from C12 can send those original elements to different answers.

Contents · Previous chapter · Next chapter

Does every congruence on A give a congruence on A/θ? Not by the representative-independent formula. It must contain θ. Otherwise the same quotient classes may receive different answers when their representatives change.

Does “contain θ” mean that every θ-class contains a φ-class? The useful formulation is the reverse: every θ-class lies inside one φ-class. The later relation groups first-stage classes together. As sets of pairs, θ is contained in φ.

Is the bottom relation upstairs always equality? The bottom of the whole lattice Con(A) is equality. The bottom of the interval used by this correspondence is θ. Downstairs, that interval bottom becomes equality on A/θ.

Why not count classes and stop? Because class counts do not verify operations, representative independence or the inverse correspondence. The count is a check on a construction whose mathematical validity has already been established.

Can a second quotient recover information lost in the first? No. Its composite map is constant on each first-stage class. You would need additional information outside that quotient to distinguish original elements again.

Does the correspondence require the algebra to be finite? No. The proofs using representatives, inverse images and order work for general algebras. Finiteness lets us display complete examples and exhaustively check pairs; it is not a hypothesis of the theorem.

Does a successful existential image settle descent? No. It is a different construction. It may enlarge the original relation after pullback, and in a general algebra it may fail transitivity altogether.

Contents · Previous chapter · Next chapter

When you face an iterated quotient, start by naming the first relation θ. Then state what further distinctions you want to remove. Translate that second task into a relation on A/θ, or into a congruence φ on A that contains θ.

Choose the direction that makes the evidence easiest to check. If the second-stage classes are already given, pull them back. If the original algebra has familiar congruences, select those above θ and descend them. The two routes are inverse descriptions of the same possibilities.

Keep three claims separate in your written solution. First, the proposed relations are congruences. Second, the containment condition permits descent. Third, the two-stage quotient is isomorphic to the direct quotient. Each claim has its own proof and its own possible failure.

For a compact answer, show the containment witness or containment proof, state the induced relation and give the explicit class-of-classes map. For a learning exercise, also include one rejected relation and explain the precise pair that defeats it. The rejection often reveals the theorem's purpose more clearly than another successful calculation.

The practical transfer is a habit of tracking irreversible identifications. Once a construction declares two inputs equal, every well-defined later operation on its output must respect that equality. The correspondence theorem identifies all compatible further quotient choices and tells you how to move between their two descriptions.

Contents · Previous chapter · Continue to related reading