We say $\sim$ is an **equivalence relation** on a set $A$ if it satisfies the following three
properties:

a) **reflexivity**: for all $a\in
A$, $a\sim a$.

b) **symmetry**: for all $a,b\in A$,
if $a\sim b$ then $b\sim a$.

c) **transitivity**: for all
$a,b,c\in A$, if $a\sim b$ and $b\sim c$ then $a\sim c$.

Example 5.1.1 Equality ($=$) is an equivalence relation. It is of course enormously important, but is not a very interesting example, since no two distinct objects are related by equality.

Example 5.1.2 Suppose $A$ is $\Z$ and $n$ is a fixed positive integer. Let $a\sim b$ mean that $a\equiv b \pmod n$. The fact that this is an equivalence relation follows from standard properties of congruence (see theorem 3.1.3).

Example 5.1.3 Let $A$ be the set of all words. If $a,b\in A$, define $a\sim b$ to mean that $a$ and $b$ have the same number of letters; $\sim$ is an equivalence relation.

Example 5.1.4 Let $A$ be the set of all vectors in $\R^2$. If $a,b\in A$, define $a\sim b$ to mean that $a$ and $b$ have the same length; $\sim$ is an equivalence relation.

If $\sim$ is an equivalence relation defined on the set $A$ and $a\in A$,
let
$$
[a]=\{x\in A: a\sim x\},
$$
called the
**equivalence class corresponding to**
$a$. Observe that reflexivity implies that $a\in
[a]$.

Example 5.1.5 If $A$ is $\Z$ and $\sim$ is congruence modulo 6, then $$ [2]=\{…, -10, -4, 2, 8, …\}. $$

Example 5.1.6 Using the relation of example 5.1.3, $[math]$ is the set consisting of all 4 letter words.

Example 5.1.7 Using the relation of example 5.1.4, $[(1,0)]$ is the unit circle.

Theorem 5.1.8 Suppose $\sim$ is an equivalence relation on the set $A$. Then for all $a,b\in A$, the following are equivalent:

a) $a\sim b$,

b) $[a]\cap [b]\ne \emptyset$,

c) $[a]=[b]$.

**Proof.**

(a) $\Rightarrow$ (b). Suppose $a\sim b$.
Then $b$ is an element of $[a]$. Since $b$ is also in $[b]$,
$b\in [a]\cap [b]$, so $[a]\cap [b]\ne \emptyset$.

(b) $\Rightarrow$ (c). Suppose $y\in [a]\cap [b]$, that is, $a\sim y$ and $b\sim y$. We need to show that the two sets $[a]$ and $[b]$ are equal. If $x\in [a]$, then $b\sim y$, $y\sim a$ and $a\sim x$, so that $b\sim x$, that is, $x\in [b]$. Conversely, if $x\in [b]$, then $a\sim y$, $y\sim b$ and $b\sim x$, so that $a\sim x$, that is, $x\in [a]$.

(c) $\Rightarrow$ (a). If $[a]=[b]$, then since $b\in [b]$, we have $b\in [a]$, that is, $a\sim b$.

Let $A/\!\!\sim$ denote the collection of equivalence classes; $A/\!\!\sim$ is a partition of $A$. (Recall that a partition is a collection of disjoint subsets of $A$ whose union is all of $A$.) The expression "$A/\!\!\sim$'' is usually pronounced "$A$ mod twiddle.''

Example 5.1.9 Using the relation of example 5.1.5, $$ A/\!\!\sim\; = \{[0], [1], [2], [3], [4], [5]\}=\Z_6 $$

Example 5.1.10 Using the relation of example 5.1.3, $$ A/\!\!\sim\; =\{\{\hbox{one letter words}\}, \{\hbox{two letter words}\}, \{\hbox{three letter words}\},…\} $$

Example 5.1.11 Using the relation of example 5.1.4, $A/\!\!\sim\; =\{C_r\!: 0\le r\in \R\}$, where for each $r>0$, $C_r$ is the circle of radius $r$ centered at the origin and $C_0=\{(0,0)\}$.

## Exercises 5.1

**Ex 5.1.1**
Suppose $A$ is $\Z$ and $n$ is a fixed
positive integer. Let $a\sim b$ mean that $a\equiv b \pmod n$. Prove
that $\sim$ is an equivalence relation.

**Ex 5.1.2**
Let $A=\R^3$.
Let $a\sim b$ mean that $a$ and $b$ have the same $z$
coordinate. Show $\sim $ is an equivalence relation and describe $[a]$
geometrically.

**Ex 5.1.3**
Suppose $n$ is a positive integer and $A=\Z_n$. Let $a\sim b$
mean there is an element $x\in \U_n$ such that $ax=b$. Show $\sim$ is
an equivalence relation. Compute the equivalence classes when $n=12$.

**Ex 5.1.4**
Recall from section MISSING XREFN(sec:The Phi Function—Continued)
the set $G_e=\{x\mid 0\le x< n, (x,n)=e\}$. There you find an example
using $n=12$, and the sets $G_e$ bear a striking resemblence to the
answer to the previous problem. For each divisor $e$ of $n$, define
$A_e=\{eu \bmod n\mid (u,n)=1\}$, which are essentially the equivalence
classes of the previous exercise. Prove that $A_e=G_e$.

**Ex 5.1.5**
Let $S$ be some set and $A={\cal P}(S)$. For any $a,b\in A$, let
$a\sim b$ mean that $a$ and $b$ have the same
cardinality. Show $\sim$ is an equivalence
relation. Compute the equivalence classes when $S=\{1,2,3\}$.

**Ex 5.1.6**
The following purports to prove that the reflexivity condition is
unnecessary, that is, it can be derived from symmetry and transitivity:

Suppose $a\sim b$. By symmetry, $b\sim a$. Since $a\sim b$ and $b\sim a$, by transitivity, $a\sim a$. Therefore, $\sim$ is reflexive.

What's wrong with this argument?

**Ex 5.1.7**
The example in 5.1.5 and
5.1.9 is a little peculiar, since at the time we
defined $\Z_6$ we attached no "real'' meaning to the notation $[x]$.
Discuss.

**Ex 5.1.8**
Suppose $\sim$ is a relation on $A$ that is
reflexive and has the property that for all $a,b,c$, if $a\sim b$ and
$a\sim c$, then $b\sim c$. Show $\sim$ is an equivalence relation.

**Ex 5.1.9**
Suppose $\sim_1$ and $\sim_2$ are equivalence relations on
a set $A$. Let $\sim$ be defined by the condition that $a\sim b$ iff
$a\sim_1 b\land a\sim_2 b$. Show $\sim$ is an equivalence relation on
$A$. If $[a]$, $[a]_1$ and $[a]_2$ denote the equivalence class of
$a$ with respect to $\sim$, $\sim_1$ and $\sim_2$, show $[a]=[a]_1\cap
[a]_2$.

**Ex 5.1.10**
What happens if we try a construction similar to problem
9 with $\lor$ replacing $\land$?

**Ex 5.1.11**
Suppose $f\colon A\to B$ is a function and $\{Y_i\}_{i\in I}$
is a partition of $B$. Prove $\{f^{-1}(Y_i)\}_{i\in I}$
is a partition of $A$.