[FOM] Re: Which Part of Cantor Needs Infinity?

Andrew Boucher Helene.Boucher at wanadoo.fr
Mon Jan 12 00:33:05 EST 2004

> 	AZ's response:
> 	Cantor's Theorem states that the continuum is uncountable.
> 	If ,according to Andrew Boucher, "Cantor's Theorem does not depend on 
> the
> notion of infinity at all" then the continuum (as well as all its 
> subsets,
> e.g., N, Q, etc. ) must be finite.

Not "must be", but "could be".   Not making the assumption that the 
natural numbers continue ad infinitum is not the same as making the 
contrary assumption (that there is a maximum natural number).    One is 
being agnostic about the two cases (ad infinitum or max).

> 	However, I have no reason to doubt of W.Hodges' meta-mathematical
> professionalism and his high BSL-reputation, and agree with his 
> statement
> that "the PROOF of Cantor's theorem (on the uncountability of the real 
> line)
> depends on acceptance of actual infinity"

Well you have the advantage over me here because you haven't given the 
source of Hodges' quote.  I don't, for instance, find  it in "An Editor 
Recalls Some Hopeless Papers," (BSL, Vol 4, No 1, March 1998).  In any 
case, while I would prefer not to disagree with such an eminent 
logician, the exegetical point would not change my position.

> 	By the way, there are two independent definitions of the notion of 
> infinity
> sets:
> 	1) Aristotle-Peano's definition: a sequence, say, {1,2,3, . . .} is
> infinite iff it has not a maximal (last) element.
> 	(see A.A.Zenkin, As to strict definitions of potential and actual
> infinities. - [FOM]-Archive at:
> http://www.cs.nyu.edu/pipermail/fom/2002-December/006121.html
> http://www.cs.nyu.edu/pipermail/fom/2003-January/006137.html)
> 	2) Cantor's (and modern set theoretical) definition: a set is 
> infinite iff
> it's equivalent to its proper subset.
> 	Now if we shall look carefully at the traditional Cantor's diagonal 
> of the uncountability of continuum (here X=[0,1]), we shall reveal (i) 
> that
> the PROOF uses only the Definition-1 in the two places: "assume that 
> there
> is a list, x1,x2,x3, . . . ('ad infinitum'), of all reals from X" and 
> "any
> real 'a' from X is an infinite sequence of 0s and 1s, i.e., a=0.a1a2a3 
> . . .
> ('ad infinitum')",
> and (ii) that the traditional Cantor's diagonal PROOF
> which is an only (!) tool to prove the uncountability of infinite set 
> X uses
> nowhere the basic set-theoretical Definition-2 of just the INFINITE 
> sets.
> 	It is a quite strange peculiarity of Cantor's PROOF and a good reason 
> to
> make deep deductive conclusions as to what will happen if  to use 
> really the
> set-theoretical Definition 2 within the framewrok of Cantor's diagonal
> PROOF. It should be emphasized that such usage of the Definition 2 in
> Cantor's PROOF doesn't break any law of any (even meta-mathematical) 
> logic.

Perhaps we are talking at cross-purposes, but what I am talking about 
is Cantor's Proof (the traditional diagonal argument) of Cantor's 
Theorem (that there is no 1-1 correspondence between N and R).    
Cantor's Theorem doesn't mention "infinite" at all, and my point is 
that Cantor's Proof doesn't need it either - one can carry out the 
proof without making any use of the word or concept "infinite," 
explicitly or implicitly, and so clearly not making any assumption 
about which infinity one is talking about (Definition-1 or 

Cantor's Proof says:  suppose there is a correspondence f between N and 
R.  Consider the (-n)-th digit of f(n) and change it.  This defines a 
real which is not in the image of f.  There is no reference to N 
continuing ad infinitum (or that N is not equivalent to a proper 
subset).  The Proof goes through regardless.

Consider it this way.  Case I.  Suppose ad infinitum holds.  Then 
Cantor's Proof goes through.  Case II.  Suppose there is a maximum 
integer.  For the sake of argument suppose this maximum integer is 3.  
Suppose there is a 1-1 correspondence from N = {0,1,2,3} to R.   So R = 
{f(0),f(1),f(2),f(3)}.  Now elements of R consist of numbers of the 
form x0.x1x2x3 (since R is defined to be functions r between N and N 
where r(i) = 0 or 1 if i > 0).    So R = {x00.x01x02x03, x10.x11x12x13, 
x20x21x22x23, x30x31x32x33}.    There exists xii' not equal to xii, for 
i = 0,1,2,3, in fact with xii' = 0 or 1.  Define r(i) = xii'.  Then r 
is, by definition, a real number, but it also is not on "the list".

Here I have broken up the proof into cases for clarity's sake, but one 
can structure the proof so it is case-less and no mention is made of 
"ad infinitum" (as is done very briefly in the paragraph before the 
last).  In any case, clearly if a proof works in both case A and (not 
A), then there is no logical dependence of the proof on A.

Again, there is a part of Cantor's theory which depends on N being 
infinite (in the sense of continuing on ad infinitum).  But this part 
is where he proves that N is in 1-1 correspondence with Q (or even N is 
in 1-1 correspondence with the even numbers).   If there is a maximum 
integer, then *these* are the theorems which are not true.

Best regards,
Andrew Boucher

More information about the FOM mailing list