(a) Let $f: A \to B$ be a surjective function. We define $a_1 \sim a_2$ if $f(a_1)=f(a_2)$. Prove that $\sim$ is an equivalence relation.
-
Reflexivity: This comes for free. If $a_1 \sim a_1$, then $f(a_1)=f(a_1)$.
-
Symmetry: Suppose $a \sim b$. Then $f(a)=f(b)$. But that is the same as saying $f(b)=f(a)$. Thus $b \sim a$.
-
Transitivity: Suppose $a \sim b$ and $b \sim c$. Then $f(a)=f(b)$ and $f(b)=f(c)$. Then $f(a)=f(c)$. Thus $a \sim c$.
(b) Suppose $A$ is a set and $\sim$ is an equivalence relation on $A$. Find a set $B$ and a function $f\colon A \to B$ such that $f(a_1)=f(a_2)$ exactly when $a_1\sim a_2$.
This one I'm not sure how to even start. It does seem like I am trying to prove the converse to part (a), but I am not sure.
Best Answer
Hint: Let $B = \{[a] : a \in A\}$, where $[a]$ is the equivalence class of $a$. More particularly,
$$[a] = \{x \in A : x \sim a\}$$
Now try defining $f(a) = [a]$.
To prove that $f$ has the desired properties, suppose that $a_1 \sim a_2$; then by definition of an equivalence class, $a_1$ and $a_2$ lie in the same equivalence class; that is, $[a_1] = [a_2]$. Hence,
$$f(a_1) = [a_1] = [a_2] = f(a_2)$$
as desired. Now on the other hand, suppose that $f(a_1) = f(a_2)$. Then $[a_1] = [a_2]$, and in particular, $a_1 \in [a_2]$; hence, $a_1 \sim a_2$. This completes the proof.