Equivalence Relations

What Is an Equivalence Relation?

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations partition a set into groups where elements in the same group are considered "equivalent."

Properties:
  Reflexive:     aRa for all a
  Symmetric:     aRb → bRa
  Transitive:    aRb and bRc → aRc

Examples

Equality (=) on numbers:
  Reflexive: a = a ✓
  Symmetric: a = b → b = a ✓
  Transitive: a = b and b = c → a = c ✓

Congruence modulo n (a ≡ b mod n):
  Reflexive: a ≡ a mod n ✓
  Symmetric: a ≡ b mod n → b ≡ a mod n ✓
  Transitive: a ≡ b mod n and b ≡ c mod n → a ≡ c mod n ✓

Same birthday relation:
  Two people are related if they share the same birthday.

Equivalence Classes

An equivalence class [a] is the set of all elements equivalent to a:

[a] = {x ∈ A | xRa}

Example: Congruence mod 3 on {0, 1, 2, 3, 4, 5}
  [0] = {0, 3}
  [1] = {1, 4}
  [2] = {2, 5}

The equivalence classes form a partition of the set.