6
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Dec 28, 2021 at 2:45
  • 3
    $\begingroup$ Isn't your $\ S'\ $ just order-equivalent to the first uncountable ordinal ? $\endgroup$ Commented Dec 28, 2021 at 2:47
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Dec 28, 2021 at 4:14

2 Answers 2

10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .