# Proof that countable infinite set is equitotient to $\mathbb{N}$

So I wanna show that if $Y$ is an infinite countable set (i.e. there exists a surjection $\phi: \mathbb{N} \to A$), then there exists a bijection $\psi: \mathbb{N} \to A$. Here's what I came up with.

Define a sequence of maps $f_{i} : \mathbb{N} \to A, i \in \mathbb{N}$ as follows: Set $f_0 = \phi$, and construct $f_{i}$ by setting $f_{i} = f_{i - 1}$ if $f_{i - 1}$ is an injection, and if not let $f_{i}(x) = \begin{cases} f_{i - 1}(x) & x < \min \{ x \in \mathbb{N} : (\exists x' < x)(f_{i - 1}(x') = f_{i - 1}(x) \\ f_{i - 1}(x + 1) & \textrm{otherwise} \end{cases}$. That is, since we're trying to make an injective map, the next map in the sequence is made by taking the first instance of "repetition" in $f_{i - 1}$, taking it out and sliding it along. So if $f_{i - 1} = (1, 2, 3, 4, 5, 1, 6, 7, 8, 9, 10, 9, 15, 19, 23, \ldots)$, then $f_{i} = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 15, 19, 23, \ldots)$. I then want to take a sort of "limit" of these $f_{i}$ to come up with a new map that has no repetition. So construct the map $g_{i} : A \to \mathbb{N}$ by $g_{i}(a) = \min \{ x \in \mathbb{N} : f_{i}(x) = a \}$. Then since $(g_{i}(a))_{i \in \mathbb{N}}$ is a bounded monotonic sequence in $\mathbb{N}$, there exists $\lim_{i \to \infty} g_{i}(a) = \min \{ g_{i}(a) : i \in \mathbb{N} \} = : g_{\infty}(a)$.

I want to show $g_{\infty} : A \to \mathbb{N}$ is a bijection, and then set $\psi = g_{\infty}^{- 1}$.

First we show $g_{\infty}$ is injective. Suppose to the contrary that there exists $x_{0} \in \mathbb{N}$ for which there exist distinct $a, a' \in A$ such that $g_{\infty}(a) = g_{\infty}(a') = x_{0}$. Recall that $(g_{i}(a))_{i \in \mathbb{N}}$ is a downward monotonic sequence in $\mathbb{N}$, so there exist $i, i' \in \mathbb{N}$ for which $g_{i}(a) = g_{i'}(a') = x_{0}$. Suppose without loss of generality that $i \geq i'$. Then $f_{i}(x_{0}) = a$ and $f_{i}(x_{0}) = a'$, where $a \neq a'$, a contradiction. Thus $g$ is injective.

Second we show it is surjective, which we again do by suppose to the contrary that $g_{\infty}$ is not surjective. If $y \in \mathbb{N} \setminus g_{\infty}(A)$, then there does not exist $i_{y} \in \mathbb{N}$ such that $f_{i}(y) = f_{i_{y}}(y)$ for all $i \geq i_{y}$. Let $y_{0} = \min (\mathbb{N} \setminus g_{\infty}(A))$. Then for each $x \in \{ 1, \ldots, y_{0} - 1 \}$ exists $a_{x}$ such that $g_{\infty}(a_{x}) = x$. In fact, there exists $i_{0}$ such that for all $i \geq i_{0}$ we have $g_{i}(a_{x}) = x$, and thus $f_{i}(x) = a_{x}$ for $x < y_{0}$. Let $x_{0} = \min \{ x \geq y_{0} : (\nexists x' < x)(f_{i_{0}}(x) = f_{i_{0}}(x')) \}$, i.e. the first element of $\mathbb{N}$ to map to a "new" element in $f_{i_{0}}$.

We claim $g_{\infty}(f_{i_{0}}(x_{0})) = y_{0}$. Let $\ell = x_{0} - y_{0}$. We claim that $f_{i_{0} + \ell}(y_{0}) = f_{i_{0}}(x_{0})$.* But this means that in fact $y_{0} \neq \min (\mathbb{N} \setminus g_{\infty}(A))$, so we have a contradiction. This concludes the proof.

Is the above correct?

*I just realized I'm not entirely sure how to demonstrate this.

• Your question is too complicated for me, but +1 for learning me a new word, "equitotient". Is that in some book, or did you make it up yourself? – bof May 26 '16 at 7:25
• You have that $A$ is infinite, which means that you have an injection $\mathbb{N}\to A$. You also have that $A$ is countable, which you express as having a surjection $\phi:\mathbb{N}\to A$. Defining $f:A\to\mathbb{N}$ as $f(a)$ is the smallest member $k$ of $\mathbb{N}$ such that $\phi(k)=a$, gives you an injection $f$. So now use the Schroder-Bernstein theorem. – almagest May 26 '16 at 7:56
• I suppose I wanted to avoid SB. – AJY May 26 '16 at 7:57
• @bof It's the word I come across most often and am most partial to for when there exists a bijection between two sets. – AJY May 26 '16 at 7:58
• @Winther Suppose $A=\mathbb{N}$ and $\phi(2n)=\phi(2n+1)=n$. Then $\phi$ is a surjection and $f(n)=2n$, so $f$ is an injection but not a bijection. – almagest May 26 '16 at 8:33

In all honesty I did not check the details of your construction; I just wanted to note that you’re working much too hard. Suppose that $\varphi:\Bbb N\to A$ is a surjection. Then the function
$$\psi:A\to\Bbb N:a\mapsto\min\{n\in\Bbb N:\varphi(n)=a\}$$
is an injection. Let $R=\psi[A]$. Define $f:\Bbb N\to R$ recursively:
$$f(n)=\min\big(R\setminus\{f(k):k<n\}\big)\;.$$
Since $A$ is assumed to be infinite, $f$ is defined on all of $\Bbb R$, and it’s easily checked that $f$ is a bijection. Then $\varphi\circ f$ is a bijection from $\Bbb N$ to $A$.