Equivalence Relations

Math for CS · Axiom Academy

When "related" means "essentially the same" -- partitioning sets into classes A relation R on a set A is an equivalence relation if it satisfies three properties simultaneously: Reflexive: a a -- every element is related to itself Symmetric: If a b , then b a -- the relation goes both ways Transitive: If a b and b c , then a c -- the relation chains together Think of it this way: an equivalence relation is a formal way of saying "these things are the same in some respect." Equality itself is the simplest equivalence relation, but there are many others. The most important equivalence relation in CS is congruence modulo n . Two integers a and b are congruent modulo n if they have the same remainder when divided by n . Reflexive: a - a = 0 , and 3 0 . So a a . Symmetric: If 3 (a - b) , then 3 (-(a-b)) = (b-a) . So b a . Transitive: If 3 (a-b) and 3 (b-c) , then 3 ((a-b)+(b-c)) = (a-c) . So a c . Define a relation on the integers: a b if and only if a and b are both even or both odd. This is equivalent to a b . Reflexive: Every integer has the same parity as itself. Symmetric: If a has the same parity as b , then b has the same parity as a . Transitive: If a, b share parity and b, c share parity, then a, c share parity. This gives us exactly two equivalence classes: \ ..., -4, -2, 0, 2, 4, ...\ and \ ..., -3, -1, 1, 3, 5, ...\ . Given an equivalence relation on A , the equivalence class of an element a is the set of everything related to a : [0] = \ ..., -6, -3, 0, 3, 6, 9, ...\

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