Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks for your help!

share|improve this question
    
Suppose there are two different ones. How can that be? –  tomcuchta Jan 28 '12 at 0:51
1  
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

3 Answers 3

up vote 4 down vote accepted
  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$.
share|improve this answer

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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