What's wrong with the naive "take successive smallest" procedure in proving well-ordered subsets of $\mathbb R$ are countable?

Question

For context, I have no set theory background and my understanding of sets is naive. I had a discussion with a friend that I thought for any well-ordered subset of the reals, I could simply take the least element, second least, etc. to show it is countable. It is the same procedure described in Is a well-ordered subset of $(\mathbb{R},<)$ countable?. However he told me I had to make use of ordinals (which I don't know about) to index into the set. Is there an intuitive (or at least relatively elementary) reason why I can't count up using my naive procedure to conclude the subset is countable? The main concern I see is about if I ever "finish counting" which I don't know how to reason about and seems subtle.

Answer 1

Given any infinite well-ordered set $X$, you can define an injection $f:\mathbb{N}\to X$ by repeatedly taking the least remaining element as you describe. To be precise, you can recursively define $f(n)$ to be the least element of $X\setminus\{f(m):m<n\}$.

However, this map may not be surjective, and so it may not show that $X$ is countable. For a very simple example, consider $X=\{1\}\cup\{1-1/n:n\in\mathbb{Z}_+\}\subset\mathbb{R}$. This is well-ordered with the usual ordering inherited from $\mathbb{R}$. The least element is $1/2$, then the second least element is $2/3$, then the third least element is $3/4$, and so on. However, repeatedly taking least elements like this does not exhaust all of $X$: the map $f:\mathbb{N}\to X$ hits each element of the form $1-1/n$ but does not hit $1$, so it fails to be surjective.

Answer 2

Suppose $S \subseteq \mathbb{R}$ is well-ordered under $<$.

We must show that $S$ is countable.

Suppose on the contrary that $S$ is not countable. Consider $K = \{x \in \mathbb{R} \mid \{s \in S \mid s < x\}$ is uncountable$\}$.

Now $K$ must be non-empty. For suppose that $K$ were empty. Then note that $S = \bigcup\limits_{n \in \mathbb{N}} \{s \in S \mid s < n\}$ is the countable union of countable sets, hence countable.

So $K$ is non-empty. And consider the fact that $S$ has a least element $s_0 \in S$, since $S$ is not countable and hence nonempty. Then we see that $s_0$ is a lower bound of $K$, since if $z \leq s_0$ and $z \in K$, then we must have $\{s \in S \mid s < z\} = \emptyset$ and hence $z \notin K$.

Since $K$ is a non-empty set with a lower bound, it must have a greatest lower bound $B$. We see that $\{s \in S \mid s < B\}$ must be countable, since it can be written as $\bigcup\limits_{n \in \mathbb{N}_+} \{s \in S \mid s < B - 1/n\}$, which is the countable union of countable sets. By contrast, since $K$ is nonempty, there must be some $k \in K$, and for this $k$, we must have $\{s \in S \mid s < k\}$ is uncountable. So there must be some $s \in S$ such that $B < s$.

Then consider $\{s \in S \mid s > B\}$, a nonempty set. It has a minimal element $s_1 > B$. But in that case, we have $\{s \in S \mid s < s_1\} = \{s \in S \mid s < B\}$ is countable. And $s > B$. This leads to a contradiction.