Definition.
(Page 49)
A relation $\sim$ on a nonempty set $S$
is an
equivalence relation
on $S$ if it satisfies the following
three properties:
-
Reflexive.
If $a\in S$ then $a\sim a.$
-
Symmetric.
If $a,b\in S$ and $a\sim b$
then $b\sim a.$
-
Transitive.
If $a,b,c\in S$ and $a\sim b$
and $b\sim c,$
then $a\sim c.$
Example 9.1.
Let $p$ denote a fixed point in a plane $P,$
and for points $x$ and $y$ in $P$ let
$x\sim y$ mean that $x$ and $y$ are equidistant
from $p.$ This is an equivalence relation on the
set of points in $P.$ A point $x$ will be
equivalent to a point $q$ iff $x$ lies on the circle
through $q$ with center $p.$ (The point $p$ is
equivalent only to itself; think of $\{p\}$ as a
circle with radius $0$.)
Example 9.2.
Let $L$ denote the set of all lines in a plane with
rectangular coordinate system. For $l_1,l_2\in L,$
let $l_1\sim l_2$ mean that $l_1$ and $l_2$ have equal
slopes or that both slopes are undefined.
This is an equivalence relation on $L.$ The set of
lines equivalent to a line $l$ consists of $l$ and
all lines in $L$ that are parallel to $l.$
Example 9.3.
Let $\alpha:S\rightarrow T$ be a mapping.
For $x,y\in S,$ let $x\sim y$ mean that
$\alpha(x)=\alpha(y).$ This is an equivalence
relation on $S.$ Here are two special cases.
-
Let
$S=\{u,v,w\},$ $T=\{1,2,3\},$
and define
$\alpha:S\rightarrow T$
by
$$
\alpha(u)=3,\quad
\alpha(v)=1,\quad
\alpha(w)=3.
$$
Then $u\sim w$ because
$\alpha(u)=\alpha(w)$
But $u\not\sim v$ because
$\alpha(u)\ne\alpha(v).$
Here is a complete list of the equivalences between
elements of $S:$
$$
u\sim u,\quad
v\sim v,\quad
w\sim w,\quad
u\sim w,\quad
w\sim u
$$
-
Let $S=T=\R$ and let $\alpha$ be the sine function.
Then $x_1\sim x_2$ iff $sin x_1=sin x_2.$
Thus, for example, the set of real numbers equivalent
to $pi$ in this case is
$$
\{ x \mid \sin x = 0 \} = \{0, \pm\pi, \pm 2\pi, \ldots \}
$$
Note.
(Page 50)
A different way to define the equivalence relation in
example Example N 9.1 is to say that $x\sim y$ iff
$x$ and $y$ lie on a common circle with center $p.$
These circles form a partition of the set of points in
the plane, in the sense of the following definition.
Definition.
(Page 50)
A collection $\mathcal{P}$ of nonempty subsets
of a nonempty set $S$ forms a
partition
of $S$ provided
-
$S$ is the union of the sets in $\mathcal{P},$ and
-
if $A$ and $B$ are in $\mathcal{P}$ and $A\ne B,$
then $A\cap B=\varnothing.$
Alternatively, the collection $\mathcal{P}$
forms a partition of $S$ if each element of $S$
is contained in one and only one of the sets
in $\mathcal{P}.$
Notice that each element of $\mathcal{P}$
is a subset of $S.$
Definition.
(Page 51)
Let $\sim$ be an equivalence relation on a set $S,$
let $a\in S,$
and let $[a]=\{x\in S \mid a\sim x\}.$
This subset $[a]$ of $S$ is called the
equivalence class of $a$ (relative to $\sim.$)
Theorem 9.1.
If $\sim$ is an equivalence relation on a set $S,$
then the set of equivalence classes of $\sim$ forms a
partition of $S.$
Converseley, let $\mathcal{P}$ be a partition of $S,$
and define a relation $\sim$ on $S$ by $a\sim b$
iff there is a set in $\mathcal{P}$ that contains both
$a$ and $b;$ then $\sim$ is an equivalence relation
on $S.$ Thus there is a natural one-to-one correspondence
between the equivalence relations on a set and the partitions
of the set.
Example 9.4.
Let $E$ denote the set of even integers and $O$ the set of
odd integers. Then $\{E,O\}$ forms a partition of the set
of all integers. For the corresponding equivalence relation,
$a\sim b$ iff $a$ and $b$ are both even or both odd.
Alternatively, $a\sim b$ iff $a-b$ is even.
Definition.
(Page 52)
In working with an equivalence relation on a set $S,$
it is often useful to have
a complete set of equivalence class representatives
—that is, a subset of $S$ containing precisely
one element from each equivalence class.
Example 9.5.
-
In Example N 9.4, $\{0,1\}$ is a complete set
of equivalence class representatives. Each
integer is equivalent to either $0$ or $1,$
but no integer is equivalent to both. More
generally, any set $\{a,b\}$ of integers
with $a$ even and $b$ odd is a complete set of
equivalence class representatives in this case.
-
In Example N 9.3, $\{u,v\}$ is a complete set of
equivalence class representatives. Another
complete set of equivalence class representatives
in this case is $\{v,w\}.$
-
In Example N 9.1, the set of all points on
any ray (half-line) with endpoint $p$ is a
complete set of equivalence class representatives,
because such a ray intersects each equivalence
class (circle centered at $p$) in precisely one
point.
Theorem 9.2.
Let $G$ be a permutation group on $S$
and define a relation $\sim$ on $S$
by
\[
a\sim b \quad\text{ iff }\quad
\alpha(a)=b \quad
\text{ for some } \alpha\in G
\]
Then $\sim$ is an equivalence relation on $S.$
Example 9.6.
Consider Theorem 9.2 for $S=\{1,2,3,4,5\}$
and $G$ the group $\{(1),(1\,2\,5),(1\,5\,2)\}.$
In this case, the equivalence classes are
$$
\{1,2,5\},\quad \{3\},\quad \{4\}.
$$
A complete set of equivalence class representatives is
$\{1,3,4\}.$
Alex Notes