Skip to content
Axiomatic Wiki

WLCongruence modulo n is an equivalence relation

Lemma·L73

Congruence mod n is an equivalence relation whose classes are the cosets of nZZ.

Fix . Then (D113) is an equivalence relation on , and for every its class is the coset .
In words
Congruence modulo n is an equivalence relation on the integers, and for every integer a, its class is the coset a plus nZZ: the multiples of n shifted by a.
Rests onF02F03F04F05F06F08F09F11F12F13F14A01A02A06A08
Never needed: F10 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).

Proof

  1. 1
    By L72, is a subgroup of and for all .
  2. 2
    Let be the coset relation of in . Since the operation is and the inverse of is (T22, D059), the defining condition reads .
  3. 3
    is congruence modulo . The elements and are additive inverses of each other: their sum rearranges to by the abelian group laws (T22), so since inverses are unique (L28). As a subgroup, is closed under negation (D039), so . With step 1, .
  4. 4
    By L29 (i), , that is congruence modulo , is an equivalence relation on . By L29 (ii), the class of is the coset of , which written additively is .
∎

Remarks

Unwinding the subgroup axioms of recovers the three properties directly: reflexive because ; symmetric because forces ; transitive because give . The classes are the residue classes modulo ; for there are exactly of them (T60), the sets . This is the additive instance of the general fact that a subgroup partitions its group into cosets.
Wikipedia ↗Int.ModEq.equivalence ↗

Used by

L78T60T62
Propose an edit1 published revision