If a set is countable and infinite, there is a bijection between the set and $\mathbb{N}$

Question

I'm trying to show that if a set $S$ is infinite and countable then there is a bijection $\varphi : S\to \mathbb{N}$. Since $S$ is countable, we know that there is an injection $f: S\to \mathbb{N}$. Now there are two things that can be done:

1. We can construct a bijection $\varphi : S\to \mathbb{N}$ directly.
2. We can construct a surjection $g: S\to \mathbb{N}$ and use Cantor-Bernstein-Schröder theorem to show there is a bijection between $S$ and $\mathbb{N}$.

The second way seems better, but I don't know how to start. I thought on the following: we want to build a surjection $g : S\to \mathbb{N}$. For that, fix an element $a_1\in S$ and define $g(a_1)=1$. Now, since $S$ is infinite, $S\setminus\{a_1\}$ is infinite, so we can pick $a_2\in S\setminus\{a_1\}$ and define $g(a_2)=2$.

We can continue this procedure arbitrarily so that given $n$ we will have $a_n\in S\setminus\{a_1,\dots,a_{n-1}\}$ so that $g(a_n)=n$, so that $g$ is a surjection.

Although the idea is clear to me, I recognize it lacks rigor. First of all, the statement "continue this process arbitrarily" when defining $g$ is not meaningful from a rigorous standpoint in my opinion. I believe there should be some argument with the axiom of choice to make this rigorous, but there might be a simpler way.

In that case, is this a correct way to prove the result? Also, how to make this idea I exposed rigorous and define $g$ correctly?

EDIT: The definitions I'm using are as follows:

1. A set $S$ is countable if there is an injective function $f : S\to \mathbb{N}$

2. A set $S$ is infinite if for all $n\in \mathbb{N}$ there is no bijection between $S$ and $\{1,\dots,n\}$.

From the second definition then I've proved that if $S$ is infinite and $a\in S$ then $S\setminus\{a\}$ is non-empty and still infinite.

Answer 1

Given an injection $f : S \to \mathbb{N}$, where $S$ is infinite, you can define a function $h : \mathbb{N} \to S$ by, for each $n \in \mathbb{N}$, defining $h(n)$ to be the element $s \in S$ for which $f(s)$ is the $n^{\text{th}}$ least element of $f(S) \subseteq \mathbb{N}$. This is possible because $S$ is infinite, so such an element $s \in S$ always exists, and $f$ is injective, so such an element $s \in S$ is unique.

It is straightforward to check that $h$ is bijective; then setting $g=h^{-1}$ gives you a bijection $g : S \to \mathbb{N}$.

Answer 2

Consider the range of the injection $f:S\to\Bbb N.$ It will necessarily be an infinite (why?) subset of $\Bbb N,$ which can readily (and order-isomorphically!) be mapped onto $\Bbb N$ by sending its least element to the least element of $\Bbb N,$ its second-least element to the second-least element of $\Bbb N,$ and so on.

Edit: Basically, all you have to do is adapt your approach slightly. Let $A$ be the range of $f,$ so that $A\subseteq\Bbb N$ and $f:S\to A$ is a bijection. (Why?) Then we define a function $g:A\to\Bbb N$ as follows: Let $g(\min A)=1,$ and for all $n\in\Bbb N,$ let $$g\Bigl(\min\bigl(A\setminus \{a\in A\mid g(a)\le n\}\bigr)\Bigl)=n+1.$$ You should try to show that $g$ is well-defined and that $g:A\to\Bbb N$ is a bijection.

Once everything above is proved, it is fairly straightforward to prove that $g\circ f$ is the desired bijection $S\to\Bbb N.$ Let me know if you get stuck with any steps of the proof, and I'll do what I can to get you unstuck when I am able. Also, feel free to bounce your reasoning off me if you just want someone to check your thinking.

Answer 3

Since $f$ is an injection, we have that $f:S\rightarrow f(S)$ is a bijection. Since $f(S)\subset N$. It suffices to find a bijection between some infinite subset $A\subset N$ and $N$.

Now, we can construct the following bijection $g:N \rightarrow A$:

$g(1):=\min A$, $g(2):=\min (A-\{g(1)\})$, $g(3):=\min (A-\{g(1),g(2)\})$ and so on.

It remains to show that $g$ is a bijection.

Answer 4

Any injection becomes a bijection when its codomain is restricted to its image. Given an injection $f : S \to \mathbb{N}$, define a bijection $\tilde{f} : S \to f(S)$ as, for all $s \in S$, $\tilde{f}(s) = f(s)$.

$f(S)$ must be infinite since $S$ is infinite and $\tilde{f} : S \to f(S)$ is injective. Thus $f(S)$ is an infinite subset of $\mathbb{N}$, so there is a bijection $g : f(S) \to \mathbb{N}$. Then $g \circ \tilde{f} : S \to \mathbb{N}$ is a bijection since the composition of two bijections is a bijection.

---

Why does "infinite subset of $\mathbb{N}$" imply "there is a bijection into $\mathbb{N}$"? See this question; you can use the inverse of the map $\varphi : \mathbb{N} \to f(S)$ defined by $\varphi(n) = $ the $n$th smallest element of $f(S)$.

(This post is a rephrasing of the argument from user178826.)