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?

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

1 Answer 1


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.

  • $\begingroup$ I take it in this definition, the enumeration cannot cross $\omega$? $\endgroup$ Jul 14, 2020 at 22:02
  • 2
    $\begingroup$ When you count $1,2,3,\ldots$, do you ever reach $\omega$? $\endgroup$ Jul 14, 2020 at 22:03
  • $\begingroup$ Haha! Quite... I see your point. $\endgroup$ Jul 14, 2020 at 22:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – plop
    Jul 14, 2020 at 22:27
  • $\begingroup$ @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. $\endgroup$ Jul 14, 2020 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.