5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Why should $f$ be surjective? $\endgroup$ – alex Mar 14 '14 at 8:32
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why you say "not an unordered set", you mean not a well-ordered set? $\endgroup$ – 6005 Mar 14 '14 at 15:59
  • $\begingroup$ Of course. Thank you. $\endgroup$ – 5xum Mar 14 '14 at 19:17
4
$\begingroup$

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)

$\endgroup$

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.