# [FOM] Which Part of Cantor Needs Infinity?

Andrew Boucher Helene.Boucher at wanadoo.fr
Sun Jan 11 01:52:19 EST 2004

```On Jan 9, 2004, at 21:35, Alexander Zenkin wrote:
>
>
> 	Solomon Feferman writes in one place, "The ideas of potential vs.
> actual
> infinity are vague but at the intuitive, philosophical level very
> suggestive."
> 	Wilfried Hodges writes in one place: " . . .the author observes quite
> correctly that the PROOF of Cantor's theorem (on the uncountability of
> the
> real line) depends on acceptance of actual infinity."
>
> 	How is it possible that not simply mathematical theorem (Cantor's
> theorem
> on the uncountability of continuum), not "the intuitive meaning of the
> theorem", but its MATHEMATICAL PROOF may depend on an acceptance of the
> "vague, intuitive, philosophical" notion of "actual infinity" "what is
> <certainly> not a mathematical theorem or axiom"?
>
> 	Alexander Zenkin

In a concrete sense Cantor's Theorem does not depend on the notion of
infinity at all.

Apologies for putting it in the following framework, but it it is the
system with which I am most familiar.  Consider (third-order) PA minus
the ad infinitum assumption that there is always a next number, that is
with the following axioms:

(F1)  Uniqueness of numbering
(n)(m)(P) (Mn,P & Mm,P => n = m)

(F2)  Zero
(P) (M0,P <=> (x) ! Px)

(F3)  Successoring
(P)(Q)(a)(n)(m) ( Nn & Sn,m & ! Pa &  (x)(Qx <=> Px V x = a) => (Mm,Q
<=> Mn,P))

(F4)  Induction
From phi(0) and (n)(m) (Nn & Sn,m & phi(n) => phi(m)), infer (n)(Nn =>
phi(n))

where:
Nn means "n is a finite number"
Sn,m means "m is a successor of n"
Mn,P means "P numbers n"
! = "not"

Then models of this system are not only the natural numbers but also
the (finite) initial segments of the natural numbers.

Define a real number f to be a (second-order) functional relationship
from N to N, where f(i) is 0 or 1 if i > 0.  That is, f(0) can be
considered the integral part of the real number, and f(1)f(2)f(3)...
its binary expansion.   Actually this is only the non-negative reals,
and one also has to worry about an expansion of infinitely repeating 1s
- but these technical matters are easily rectified.  Notice that of
course infinity is not pre-supposed or needed in the definition.  For
instance, if N is the initial segment {0,1,2}, then the real numbers
are the (third-order) set R corresponding to all numbers of the form
{n + i/2 + j/4 + k/8 : n = 0,1, or 2 and i,j,k = 0 or 1}.
N can of course be embedded in R, and one can ask whether there is a
1-1 correspondence from N onto R.  The answer is "no", and one can use
Cantor's proof to show it using only axioms (F1), (F2), (F3), and (F4).
Ad infinitum is not needed.

So R is uncountable even if it is, from the "outside", finite - an
extension, as it were, of Skolemization.

While Cantor's theorem goes through even if there is a maximum number
(i.e. the contrary of the ad infinitum case), the Cantorian universe is
not unchanged - but it's the proof that the rationals are in 1-1
correspondence with the naturals which falls down.  Define the
rationals Q in the natural way, where an element of R is rational if,
when multiplied by a non-zero natural number, a natural number results.
Not all reals are rationals.  For instance, if N is the initial
segment {0,1,2}, then  the rationals correspond to the set {n + i/2 : n
= 0,1, or 2 and i = 0 or 1}, which is a proper set of the reals.  N can
be embedded in Q, but there is no 1-1 correspondence from N to Q.

In brief, the part of Cantor which needs infinity is not Cantor's
Theorem, but the usually uncontroversial theorem that Q can be put into
1-1 correspondence with N.

```

More information about the FOM mailing list