Equivalence Classes Proof 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.
 A: 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|$.
A: 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'$$.  
