# Bijection between Natural numbers and the range of a sequence

I came across this proof in the 3rd edition of Royden's Real Analysis which I find quite confusing. The problem statement and its proof are as follows.

If an infinite set $E$ is the range of a sequence , then $E$ can be put in one-to-one correspondence with $\mathbf{N}$. To do this we define a function $\phi:\mathbf{N} \rightarrow \mathbf{N}$ by recursion. Let $\phi(1)=1$ and define $\phi(n+1)$ to be the smallest value of $m$ s.t. $x_m\neq x_i$ for $i\leq \phi(n)$. Since $E$ is infinite such an $m$ always exists and by the well-ordering principle for $\mathbf{N}$ there is always a least such $m$. The correspondence $n\rightarrow x_{\phi(n)}$ is one-to-one between $\mathbf{N}$ and $E$.

I have the following questions and please forgive me if they're dumb (I'm mathematically illiterate).

1) Why doesn't the author just map each natural number to its corresponding element in the sequence, i.e., $1\rightarrow x_1$, $2\rightarrow x_2$, etc., to define a bijection between $\mathbf{N}$ and $E$?

2) The definition of $\phi(n+1)$ is quite confusing. For example, in the sequence $<1,1,2,...>$, would $\phi(3)$ take the value 2 or 4? If it takes the value 4, then the function is not a bijection then, right?

• The map $n\mapsto x_n$ may not be injective: consider the sequence $\langle 1,1,2,2,3,3,\ldots\rangle$, for instance. If we apply Royden's recipe to it, we get $\varphi(1)=1,\varphi(2)=3,\varphi(3)=5$, and so on. In general $\varphi(n)$ turns out to be the subscript of the $n$-th distinct term of the sequence. – Brian M. Scott Nov 8 '16 at 8:14

If the author did as you suggested, then for my sequence $\{1, 1, 2, 2, 4, 4, 8, 8, ...\}$ you would have both $1$ and $2$ mapped to $1$ thus not being a bijection.

Now the problem here surely is the part when we define $\phi(n+1)$. Let us try to "translate" what he wrote there.

When he talks about setting $\phi(n+1)$ he assumes that we already know all the values of $\phi$ for $i \le n$. The idea behind this proof is mapping each natural $n$ to the $n$th unique number that appears in the range, by the order in which they appear.

Consider again

$$\{1, 1, 2, 2, 4, 4, 8, 8, ...\}$$

Then the first number to appear in the range is obviously the first number of the sequence, $x_1$ so $\phi(1) = 1$. Now the second unique number to appear is $2$, that is $x_3$ so for this case $m=3$ and $\phi(2) = 3$ because $x_3 \notin \{x_1, x_2\}$. The third unique number here is $4$, in the $5$th position so $\phi(3) = 5$ because $x_5 \not\in \{x_1, ..., x_4\}$ and so on and so forth.

The author concludes by saying that we can keep on doing this forever because

1) The set $E$ is infinite;

2) Because $\mathbb {N}$ is well-ordered we can always pick the smallest $n$ that would be of good use to us.