title: "Equivalence Relation"

Equivalence Relation

Definition. An equivalence relation is a Relation that is reflexive, symmetric, and transitive. The equivalence class of $a$ is $[a] = \{x : a \mathrel{R} x\}$, and the distinct classes form a Partition of the underlying set.

The canonical example is congruence mod $m$ (Lecture 2, Example 10). Equivalence relations are how the course lumps objects that behave identically, such as strings a machine cannot tell apart in Unit 1.