# Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers?

A few minutes ago I asked a question about a "proof" that $$\mathbb{R}$$ is enumerable that crossed my mind: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

I was told to look into ordinal numbers, and that after crossing $$\omega$$ we stop considering something to be an enumeration.

Why is this the case? Are there negative consequences if we don't put this limitation?

Edit: I always thought of $$\mathbb{N}$$ as the "counting numbers" - but... when we cross over to ordinals like $$\omega$$, $$\omega+1$$, etc, aren't we still effectively counting?

• It is just a definition. Nothing negative or positive. Just a name to put things into categories.
– plop
Jul 14 '20 at 21:45
• @plop Thank you - so what would we call an algorithm that goes through a well-ordered set that has an ordinal beyond $w$? Jul 14 '20 at 21:48
• See hypercomputation.
– plop
Jul 14 '20 at 21:52
• Assuming the axiom of choice, every set can be well-ordered, so the concept of enumerability becomes empty. Jul 14 '20 at 21:56
• It is a classical theorem in set theory that the axiom of choice is equivalent to the well-ordering principle. Jul 14 '20 at 22:00

A set $$S$$ is enumerable (or, countable) if we can enumerate it: $$S = \{s_1,s_2,s_3,\ldots\}$$ In other words, there is a mapping from $$\mathbb{N}$$ onto $$S$$.

Cantor showed that $$\mathbb{R}$$ isn't enumerable.

We can consider more relaxed notions of enumeration. For example, a set $$S$$ is well-orderable if there is a linear order $$<$$ on $$S$$ such that any non-empty subset of $$S$$ has a minimum. This encompasses your examples, and much more.

The axiom of choice is equivalent to the well-ordering principle, which states that every set can be well-ordered. Hence if you assume the axiom of choice, every set can be enumerated in this sense.

• I take it in this definition, the enumeration cannot cross $\omega$? Jul 14 '20 at 22:02
• When you count $1,2,3,\ldots$, do you ever reach $\omega$? Jul 14 '20 at 22:03
• Haha! Quite... I see your point. Jul 14 '20 at 22:04
• @Novicegrammer But when you well-order $\mathbb{R}$ you do cross $\omega_0$ and $\omega_0+1$ and $2\omega_0$, and $\omega_0^{\omega_0}$, ... Assuming the continuum hypothesis you won't need to cross $\omega_1$, but if not, then you may have to cross even more ordinals.
– plop
Jul 14 '20 at 22:27
• @plop Oh thanks, I've been introduced to yet another hypothesis. ...I'll throw this somewhere in the backlog of stuff I have to read. Jul 14 '20 at 23:48