Equivalence Classes Proof

Question

I'm having problems proving this:

Suppose that $ f: A \to B $ is a surjective function. Define the following relation on A: $a_1 \sim a_2 $ if and only if $f(a_1)=f(a_2)$. Denote by $A/\sim$ the set of equivalence classes of $\sim$. Prove that $$ |A/\sim| =|B| .$$ I know that each equivalence class of each $a_i$ in A is the set of all $a_j$ in A that is sent to the same $b_k$ in B as $a_i$ is, so each equivalence class in $A/\sim$ should correspond to a $b_k$ in B, thus they must have the same size. I just don't know how to put this into a mathematical proof.

Answer 1

You basically gave the proof already, so let's turn it into a precise mathematical proof.

To show that $|A / \sim | = |B|$, we need to construct a bijection $g: A / \sim \to B$. You already told us how to construct this bijection: let $[a]$ be the equivalence class of some $a \in A$, then we set $g([a]) = f(a)$. We need to check a few things now.

Well-defined. The function $g$ is indeed well-defined. That is, it does not depend on the representative of the equivalence class. So if $a \sim a'$, then by definition that means that $f(a) = f(a')$ so indeed the value of $g$ is well-defined.

Injective. Suppose that $g([a]) = g([a'])$, so $f(a) = f(a')$. Then by definition $a \sim a'$, so $[a] = [a']$ and $g$ is indeed injective.

Surjective. Let $b \in B$, then because $f$ is surjective there is $a \in A$ such that $f(a) = b$. So $g([a]) = f(a) = b$, and indeed $g$ is surjective.

Altogether we have a bijection $A / \sim \to B$, so $|A / \sim| = |B|$.

Answer 2

The map $b\mapsto[b]:=\{a\in A: f(a)=b\}$ defines a surjection from $B$ to $A/\sim$ because $[f(a)]$ is precisely the equivalence class $\sim a$ of $a$ under $\sim$. Finally, $b\mapsto[b]$ is an injection because $$[b]=[b']\implies\forall x\in[b]\;f(x)=b=b'\implies b=b'$$.