Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know there are well-ordered sets that are not countable.

Suppose you are given an uncountable, well-ordered set $S$.

Isn't it possible to provide a bijection $f:\mathbb{N} \rightarrow S$ as following?

$S$ is well-ordered, so it has the smallest element, say $s_1$. $S \setminus$ {$s_1$} is also well-ordered, so there is the next smallest element, $s_2$, Similarly, there is the next smallest element $s_3$, and so on.

Continuing like this, define $f(i) = s_i$.

I know there is something wrong with this, but I cannot really see why...

share|cite|improve this question
Why should $f$ be surjective? – alex Mar 14 '14 at 8:32
up vote 8 down vote accepted

Suppose you are given an uncountable, well-ordered set $S$.

Isn't it possible to provide a bijection $f:\mathbb{N} \rightarrow S$

No. $\mathbb N$ is countable. You will end up with a set of elements $\{s_1,s_2,s_3,\dots\}$, but there will exist elements you have not covered. There is nothing in your definition that demands you covered all of the elements.

An example (not a well ordered set, I know, but may still illustrate my point) is if you look at the set $$S=\left\{\frac12, \frac23, \frac34, \dots, \frac{n}{n+1},\dots\right\}\cup[1,2]$$

The procedure you described works on $S$, although $S$ is not well ordered. It takes $\frac12 = s_1$ as it is the least element. Then it takes $s_2=\frac23$ and so on. It produces $s_i = \frac{i}{i+1}$ which is an injection from $\mathbb N$ to $S$, but it does not cover the whole $S$.

Edit: In fact, you can even take the set $$T=\left\{\frac12, \frac23, \frac34, \dots, \frac{n}{n+1},\dots\right\}\cup\{1\},$$ whic is well ordered and is even countable, but your procedure still does not produce a bijection from $\mathbb N$ to $T$.

share|cite|improve this answer
Why you say "not an unordered set", you mean not a well-ordered set? – 6005 Mar 14 '14 at 15:59
Of course. Thank you. – 5xum Mar 14 '14 at 19:17

Even if you made a mistake about surjectivity, as pointed out by 5xum and alex, you did a good thing: you proved that

given any two well-ordered sets, one is always the intial segment of the other! (which is, of course, true. The proof needs transfinite induction in general, but works exactly as your attempt of building the bijection)

share|cite|improve this answer

Your Answer


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.