# [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
> 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.
```