Equivalence relation

Let $A$ be a set and let $\sim$ be a relation on $A$ (so $\sim \subseteq A\times A$, the Cartesian product ). Then $\sim$ is an equivalence relation if it satisfies:

• (Reflexive) $\forall a\in A,\; a\sim a$.
• (Symmetric) $\forall a,b\in A,\; a\sim b \Rightarrow b\sim a$.
• (Transitive) $\forall a,b,c\in A,\; (a\sim b \text{ and } b\sim c)\Rightarrow a\sim c$.

Equivalence relations are exactly the relations that partition $A$ into equivalence classes ; the set of classes is the quotient set .

Examples:

• Equality $=$ on any set $A$ is an equivalence relation.
• On $\mathbb{Z}$, define $a\sim b$ iff $a-b$ is divisible by $n$ (congruence modulo $n$).
• On $\mathbb{R}$, define $x\sim y$ iff $x-y\in\mathbb{Z}$.