[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 => 

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