Re: Cantor's Diagonal

From: Daniel Grubbs <dangrubbs.domain.name.hidden>
Date: Sun, 16 Dec 2007 22:09:15 -0500
Hi Barry,

Let me see if I am clear about Cantor's  method.  Given a set S, and some enumeration of that set (i.e., a no one-one onto map from Z^+ to S) we can use the diagonalization  method to find an D which is a valid element of S but is different from any particular indexed element in the enumeration.

Cantor's argument then goes on to say (and here is where I disagree with it) that therefore D is not included in the enumeration and the enumeration is incomplete.

I, on the other hand, would posit that the enumeration may include elements whose index is not well defined. For example, 1 or 4 in  my second example.  They were in the enumeration prior to its being shuffled, and always had a definite position during the process.  They must still be in there, with definite positions, despite the fact that their indices are now infinite and ill-defined.

If the diagonalization process does not produce the proffered result in this case (i,e., it does not prove that the element D is not included in the enumeration) then it does not prove it in any case.  The number D found with this method may actually be in the enumeration, but with an ill-defined index.

Dan

Barry Brent wrote:
Hi.

Bruno could do this better, but I like the practice.

I guess you're trying to demonstrate that the form of Cantor's  
argument is invalid, by displaying an example in which it produces an  
absurd result.

Start with a set S you want to show is not enumerable.  (ie, there is  
no one-one onto map from Z^+ to S).  The form of the diagonalization  
argument is as follows: give me any, repeat, any, particular  
candidate for an enumeration of S.   This should be a map from Z^+  
into S.  (If it isn't such a map, it isn't an enumeration.)   I will  
show you an element D of S that your candidate enumeration omits.   
(That is, I will show you that your candidate is not onto.)  Hence, S  
is not denumerable.

In your first attempt, your D is not an element of your S (= Z^+).   
So your first attempt doesn't fit the form of the diagonalization  
argument on this account.  More fundamentally, it also fails to fit  
the form of Cantor's argument because you haven't tried to debunk  
*any* candidate enumeration, but a particular one.

In your second attempt, if I understand you, you start with a map  
from the primes (all of them!) and then (your work suggests, but I  
think you'd need more details--what's the image of 4, for example?)  
from the rest of Z^+, into S = Z^+ again.   This example doesn't  
invalidate Cantor's argument either.  Again, you debunk a particular  
candidate enumeration, not any and all candidate enumerations.  So  
you don't arrive at the absurdity you seem to be after, even if you  
fill in the details I mentioned.

Barry

On Dec 16, 2007, at 3:49 AM, Daniel Grubbs wrote:

  
Hi Folks,

I joined this list a while ago but I haven't really kept up.   
Anyway, I saw the reference to Cantor's Diagonal and thought  
perhaps someone could help me.

Consider the set of positive integers: {1,2,3,...}, but rather than  
write them in this standard notation we'll use what I'll call  
'prime notation'.  Here, the number m may be written as
m = n1,n2,n3,n4,...
where ni is the number of times the i'th prime number is a factor  
of m. Thus:
1 = 0,0,0,0,0,...
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
4 = 2,0,0,0,0,...
5 = 0,0,1,0,0,...
...
28 = 2,0,0,1,0,0,0,...
...
If we now apply the diagonal method to this ordered set, we get the  
number:
D = 1,1,1,1,1,...
Has this just shown that the set of positive integers is not  
denumerable?

I can see that one may complain that D is clearly infinite and  
therefore should not be in the set, but consider the following...

Let's take the original set and reorder it by exchanging the places  
of the i'th prime number with that of the number in the i'th  
position.  (i.e. First switch the number 2 with the number 1 to  
move it to the first position. Then switch 3 with the number -- now  
1 -- in the 2nd position. Then 5 with the 1 which is now in the 3rd  
position. Etc...) Because we are just trading the positions of the  
numbers, all the same numbers will be in the set afterwards.

The set is now:
2  = 1,0,0,0,0,...
3  = 0,1,0,0,0,...
5  = 0,0,1,0,0,...
7  = 0,0,0,1,0,...
11= 0,0,0,0,1,...
...
Now instead of adding 1 to each 'digit' of the diagonal, subtract  
1.  This will ensure that the diagonal number is different from  
each of the numbers in the set. Thus,
D = 0,0,0,0,...
But this is the number 1 which we know was in the set to begin  
with.  What happened to it?

I would suggest that the diagonal method does not find a number  
which is different from all the members of a set, but rather finds  
a number which is infinitely far out in the ordered set.

If anyone can find where I've gone wrong, please let me know.

Dan Grubbs

    

Dr. Barry Brent
barrybrent@earthlink.net
http://home.earthlink.net/~barryb0/






  


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

Received on Sun Dec 16 2007 - 22:09:29 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:14 PST