Suppose $B \neq \varnothing$. Prove the following are equivalent
${\bf A.}$ B countable
${\bf B.}$ there is a surjection $f: \mathbb{Z}_+ \to B$
${\bf C.}$ there is an injection $g: B \to \mathbb{Z}_+ $
Attempt:
(I already proved $A \implies B$) First we prove $B \implies C$. Let $f$ be surjection. Since $B$ is not empty, it has a smallest element, say $b_1$ and $f$ surjection $\implies$ there is some $i_1 \in \mathbb{Z}_+$ such that $f(i_1) = b_1$
Now, consider $B \setminus \{ b_1 \}$. If this set is empty, then $g(b_1) = i_1$ is desired injection.
If not, then there is smallest element in $B \setminus \{b_1\}$, call it $b_2$ and so $\exists i_2 \in \mathbb{Z}_+$ so that $f(i_2) = b_2$
Now, if $B \setminus \{ b_1, b_2\}$ is empty, then $g(b_k) = i_k $ for $k=1,2$
If we continue in this fashion, we obtain a list $\{ b_1,b_2,...... \}$ so that $g(b_k) = i_k $ where $i_1,i_2,.....$ are positive integers.
${\bf C \implies A}$
Take $g: B \to \mathbb{Z}_+$ an injection. We need to prove $B$ is countable.
By contradiction if $B$ is uncountable, then there is ${\bf NO}$ bijection from $B \to \mathbb{Z}_+$ but this really doesnt help, we can still have injections.
My other idea is to procceed as : since $g$ is injection then $g$ maps some $b_i$ from $B$ in one-to-one correspondence to positive integers: $g(b_i) = i$ say $i \leq n$
But I am having trouble seeing how to extend this to a surjection. Any help? Is my first implication correct?
C is usually the definition of countable.
To finish the proof prove
exists injection f:X -> Y iff exists surjection g:Y -> X.
Left to right. Let g(y) = f$^{-1}$(y) for all y in f(X)
and for all y not in f(X), g(y) any element of X.
Conversely define for all x in X, f(x) to be some element in g$^{-1}$(x).