Exercise 3.4

Proof. We show the three properties necessary for $\sim$ to be an equivalence relation:

• (Reflexivity) Consider any $a\in A$ so that of course $f(a)=f(a)$ since $f$ is a function. Hence $a\sim a$ so that $\sim$ is reflexive since $a$ was arbitrary.
• (Symmetry) Consider $a,b\in A$ and suppose that $a\sim b$. Then by definition $f(a)=f(b)$ so that obviously also $f(b)=f(a)$ since equality is symmetric. So of course $b\sim a$, which shows that $\sim$ is symmetric.
• (Transitivity) Consider $a,b,c\in A$ and suppose that $a\sim b$ and $b\sim c$. Then by definition $f(a)=f(b)$ and $f(b)=f(c)$ so that of course $f(a)=f(b)=f(c)$, and hence $a\sim c$. This shows that $\sim$ is transitive.

□

Proof. Define the function $g:A^{\text{∗}}\to B$ as follows. For any equivalence class $C\in A^{\text{∗}}$, we know that $C$ is nonempty since $A^{\text{∗}}$ is a partition of $A$. Hence there is an $a\in C$, so set $g(C)=f(a)$, noting that clearly $g(C)=f(a)\in B$ so that $B$ can be the range of $g$.

To show that $g$ is injective, consider two equivalence classes $C$ and $D$ where $g(C)=g(D)$. Then there are elements $c\in C$ and $d\in D$ where $f(c)=g(C)=g(D)=f(d)$. This shows that $c\sim d$ so that they must be in the same equivalence class. Thus $d\in C$ since $c\in C$, but also $d\in D$ so that $C$ and $D$ are not disjoint. Hence it must be that $C=D$ by Lemma 3.1, which shows that $g$ is injective.

To show that $g$ is surjective, consider any $b\in B$. Since $f$ is surjective, there is an $a\in A$ such that $f(a)=b$. Since $A^{\text{∗}}$ is a partition, $a$ must belong to an equivalence class $C\in A^{\text{∗}}$. Then there is an element $c\in C$ such that $g(C)=f(c)$ by the definition of $g$. Since $a$ and $c$ are both in the same equivalence class $C$, we have that $a\sim c$ so that $g(C)=f(c)=f(a)=b$. This shows that $g$ is surjective since $b\in B$ was arbitrary.

Therefore we have shown that $g$ is both injective and surjective, and so is a bijection by definition, as desired. □