Equivalence relations as proof tools

A relation on a set specifies which ordered pairs of its elements are related. Reflexivity says each element relates to itself. Symmetry permits reversal of a related pair. Transitivity permits chaining: if the first relates to the second and the second to the third, the first relates to the third. All three are necessary for the usual equivalence-class construction. The less-than-or-equal relation is reflexive and transitive but not symmetric, so it records order rather than interchangeability.

For integers a and b, congruence modulo a positive integer m means their difference is an integer multiple of m. Reflexivity uses multiplier zero. Symmetry changes the multiplier’s sign. Transitivity adds two integer multipliers. These short verifications depend on integer closure and the fixed modulus, not on drawing numbers in a circle. Once established, the relation can be used as a controlled way of replacing an integer by another representative.

The equivalence class of a is the set of elements related to a. Reflexivity puts a in its own class, so every element belongs to at least one class. If two classes share an element, symmetry and transitivity show that every member of either belongs to the other. Thus the classes are equal. This proves that distinct classes are disjoint, a stronger and more useful conclusion than simply displaying several examples that seem not to overlap.

Keep distinct the element a, its class, and the set of all classes. An integer is not a collection of integers, even if a familiar notation uses the same symbol for its residue class. Choosing a representative from each class can simplify a calculation, but that choice should not become an unstated extra condition on the original objects. For congruence modulo three, representatives zero, one, and two are convenient names; negative integers still belong to the same three classes.

To define addition of residue classes by adding representatives, show that replacing either representative by an equivalent integer gives an equivalent sum. If a differs from a′ by a multiple of m and b differs from b′ by another, their sums also differ by a multiple of m. This is representative independence, often called well-definedness. Without it, the same two input classes could be assigned two different outputs depending on how you happened to write them.

Not every familiar operation descends automatically. Integer division, for example, cannot be applied blindly to residue classes, because division by a class may not have a unique solution or any solution. Even a numerical function must be checked: sending the class of an integer to that integer’s ordinary square as a real number depends on the representative. Sending it to the class of its square is a different proposal and does pass the relevant congruence check.