3

Suppose $(\Omega,\leq)$ is a totally ordered set, with $\Omega$ infinite and countable. If $S$ is an infinite subset of $\Omega$, then $(S,\leq)$ denotes the induced totally ordered set.

Are there examples of such $(\Omega,\leq)$ for which no $(S,\leq)$ is order isomorphic to $(S',\leq)$ with $S' \subset S \ne S'$ ?

Boccherini
  • 779
  • https://math.stackexchange.com/questions/406019/do-there-exist-totally-ordered-sets-with-the-distinct-order-type-property-that https://math.stackexchange.com/questions/2539534/are-well-orderings-and-converse-well-orderings-the-only-partial-orderings-which https://math.stackexchange.com/questions/437826/is-this-a-characterization-of-well-orders – Asaf Karagila Dec 11 '18 at 14:18
  • Just to be clear about the quantifiers, you want an example of a totally ordered set, such that for every infinite subset $S$ and every proper subset $S'$, $S$ and $S'$ are non-isomorphic? – Alex Kruckman Dec 11 '18 at 14:19
  • @AlexKruckman : yes, indeed ! – Boccherini Dec 11 '18 at 14:23

1 Answers1

3

No, no such $(\Omega,\leq)$ exists. Let $(\Omega,\leq)$ be any countably infinite linear order. Then there is a subset $S\subseteq \Omega$ such that $(S,\leq)$ is isomorphic to either $\mathbb{N}$ or $\mathbb{N}^*$, where the latter is $\mathbb{N}$ with the usual order reversed (see below for a proof). In the first case, let $S'$ be $S$ without the least element, and in the second case, let $S'$ be $S$ without the gretest element. In either case, we have $S'\subsetneq S$, but $S'\cong S$.

Why does such a set $S$ exist? I think the easiest way to prove it is by Ramsey's theorem. Let $(a_n)_{n\in \mathbb{N}}$ be an enumeration of $\Omega$. We color a pair $(a_n,a_m)$ with $n<m$ red if $a_n\leq a_m$ in $\Omega$ and blue if $a_m \leq a_n$ in $\Omega$. By Ramsey's theorem, there is an infinite homogeneous subset $H\subseteq \Omega$. If all pairs are colored red, then the map $a_n\mapsto n$ embeds $H$ in $\mathbb{N}$, and every infinite subset of $\mathbb{N}$ is order-isomorphic to $\mathbb{N}$. Similarly, if all the pairs are colored blue, then $H$ embeds in $\mathbb{N}^*$.

I believe your original question, before the edit, was:

Is there a countably infinite linear order $(\Omega,\leq)$ which is not isomorphic to any of its proper suborders?

This is a much more interesting question, and the answer can be found here: https://mathoverflow.net/questions/131933/is-it-possible-to-construct-an-infinite-subset-of-bbb-r-that-is-not-order-iso

The paper of Dushnik and Miller linked in the answer by François G. Dorais proves:

  1. Every countably infinite linear order is isomorphic to a proper suborder.

  2. There is a suborder $\Omega\subseteq \mathbb{R}$ of cardinality $2^{\aleph_0}$ such that $\Omega$ is not isomorphic to any proper suborder.

Alex Kruckman
  • 76,357
  • @ AlexKruckman : indeed, I would still be interested in answers to my initial question as well ! – Boccherini Dec 11 '18 at 14:48
  • 1
    @Boccherini Done! – Alex Kruckman Dec 11 '18 at 14:49
  • An equally simple proof, without using Ramsey's theorem, of the fact that an infinite linear order contains a strictly monotonic infinite sequence: The set of elements having only finitely many predecessors is either finite (Case 1) or infinite (Case2). In Case 1 there is a strictly decreasing infinite sequence, in Case 2 a strictly increasing infinite sequence. – bof Dec 11 '18 at 16:50