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.

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|improve this question
2  
Why should $f$ be surjective? –  alex Mar 14 at 8:32
add comment

2 Answers 2

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|improve this answer
    
Why you say "not an unordered set", you mean not a well-ordered set? –  Goos Mar 14 at 15:59
    
Of course. Thank you. –  5xum Mar 14 at 19:17
add comment

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|improve this answer
add comment

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.