Equivalence Relations

A relation that is reflexive, symmetric and transitive is called an equivalence relation. It captures the idea of "being alike in some respect": having the same remainder on division by 5, being parallel, being similar triangles, having the same birthday month.

Equivalence classes

For an equivalence relation \(R\) on \(A\), the equivalence class of \(a\) is \([a]=\{x\in A : x\,R\,a\}\). Two facts make classes useful:

• Every element lies in its own class (reflexivity).
• Two classes are either identical or disjoint. So the classes partition \(A\) into non-overlapping pieces.

Example: on \(\mathbb{Z}\), \(a\,R\,b \iff 3 \mid (a-b)\). The classes are \([0]=\{\dots,-3,0,3,6,\dots\}\), \([1]=\{\dots,-2,1,4,\dots\}\) and \([2]=\{\dots,-1,2,5,\dots\}\) – exactly three classes, one for each remainder.

Proving a relation is an equivalence relation

1. Reflexive: show \(a\,R\,a\) for an arbitrary \(a\).
2. Symmetric: assume \(a\,R\,b\), deduce \(b\,R\,a\).
3. Transitive: assume \(a\,R\,b\) and \(b\,R\,c\), deduce \(a\,R\,c\).