Equivalence Relations

Discrete Math · Axiom Academy

Understanding how equivalence relations partition sets into disjoint equivalence classes, with applications to modular arithmetic and geometric congruence. A relation R on a set A is an equivalence relation if it satisfies three essential properties: 2. Equivalence Classes and Partitions An equivalence relation divides a set into equivalence classes . The equivalence class of an element a , denoted [ a ], contains all elements equivalent to a . Every element belongs to exactly one equivalence class Two equivalence classes are either identical or disjoint The union of all equivalence classes equals the original set This creates a partition of the set 3. Example: Modular Arithmetic Congruence modulo n is a classic equivalence relation. We say a ≡ b (mod n ) if n divides ( a - b ). Consider integers modulo 3. This relation partitions the integers into three equivalence classes: [0] = ..., -6, -3, 0, 3, 6, 9, ... (multiples of 3) [1] = ..., -5, -2, 1, 4, 7, 10, ... (one more than multiples of 3) [2] = ..., -4, -1, 2, 5, 8, 11, ... (two more than multiples of 3) Verification: This satisfies all three properties: Reflexive: a - a = 0, and n divides 0 Symmetric: If n divides ( a - b ), then n divides ( b - a ) Transitive: If n divides ( a - b ) and ( b - c ), then n divides ( a - c ) 4. Example: Geometric Congruence

This is the written version of the interactive lesson above. See the full Discrete Math course.