[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:
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.
More information about the FOM
mailing list