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

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. $\square$

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). $\square$

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. $\square$

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. $\square$

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, …\}. $$ $\square$

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

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

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$. $\qed$

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 $$ $\square$

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}\},…\} $$ $\square$

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)\}$. $\square$

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 3.9 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$.