# Strange property of Well-Ordering on an Uncountable Set

### Background

I was messing around with well-orderings of uncountable sets, and proved the following theorem. It seems a little strange to me, and I am curious if anyone here has encountered something similar or could offer some explinations/intuition.

### Theorem

Any well-ordering $$<$$ on an uncountable set $$S$$ has an uncountable subset $$S' \subset S$$ such that for all $$s \in S'$$, the set $$\{s' \in S' : s' < s\}$$ is countable.

### Proof

Suppose that for all uncountable sets $$S$$, there exists $$S_1,S_2\subset S$$ such that

• $$S_1$$ is uncountable, and $$S_2$$ is non-empty
• $$\forall (s_1,s_2) \in S_1\times S_2$$, $$\ s_1 < s_2$$.

Then, we can construct the following sequence

• Break $$S$$ into $$S_1,S_2\subset S$$, following our assumption. E_0 := S_2
• Break $$S\setminus (\cup_{k=0}^{n-1}E_k)$$ into $$S_1,S_2$$ following our assumption. $$E_n := S_2$$.

Now, by the axiom of choice, we construct an infinite set $$E$$ by selecting exactly one element from each of $$\{E_k\}_{k=1}^\infty$$. Suppose this set has some least element $$e$$. Since $$e \in E$$, there exists $$n \in \mathbb{N}$$ such that $$e \in E_n$$. But there exists an element in $$E_{n+1}\subset E$$, which is by definition less than $$e$$.

Absurd.

So we will eventually reach an uncountable subset of $$S$$ for which our assumption is false. Redefine $$S$$ to be this set. We will observe some properties of this set.

First define $$H_s := \{s' \in S : s' < s\}$$ for all $$s \in S$$. I will show that

$$A := \{s \in S : H_s\ \text{countable}\} = S$$

Clearly $$A \subset S$$. Now suppose that for some $$s \in S$$, $$s \not\in A$$ so $$H_s$$ is not countable. Since $$S$$ does not follow our initial assumption, $$H_s < H_s^c$$, $$H_s^c = \emptyset$$, and so $$H_s = S$$. But $$s \not\in H_s = S$$ and we arrive at a contradiction. So, $$H_s$$ is countable, and so $$s \in A$$. Thus $$S\subset A \Rightarrow S = A$$.

This concludes our proof. We have found a subset with the desired property. QED

### Questions

This is a little strange; $$\{H_s : s \in S\}$$ is an uncountable collection of strictly assending countable sets. Shouldnt this contradict with strictly assending countable sets? Maybe this gives some insight into there existing no infinity between countable and uncountable -- the idea being there is some jump from countable to uncountable?

Since $$\mathbb{R}$$ embeds into any uncountable set, we also get some insight into one of the well orderings on $$\mathbb{R}$$. If we find an uncountable collection of assending countable sets which cover any uncountable set, with some work, this should reveal an explicit well ordering on $$\mathbb{R}$$. Cool!

Have any of you encountered a similar set before? Is there any clarification you could offer as to the ideas behind this set, and how such a set is possible? Are there any explicit examples of such a set?

• Possibly worth noting, though not answering your questions: there's a simpler proof of this fact. Let $B$ be the set of $s\in S$ such that $\{s' \in S : s' < s\}$ is uncountable. Either $B$ is empty (in which case your property holds with $S'=S$) or, by well-ordering, it has a minimal element $b\in B$. If we let $S'=\{s' \in S : s' < b\}$, then $S'\cap B$ is empty by minimality of $b$ and $S'$ is uncountable by definition of $B$, hence $S'$ satisfies your condition. Commented Dec 28, 2021 at 2:45
• Isn't your $\ S'\$ just order-equivalent to the first uncountable ordinal ? Commented Dec 28, 2021 at 2:47
• I'm not sure why this wasn't addressed in the answers, but unfortunately, your second to last paragraph will not work. "$\mathbb R$ embeds into any uncountable set" (I'm assuming you just mean there is an injective function from $\mathbb R$ into any uncountable set) is equivalent to the continuum hypothesis, which is undecidable over ZFC. And even granting that, it would do little to give us an explicit well-ordering unless this injection you have in mind were also explicit. It is consistent with ZFC that there is no definable well-ordering of the reals, and also consistent that there is one. Commented Dec 28, 2021 at 4:14

Any infinite well-order $$S$$ has an infinite set of elements with finitely many predecessors.
Basically, $$\omega$$ is an infinite well-ordering in which each element is finite. In general, for any cardinal $$\kappa$$, every well-ordering $$W$$ of cardinality $$\ge\kappa$$ will have an initial segment $$\hat{W}$$ isomorphic to $$\kappa$$, and every element of this $$\hat{W}$$ will have $$<\kappa$$-many predecessors (since $$\kappa$$ is a cardinal).
Any well ordering of an uncountable set has an initial segment order-isomorphic to $$\omega_1$$. There are uncountably many elements of $$\omega_1$$, but each of those elements has the property that it is greater than only countably many elements.
In other words, $$\omega_1$$ is the set of all countable ordinals.