What subsets of $\mathbb{R}$ can be ordered?

165 Views Asked by At

Correcting my question.

Is there a necessary and sufficient condition on a set $S \subset \mathbb{R}$ such that $S = \{s_1, s_2, ....\}$ where $s_{k} < s_{k+1}$?


I have had this question pop up in my mind often lately.

Suppose I'm given a subset $S \subset \mathbb{N}$. $S$ is countable and contains its infimum. If I'm asked to generate an ordered sequence $(x_1, x_2, ..)$ of $S$ that contains all the elements of $S$, I would be a able to. I would start with $x_1 = \inf(S)$ then $x_k = \inf (S - \{x_1, x_2, ... x_{k-1}\})$. Hence $x_1 < x_2 < x_3 ..$ . So far so good.

Now I'm given $\mathbb{Q_+} = \{x\in \mathbb{Q} | x \ge 0\}$ and asked to order it. Well, it is countable, so there is hope. It contains its infimum, so I can at least define $x_1$. But I get into problems, since $\inf (\mathbb{Q_+} - \{0\}) = 0$, I'm forced to set $x_2 = 0$ and I end up with $(0,0,.....) \neq \mathbb{Q_+}$.

It is quite clear to me that $\mathbb{Q_+}$ can not be ordered (by my definition). My question is, what is the property of a subset of $\mathbb{R}$ that guarantees (or ideally, equivalent) for it be ordered in a sequence? Clearly it being countable is not enough. Finite is too strong of a restriction.

The only requirement I can think of is:

Let $S \subset \mathbb{R}$. If for any finite collection $F = \{s_1, s_2, .., s_n\} \subset S$, we have that $S - F$ contains its infimum, then $S$ can be ordered in a sequence.

Am I in the right direction? Does this property have a name? Is it an equivalent property? Share with me !

1

There are 1 best solutions below

2
On BEST ANSWER

Let's try to make your request more rigorous:

For which subsets $S\subseteq \mathbb{R}$ there exists a bijection $$b:\mathbb{N}\to S$$ that preserves order?

For simplicity I'll call such subsets "sequencable". I want to show you that:

A subset $S$ is sequencable iff it's infinite, well ordered and has no limit points (or its only limit point is its supremum and in this case the supremum must NOT belong to $S$).

It's pretty clear that a sequencable subset is infinite and it's well ordered because $b$ is an order preserving bijection. Moreover let's suppose by contradiction $S$ had a limit point $L$ different from its superior.

(Technically we should also consider the case in which the only limit point is the supremum but it also belongs to $S$. But this would mean that $S$ has maximum, which is a contradiction since $\mathbb{N}$ doesn't.)

If there's an element $s_1\in S$ such that $s_1<L$ then there is a sequence $(s_n)_{n\in \mathbb{N}}$: $$s_1<s_2<s_3<\cdots<L.$$ Moreover since $L$ is not the upper bound, there is an $s\in S$ such that: $$s_1<s_2<s_3<\cdots<L<s$$ So we have infinite elements of $S$ between two given elements of $S$ (that are $s_1$ and $s$). This can't happen in $\mathbb{N}$ and such a property must be preserved by order preserving bijections. This is a contradiction.

If there's not an element $s_1<L$ then $L$ is clearly the infimum of $S$. But the infimum is the minimum because $S$ is well ordered. Since $L$ is a limit point of $S$, there must be a sequence: $$L<\cdots<s_3<s_2<s_1.$$ And we are again in the situation of the first case.

Viceversa, we would like to define recursively: $$\begin{cases}x_1=\min(S) \\ x_{n+1}=\min(S-\{x_1,\ldots,x_n\})\end{cases}$$ This recursion is clearly well posed because $S$ is well ordered and infinite. Now we can define our bijection: $$b:\mathbb{N}\to S,\quad n\mapsto x_n.$$ This map is clearly order preserving and injective. We just need to prove that it's surjective. By contradiction let's suppose there's an element $s\in S$ such that $s\neq x_n$ for all $n\in \mathbb{N}$.

Notice that $s>x_n$ for all $n\in \mathbb{N}$, because if there was an $m\in \mathbb{N}$ such that $s<x_m$ then $$s<\min(S-\{x_1,\ldots,x_{m-1}\}),\ \ s\in S-\{x_1,\ldots,x_{m-1}\}, $$ which is a contradiction.

Since $s$ upper bounds $(x_n)_{n\in \mathbb{N}}$, then the family $(x_n)_{n\in \mathbb{N}}$ is bounded and by Bolzano-Weierstrass it admits a limit point $L$. Since the only (eventual) limit point of $S$ is its supremum (so $s<L$, notice that the disequality is strict because $S$ doesn't contain $L$ by hyphotesis). This implies that $L$ is at the same time a limit point and an upper bound of $(x_n)_{n\in\mathbb{N}}$, so: $$L=\sup_{n\in\mathbb{N}}(x_n)$$ But this is a contradiction because $(x_n)_{n\in\mathbb{N}}<s<L$.

The proof is now complete.