Aside on equivalence relations

Aside on equivalence relations

A relation on a set is a subset of $S\times S$ . By a slight abuse of notation, let us write, for any $s,t\in S$ , 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 )

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 is a fixed modulus then $\equiv$ modulo is an equivalence relation. The verification of this is left as an exercise.

The equivalence class of $s\in S$ is

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

If

is an equivalence class of

then we call

(or any other element of

) a representative of

in

.

David Joyner 2007-09-03