Equivalence Relations

Set Theory · Axiom Academy

Relations that partition sets into meaningful classes 1. Definition of Equivalence Relation A relation R on a set A is an equivalence relation if it satisfies three properties: These three properties together capture the essence of "being equivalent to" in a mathematically precise way. The most fundamental equivalence relation is equality (=) on any set. Symmetric: If x = y, then y = x Transitive: If x = y and y = z, then x = z Equality satisfies all three properties, making it an equivalence relation. In fact, it's the finest possible equivalence relation, where each element is only equivalent to itself. For a positive integer n, define a a b (mod n) to mean n divides (b - a). - 1 a 4 a 7 a 10 (mod 3) because they all have remainder 1 when divided by 3 - 2 a 5 a 8 a 11 (mod 3) because they all have remainder 2 This is an equivalence relation: it's reflexive (a a a), symmetric (if a a b then b a a), and transitive (if a a b and b a c, then a a c). 4. Equivalence Relations Create Partitions Every equivalence relation on a set A partitions A into disjoint subsets called equivalence classes. Key Theorem: If R is an equivalence relation on A, then the equivalence classes of R partition A. Conversely, every partition of A defines an equivalence relation. This deep connection shows that equivalence relations and partitions are two ways of expressing the same idea.

This is the written version of the interactive lesson above. See the full Set Theory course.