Let $S$ be a countable well-ordered set which is unbounded (i.e. it has no maximum). Does there exist an unbounded increasing sequence in $S$?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Are you asking if every countable ordinal does, or if there is some countable ordinal which does? $\endgroup$– B. MehtaMar 17, 2018 at 19:18
-
$\begingroup$ Thanks, I meant does every countable ordinal...? $\endgroup$– Erfan SalavatiMar 17, 2018 at 19:20
-
$\begingroup$ Take $\omega + 1$. $\endgroup$– B. MehtaMar 17, 2018 at 19:23
-
$\begingroup$ Thanks for the example but indeed this is not what I wanted. Archimedean was not a proper term that I used here... $\endgroup$– Erfan SalavatiMar 17, 2018 at 19:27
-
$\begingroup$ $\omega + 1$ is a countable ordinal, and equivalently $0, 1, 2, \dotsc, \omega$ is well-ordered but does not contain an unbounded increasing sequence since $\omega$ is an upper bound for the whole sequence. $\endgroup$– B. MehtaMar 17, 2018 at 19:29
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
1
Hint: let $f : \omega \to S$ enumerate $S$. Starting at $1$, remove $i$ from the domain of $f$ if $f(i) < f(j)$ for some $j < i$. The result is an unbounded partial function from $\omega$ to $S$, which you can convert into a sequence by renumbering the arguments.
answered Mar 17, 2018 at 19:46
-
$\begingroup$ Nice solution. It works for any totally ordered countable set. $\endgroup$ Mar 17, 2018 at 19:54
$\begingroup$
$\endgroup$
I found a related question which answers this question too.
A generalization of "any countable limit ordinal is the union of a sequence of increasing ordinal"
$\begingroup$
$\endgroup$
1
Yes.
Let $s_1$ be an element of $S$. Because $S$ is unbounded, $s_1$ can't be the maximum element. Therefore, there exists at least one element of $S$ greater than $s_1$. Call this element $s_2$. $S$ also can't have $s_2$ as its maximum element, so there must be an element of $S$ (call it $s_3$) greater than $s_2$.
Repeat this process ad infinitum, and you have an unbounded increasing sequence.
-
$\begingroup$ It is not necessarily unbounded. It is possible that some element of $S$ is greater than all the elements of the sequence. $\endgroup$ Mar 18, 2018 at 11:20