Explicit bijections are overrated.
We can prove the following three things (without the axiom of choice, which has been mentioned in the comments):
- If $A\subseteq\Bbb N$ then it is either finite or countably infinite.
- If $f\colon\Bbb N\to X$ is surjective, then $X$ is finite or countably infinite.
- There is a surjection from $\Bbb N$ onto $\Bbb Q$.
The first proof is quite easy, we simply start to enumerate $A$ according to the order induced from the usual order of the the natural numbers. Either we "finish" the set, in which case it's finite, or the enumeration produces a bijection of $A$ with $\Bbb N$.
The second proof is also easy, since the function is a surjection, every $x\in X$ has a least $n\in\Bbb N$ such that $f(n)=x$. This minimal $n$ is unique, so we defined an injection from $X$ into $\Bbb N$, which is a bijection with a subset of $\Bbb N$. By the first claim, $X$ is finite or countably infinite.
The last proof is also not difficult. First write a surjection of $\Bbb N$ onto $\Bbb{N\times N}$ and a surjection from $\Bbb N$ onto $\Bbb Z\setminus\{0\}$, compose them to a surjection from $\Bbb N$ onto $\Bbb{N\times (Z\setminus\{0\})}$. Then you the surjection you have defined, $(n,m)\mapsto\frac nm$.
Now we can conclude the fourth statement:
- $\Bbb Q$ is countably infinite.
Of course $\Bbb Q$ is not finite, and since there is a surjection from $\Bbb N$ onto $\Bbb Q$, the claim is proved.