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 '20 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$ – Novicegrammer Jul 14 '20 at 21:48
  • $\begingroup$ See hypercomputation. $\endgroup$ – plop Jul 14 '20 at 21:52
  • 2
    $\begingroup$ Assuming the axiom of choice, every set can be well-ordered, so the concept of enumerability becomes empty. $\endgroup$ – Yuval Filmus Jul 14 '20 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$ – Yuval Filmus 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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