# There is only one increasing bijection from $\mathbb{N}$ to an infinite subset $X\subseteq \mathbb{N}$

Exercise 23, page 45, from Elon's book Curso de Análise: vol 1 (In Portuguese) I will translate it.

Let $X\subseteq \mathbb{N}$ be an infinite subset. Show that there exists only one increasing bijection $f:\mathbb{N}\rightarrow X$.

-
Suppose there are two different ones. How can that be? – tomcuchta Jan 28 '12 at 0:51
In general, a linear order is called a well order if every nonempty subset has a minimal element. Between two well ordered sets there is a unique isomorphism, if it exists; otherwise one is isomorphic to a proper initial segment of the other (and as before the isomorphism is unique). – Asaf Karagila Jan 28 '12 at 1:01

1. Construct an order-preserving bijection $f:\mathbb N\to X$.
2. Note that $f^{-1}$ is order-preserving as well.
3. Assume $g$ is another increasing bijection $\mathbb N\to X$, then note that $h = f^{-1}\circ g$ is an oder-preserving bijection $\mathbb N\to\mathbb N$.
4. In particular $h$ maps the minimum of $\mathbb N$ to the minimum of $\mathbb N$. Thus $h(1)=1$ and $h$ induces an order-preserving a bijection $\mathbb N \setminus \{1\} \to \mathbb N \setminus \{1\}$
5. Show that inductively, $h(n)=n$ for all $n$. Conclude that $h$ is the identity, hence $f=g$.
-

$\bf Hint:$ Note that $f(1)$ must be the first element of $X$, $f(2)$ must be the second element of $X$ and so on ...

-

To show it's existence you have to use the well-ordering principle. Since $X\subseteq \mathbb{N}$, it admits a minimum element, say $p\in \mathbb{N}$. So you define $f:\mathbb N\to X$ recursively: put $f(0) = p$; now you define $X_1 := X-\{p\}$ and, again by the well-ordering principle, $X_1$ admits a minimum $p_1\in\mathbb{N}$; so you define $f(1) := p_1$. Assuming that you have already defined $f(n)$, in the same way as the others (taking the minimum element), you define $X_{n+1}: = X_{n}-\{f(n)\}$, and $p_{n+1}:=\min(X_{n+1})$. Since $X$ is infinite, every $X_n$ is non-empty; and every $p_k$ is the minimum of the set $X_k$ you have $p_m < p_n$ when $m<n$. That concludes the existence of such function. Now, with the non-increasing property you can show that $f$ is injective; and, the fact that $X$ is an infinite subset of $\mathbb{N}$ guarantees that $f$ is surjective.

To ensure it's uniqueness, suppose, for the sake of the proof, that you have a bijective function $g: \mathbb{N}\to X$ such that $g(m)\leq g(n)$ when $m\leq n$. Let $A$ be any non-empty subset of $\mathbb{N}$; hence, both $g(A)$ and $f(A)$ have a minimum. If $f(x)\neq g(x), \forall x\in A$; WLOG, you have $g(x)<f(x)$. Therefore, you have $g(\min(A)) < f(\min(A))$, witch is an absurd because $f$ and $g$ are both bijective. So you must have $f(x)\geq g(x)$. By the definition of $g$, if $f(x)>g(x)$, we have an absurd. So you must have $f=g$, which concludes the demonstration. $\blacksquare$

-