2
$\begingroup$

Every countably infinite linear order $L$ has a copy of $\omega$ or $\omega^{op}$. I'm interested in different kinds of proofs of this fact.

One I came up with is: pick $x_0 \in L$. Wlog $[x_0, +\infty)$ is infinite. If there is no maximum element, it is easy to embed $\omega$ by recursion. Else, let $M$ be the maximum and embed $[x_0, M]$ into $[0,1]$ fixing the endpoints. By sequential compactness there will be a limit point. So to one of the sides of that limit point there will be infinitely many points of our set and we can keep picking points closer and closer to it to get either $\omega$ or $\omega^{op}$.

I find this proof a bit ugly. What are other ways to prove this?

$\endgroup$
1
  • $\begingroup$ You can get a limit point more quickly by enumerating $L$ then embedding it in its closure, which is always compact. This gets you an accumulation point so you take the subsequence that limits to that point. You don't need to worry about different cases except above/below the limit point. $\endgroup$
    – Zoe Allen
    Commented Jul 8 at 15:18

2 Answers 2

Reset to default
3
$\begingroup$

You can use Ramsey's theorem. Enumerate $L = \{x_n:n\in \omega\}$ and color an edge $\{x_n,x_m\}$ of the complete graph on $L$ red if $x_n < x_m$ for $n<m$ (i.e. their order agrees with the order of their index), otherwise blue. Ramsey's theorem says there is an infinite subset $L'\subseteq L$ such that all edges between points in $L'$ have the same color. The points in $L'$, listed in order of increasing index, will be an infinite increasing or decreasing sequence.

$\endgroup$
3
$\begingroup$

If $L$ contains no copy of $\omega^{op}$ it is wellfounded. An infinite wellorder always has an initial segment isomorphic to $\omega$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .