Is this a surjection? (Elementary real analysis) My question is at the bottom of this wall of text, but this text is crucial to the question. I am reading Real Mathematical Analysis by Pugh, and on page 33 he states and proves the following theorem.
Theorem. If $f:\mathbf{N}\to B$ is a surjection and $B$ is infinite, then $B$ is denumerable.
Before reading his proof, I tried the following.
Proof. For each $b \in B$, define $S_b = \{n\in\mathbf{N}\mid f(n) = b\}$, which is nonempty for each $b\in B$ since $f$ is a surjection. Define $\phi: B \to \mathbf{N}$ by $\phi(b) = \min S_b$. If $\phi$ is a bijection, we are done.
Lemma. $\phi: B\to \mathbf{N}$ is a bijection.
Proof. We show that $\phi$ is injective. Suppose that $\phi(b) = \phi(b')$. Then, we have that $\min S_b = \min S_{b'}$, so $b = b'$ by the definition of $f$.
Here's where I am having trouble, and where I notice Pugh diverges from me. I would like to show that $\phi$ is a surjection and be done. However, I am having trouble showing that for each $n\in \mathbf{N}$, $n = \phi(b)$ for some $b$ in $B$. I would like to say that since $f$ is defined everywhere on $\mathbf{N}$ and $S_b$ is nonempty for each $b$, $n = f(b)$ for some $b$, namely the $b$ corresponding to $\min S_b$.
The way Pugh shows this result is true is not so important to me, and my question is whether I am on the right track with this proof, and how can I show that $\phi$ so defined is a surjection? Thanks.
 A: You might have made a minor mistake, consider the following example:
let your set $B=\textbf{N}$. Define $f$ as follow:
$f(2n)=f(2n+1)=n$.
Now $\phi: B \rightarrow \textbf{N}$ is not a surjection, because $\phi(n)=2n$. For example $\phi^{-1}(1)=\emptyset$.
A: For each $b\in B$ let $g(b)=\min f^{-1}\{b\}=\min \{n : f(n)=b\}.$ Then $g$ is a bijection from $B$ to  $G=\{g(b):b\in B\}\subset  N.$
Now for  $n\in G$ let $h(n)\in N$, where $h(n)$ is the number of members of $\{j\in G:j\leq n \}.$ (So  $h(n)=m$ iff $n$ is the $m$-th least member of $G.$) Then $h$ is a bijection from $G$ to $H=\{h(n):n\in G\}.$ And the composite function $h g :B\to H$ is also a bijection.
(1).  $B\ne \emptyset \implies G\ne \emptyset \implies 1=h(\min G)\implies 1\in H. $ 
(2). For any $n\in N,$ suppose $S(n)=\{j\in N:j\leq n\}\subset H.$ Then $S(n)\ne H$ (else $h g:B\to S(n)$ is a bijection, and  and $B$ would have exactly $n$ members).  So $h(\min \{k\in G:k>n\})=n+1,$ and so  $S(n+1)\subset H.$
(3). From (1) and (2) we have, by induction, $H=N.$ So $h g:B\to H$ is a bijection from $B$ to $N.$      
