Knowlpedia

Equivalence relation

A relation that formalizes when two elements should be regarded as the same type.

An equivalence relation on a set AA is a ∼ ⊆A×A\sim\,\subseteq A\times A satisfying the following three properties for all a,b,c∈Aa,b,c\in A:

  • Reflexive: a∼aa\sim a.
  • Symmetric: if a∼ba\sim b, then b∼ab\sim a.
  • Transitive: if a∼ba\sim b and b∼cb\sim c, then a∼ca\sim c.
Remarks

Equivalence relations partition AA into , and the set of all classes forms a .

Examples
  • On Z\mathbb{Z}, define a∼ba\sim b iff a−ba-b is divisible by a fixed n∈Nn\in\mathbb{N} (congruence modulo nn).
  • On any set AA, the equality relation a∼b  ⟺  a=ba\sim b \iff a=b is an equivalence relation.