[FOM] Cantor's argument

[Andrej Bauer]

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:

  Definition:
  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

  Definition:
  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
http://andrej.com

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