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.

  • $\begingroup$ 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? $\endgroup$ – bof May 26 '16 at 7:25
  • 1
    $\begingroup$ 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. $\endgroup$ – almagest May 26 '16 at 7:56
  • $\begingroup$ I suppose I wanted to avoid SB. $\endgroup$ – AJY May 26 '16 at 7:57
  • $\begingroup$ @bof It's the word I come across most often and am most partial to for when there exists a bijection between two sets. $\endgroup$ – AJY May 26 '16 at 7:58
  • $\begingroup$ @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. $\endgroup$ – 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:


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$.

  • $\begingroup$ I think that's pretty much what I did, just perhaps with a bit more words. $\endgroup$ – AJY May 28 '16 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.