[FOM] Cantor's argument

Andrej Bauer Andrej.Bauer at andrej.com
Mon Feb 3 05:10:51 EST 2003

Since somebody has to respond, and I might have more time than all
of those cc-ed on Zenkin's messages, I will allow myself to do so:

"Alexander Zenkin" <alexzen at com2com.ru> writes:
> 	W.Hodges believes that only such indexing of reals in (C) are
> admissible which use ALL natural numbers of the set N={1,2,3, . . .},
> since only such indexing allows "to reach Cantor's conclusion", but any
> re-indexings of the reals in (C) which use NOT ALL natural numbers are
> inadmissible since they lead to conclusions contradicting to Cantor's
> one. Unfortunately, he did not formulate a mathematical or logical
> criterion to make such a differentiation.

Alexander Zenkins claims, if I understand him correctly:

  Cantor's argument shows there is no surjection from the set of natural
  numbers N = {1, 2, 3, ...} onto the real numbers R. From this we may
  _not_ conclude that there does not exist some other countable set C
  such that there is a surjection from C onto R.

We may conclude precisely that.

Perhaps there is a misunderstanding as to the word "countable".
The concept "countable set" is _defined_ as follows:

  A set C is _countable_ if there is a surjection from N onto C.

Now what Alexander Zenkin seems not to have noticed is the following
rather trivial observation:

  If there is a surjection from a countable set C onto the real
  numbers R, then there is a surjection from N onto R.

  Proof: compose the surjections N --> C and C --> R.

So, as a trivial corollary of Cantor's Theorem we get:

  There is no surjection from a countable set C onto the real
  numbers R.

In other words:

  The set of real numbers is not countable.

Anticipating Zenkin's reply, let me suggest to him that he should
prove the following Lemma before writing the reply:

  Lemma: every non-empty subset of natural numbers N is countable.

Therefore, nothing is gained by defining "countable set" as

  A set C is _countable_ if there is a surjection from an
  infinite subset of N onto C.

You may try to define "countable" in some other way, but rest assured
that it won't help.

Remark: In intuitionistic logic a set X such that there is a
surjection from a subset of N onto X is sometimes called
"subcountable". In intuitionistic logic it _cannot_ be proved that the
set of reals R is not subcountable (because it is subcountable in the
effective topos?). Alas, we're working in classical logic here.

I hope this closes the discussion.

Andrej Bauer
University in Ljubljana

P.S. What Giuseppina Ronzitti says about the intuitionstic version of
     Cantor's argument seems wrong to me.

More information about the FOM mailing list