Strange property of Well-Ordering on an Uncountable Set

order-theoryset-theorywell-orders

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?

Best Answer

There's nothing mysterious about this at all. Think of the following simpler case, where "finite" and "infinite" take the roles above held by "countable" and "uncountable" respectively:

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).

Related Question