Aside on equivalence relations

A relation on a set $S$ is a subset $R$ of $S\times S$ . By a slight abuse of notation, let us write, for any $s,t\in S$ , $sRt$ if and only if $(s,t)\in R$ . An equivalence relation is a relation satisfying (for equivalence relations, we write $s\sim t$ instead of $sRt$ )

• for all $s\in S$ , $s\sim s$ (reflexive),
• for all $s,t\in S$ , $s\sim t$ implies $t\sim s$ (symmetric),
• for all $s,t,u\in S$ , if $s\sim t$ and $t\sim u$ then $s\sim u$ (transitivity).

Example 1.7.1  

• The most common example of an equivalence relation is equality $=$ .

• Another example is from high school geometry: the similarity or congruence relation for triangles.

• If $m>1$ is a fixed modulus then $\equiv$ modulo $m$ is an equivalence relation. The verification of this is left as an exercise.

The equivalence class of $s\in S$ is

$$[s]=\{t\in S \vert t\sim s\}.$$

If $[s]$ is an equivalence class of $S$ then we call $s$ (or any other element of $[s]$ ) a representative of $[s]$ in $S$ .