[Math] $A$ is a countable set if and only if exist a injective function $h: A \to \mathbb{N} $

elementary-set-theory

$A$ is a countable set if and only if exist a injective function $h: A \to \mathbb{N} $

I have the second implication: we know that $\mathbb{N}$ is countable then exist a injective function such that $h: A \to \mathbb{N}$ then $A$ is countable.
But for first implication I don't know what I can do. I try with inverse function but, with my definition of countable set ($A$ is countable set if exist a surjective function $f: \mathbb{N} \rightarrow A$) and with composition I can't have the correct answer.

Best Answer

Suppose $A \neq \varnothing$ is countable. So there is $f: \mathbb{N} \to A$ surjective (your definition). To each $a \in A$, $f^{-1}(\{a\}) \neq \varnothing$, let $h(a) = \min f^{-1} (\{a\}) \in \mathbb{N}$ (because $\mathbb{N}$ is well ordered). Define $h: A \to \mathbb{N}: a \mapsto h(a)$.

Note, $$(f\circ h)(a) = f(h(a)) = f(\min f^{-1} (\{a\})) = a $$, then $h$ is injective.