Blog

Let $f : A \rightarrow B$ be a surjective map of sets. Prove that the relation $\sim$ on $A$ given by $a \sim b$ iff $f(a) = f(b)$ is an equivalence relation and that the equivalence classes of $\sim$ are precisely the fibers (i.e. the preimages of elements) of $f$.

Solution: First we show that $\sim$ is an equivalence relation.

1. We have $f(a) = f(a)$ for all $a \in A$ since set equality is reflexive, $\sim$ is reflexive.
2. Suppose $a \sim b$. Then $f(a) = f(b)$. Since set equality is symmetric, $f(b) = f(a)$, hence $b \sim a$. Thus $\sim$ is symmetric.
3. Suppose $a \sim b$ and $b \sim c$. Then we have $f(a) = f(b)$ and $f(b) = f(c)$. Since set equality is transitive, we have $f(a) = f(c)$, hence $a \sim c$. Thus $\sim$ is transitive.

Now we will show that every $\sim$-equivalence class is the preimage of some element of $B$ and vice versa.

• Let $X$ be a $\sim$-equivalence class. Then $X$ is nonempty; choose some $x \in X$. By definition, then, for all $a \in A$ we have $a \in X$ if and only if $a \sim x$; that is, $f(a) = f(x)$. Since $X$ was arbitrary, we have that $X$ is the $f$-preimage of some $x \in B$ for all $\sim$-equivalence classes $X$.
• Let $f(x) \in B$ (note that $f$ is surjective), and consider $f^\star(x)$, the $f$-preimage of $x$. Note that for all $a \in A$, we have $a \in f^\star(x)$ if and only if $f(a) = f(x)$; that is, $a \sim x$. Since $x$ was arbitrary and $f$ is surjective, we have that $f^\star(x)$ is a $\sim$-equivalence class for all $x \in B$.