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