Author |
Topic: Denumerability Dilemma (Read 2993 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Denumerability Dilemma
« on: Sep 7th, 2003, 11:59am » |
 Quote  Modify
|
It will probably not surprise some members here to know that I have issues with transfinite set theory, in particular, the notion of denumerability.
In case this is unfamiliar, here's a brief introduction to the black art...
A transfinite theorist says that a set of numbers is denumerable if there exists a one-to-one mapping with the set of natural numbers; they would even go as far as saying that the set is countable.
The typical example cited is the set of even numbers.
1[to]2, 2[to]4, 3[to]6, ... , n[to]2n
Hence there are infinitely many even numbers as there are natural numbers.
We can use a two-dimensional array to form a grid of ordered pairs:
(1,1) (2,1) (3,1) (4,1) ...
(1,2) (2,2) (3,2) (4,2) ...
(1,3) (2,3) (3,3) (4,3) ...
(1,4) (2,4) (3,4) (4,4) ...
and so on.
By taking the ratio of any pair (p,q), we can form a rational number, p/q. As the array extends to infinity, every rational number is contained and can be expressed from the grid.
By taking pairs off in a diagonal snaking pattern, we obtain the following sequence:
(1,1) (2,1) (1,2) (1,3) (2,2) (3,1) (4,1) (3,2) (2,3) (1,4) ...
Converting these to rational numbers and removing repeats, we get the following one-to-one mapping:
1[to]1, 2[to]2, 3[to]1/2, 4[to]1/3, 5[to]3, 6[to]4, 7[to]3/2, ...
Hence the rational numbers are denumerable.
The final assault in an introductory course to the transfinite is the demonstration that the set of real numbers are NOT denumerable. This is usually demonstrated in the following way...
Without loss of generaility, we shall consider the real numbers on the continuum over the interval 0 and 1. Imagine we have a complete list of the decimal numbers in this interval and suppose that this is the top of the unordered infinite set we have obtained:
0.32150136...
0.54314772...
0.75325180...
et cetera
We will now write-down a number in the following way. The 1st digit will be different from the 1st digit of the 1st number, therefore, even if the other digits match, it will be a different number from the 1st number. Similarly we shall ensure that the 2nd digit of our number is different from the 2nd digit of the 2nd number, and so on.
As this number will be different from every number in the list, which was supposed to be the entire list of real numbers over the interval 0 to 1, we demonstrate that the set of real numbers is not denumerable.
Now we've endured the preamble. Here's part of my objection...
Imagine writing every number from 1 to 999, except we consider the number to be a string and we shall reverse it. By placing this after "0.", we shall form every decimal fraction from 0.001 to 0.999; in other words, every decimal fraction containing 3 decimal places.
If we extend this to infinity, each natural number corresponds, on a one-to-one mapping, with the complete set of decimal fractions, that is, the real numbers:
1[to]0.1, 2[to]0.2, ... , 9[to]0.9, 10[to]0.01, 11[to]0.11, 12[to]0.21, ... , 19[to]0.91, 20[to]0.02, 21[to]0.12, ... , 1432[to]0.2341, ...
Hence the set of real numbers is denumerable.
I've deliberately not said any more at this stage – I've got bucket loads more  – as I'd be very interested to hear thoughts on this first.
|
| « Last Edit: Sep 7th, 2003, 12:02pm by Sir Col » |
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Denumerability Dilemma
« Reply #1 on: Sep 7th, 2003, 12:49pm » |
Quote Modify
|
You are asking for trouble from Icarus.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Denumerability Dilemma
« Reply #2 on: Sep 7th, 2003, 12:53pm » |
Quote Modify
|
even 1/9, a rational number, will never be in that set..
in the natural -> even and natural -> rational case for every even, resp. rational number you can prove there's a natural number (inherently finite) that maps to it.
But you can't find any (finite) number that maps to 1/9 in this supposed natural -> real mapping.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #3 on: Sep 7th, 2003, 1:13pm » |
Quote Modify
|
on Sep 7th, 2003, 12:49pm, SWF wrote:| You are asking for trouble from Icarus. |
|
As I post this, I just noticed from the "who's on-line" that he's prowling, and upon reading this, no doubt, growling! 
My argument, Towr, would be that 1/9=0.111... would not exist in any finite set, but as I said, "If we extend this to infinity..."
Iwe were to argue that 1/9 does not exist in my mapped set, then I would argue that the attempt to denumerate the rationals by spiralling fails too, as you cannot return along a spiral from a position at infinity. In fact, from any position, n, along either axis on an n by n grid, there will remain at least n(n–1)/2 numbers in the grid not accounted for; that is, (n-1)/2n of the grid.
As it happens, I do not accept my previous paragraph anymore than I accept that 1/9 is not in my denumerated list.
|
| « Last Edit: Sep 7th, 2003, 1:22pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Denumerability Dilemma
« Reply #4 on: Sep 7th, 2003, 1:26pm » |
Quote Modify
|
I don't quite know what you mean with 'extend to infinity', unless you actually reach infinity (which isn't a natural number and thus can't be used to map from) you can never get 1/9.
You can however reach any rational number by spiraling. every rational number is mapped to by a finite natural number (which all all finite so it really needn't be specified).
But with reals, in your way you'llonly get an infinite number of digits, as in 1/9, when you reach infinity, but never before not at any finite number.
btw here's a finite set with 1/9 in it. {1/9}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #5 on: Sep 7th, 2003, 1:35pm » |
Quote Modify
|
on Sep 7th, 2003, 1:26pm, towr wrote:Ibtw here's a finite set with 1/9 in it. {1/9}
|
|
Fair point; I meant in my mapped set.
1. How far would you have to go in your spiralling matrix before you got EVERY rational number?
2. Are you suggesting that the other (n–1)/2n of the grid has already been done? You only get just over half of an n by n grid using the spiralling method. The method does not permit you to access the remaining part.
|
| « Last Edit: Sep 7th, 2003, 1:41pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Denumerability Dilemma
« Reply #6 on: Sep 7th, 2003, 1:50pm » |
Quote Modify
|
on Sep 7th, 2003, 1:35pm, Sir Col wrote:| 1. How far would you have to go in your spiralling matrix before you got EVERY rational number? |
|
You can never get every rational number, just like you can't get every natural number.
But you can get _any_ in finite time. That's the point.
Quote:| 2. Are you suggesting that the other (n–1)/2n of the grid has already been done? You only get just over half of an n by n grid using the spiralling method. The method does not permit you to access the remaining part. |
|
The 'grid' you're working in grows, since you expand it diagonally.. You're not actually working with a square, but with a triangle
(1,1)
(1,1) (2,1)
(1,2)
(1,1)(2,1)(3,1)
(1,2)(2,2)
(1,3)
etc
As a result you're not missing out on any part.
Any rational number p/q corresponds with point (p,q) which you reach at the step with natural number (p+q-2)(p+q-1)/2+q
|
| « Last Edit: Sep 7th, 2003, 1:58pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Denumerability Dilemma
« Reply #7 on: Sep 7th, 2003, 2:02pm » |
Quote Modify
|
on Sep 7th, 2003, 1:13pm, Sir Col wrote:| As I post this, I just noticed from the "who's on-line" that he's prowling, and upon reading this, no doubt, growling! |
|
GRRrrRRRrrrRRR! 
Quote:
My argument, Towr, would be that 1/9=0.111... would not exist in any finite set, but as I said, "If we extend this to infinity..."
|
|
And your argument would be wrong! Every time a puzzle touches on the infinite, this same misconception comes up! EVERY NATURAL NUMBER is FINITE! There are an infinite number of them, yes. But they themselves do not include ANY infinite values! Now look back at your sequence definition. You will see that the only way to get infinite decimals out of it is if the index itself has an infinite number of decimals before the decimal point. While you can define such numbers, they are NOT Natural numbers. (They are called 10-adics, and are not actually infinite - the concept of finite vs infinite value is not defined for them.)
With natural numbers you only get a finite number of digits, so the corresponding numbers under your scheme are all terminating decimals. I.e., you are getting a subset of the rationals, just as Towr said, not the entire reals.
Quote:In fact, if we were to argue that 1/9 does not exist in my mapped set, then I would argue that the attempt to denumerate the rationals by spiralling fails too, as you cannot return along a spiral from a position at infinity.
Not only can you not return from a position at infinity, you can never reach one in the first place. But this is immaterial, because you do not need to. All possible pairs (p,q) are reachable before you "get" to any infinite positions.
[quote]From any position, n, along either axis, there will remain at least n(n–1)/2 numbers in the grid not accounted for. |
|
But since n is finite, you are not stopping at n. You are being fooled by trying to apply intuition obtained from finite cases to an infinite situation.
Here is the formula for the index of a pair (p, q) under a different variant of this diagonalization process (It uses the Whole numbers - starting at 0, not 1 - and instead of snaking back and forth, it takes each diagonal in the same direction)
(p, q) [mapsto] ((p+q)(p+q+1)/2) + p
As you can see, every pair has a finite index. A little work shows that any two pairs have different indices, and a bit more work shows that every whole number occurs as an index.
(To get the rationals from this version, you have to throw out not only the pairs that are not relatively prime, but also those with 0 denominators.)
Quote:| As it happens, I do not accept my previous paragraph, anymore than I accept that 1/9 is not in my denumerated list. |
|
I'm glad you don't accept it, but it sounds like the basis of your not accepting it is flawed intuition, just as your argument that 1/9 is in your denumerated list is flawed.
All joking aside, I do not mind people questioning me or the "black arts" upon which I pontificate. As I have said before, honest intellectual debate based on real issues that someone has - whatever their cause, is never a waste of my time. The only things that gets me mad are those who reject without considering, or who feel the need to insult those they disagree with (whether they are right or wrong).
Since you do not fall in either category, feel free to say all you want!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #8 on: Sep 7th, 2003, 3:49pm » |
Quote Modify
|
Good, I'm glad you feel that way. For all the dry wit I use (I hope it's never misunderstood), I only post these questions because I have the deepest of respect for the minds of the regulars at this forum, and value their gentle correcting of my amateur understanding of these concepts.
I would lik to extend my query then...
Suppose then, by the accepted grid method, we have demonstrated the denumerability of the rationals to the set of natural numbers. Clearly, there can be no rational number that exists that is not a member of that set.
Due to the one-to-one mapping I could talk about the nth member of the set, and I could call it member, n. For example, using the grid above, member 4 is 1/3, member 7 is 3/2, et cetera.
I could convert the number, n, into an infinite decimal by placing 0. at the start, reversing the string, and adding an infinite set of trailing zeros after it. For example, member 134 [to] 0.431000...
Clearly each member will be unique, and so there exists a one-to-one mapping between the member number, n, the rational number, and the infinite decimal.
Equally, for every infinite decimal representation there exists a rational number and corresponding natural number.
However, by the diagonal method, the list of decimals is not denumerable, and so there will always be another representation we can produce; therefore the list remains incomplete. Hence the rationals are not denumerable.
Of course, it would be possible to apply the whole argument to the set of natural numbers, using the following mapping:
1[to]0.1000...
2[to]0.2000...
3[to]0.3000...
...
10[to]0.01000...
11[to]0.11000...
...
134[to]0.431000...
and so on.
Hence, by using the diagonal method, it is possible to show that the natural numbers are not denumerable to themselves.
|
| « Last Edit: Sep 7th, 2003, 4:20pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Denumerability Dilemma
« Reply #9 on: Sep 7th, 2003, 10:35pm » |
Quote Modify
|
on Sep 7th, 2003, 3:49pm, Sir Col wrote:
1[to]0.1000...
2[to]0.2000...
3[to]0.3000...
...
10[to]0.01000...
11[to]0.11000...
...
134[to]0.431000...
and so on.
Hence, by using the diagonal method, it is possible to show that the natural numbers are not denumerable to themselves. |
|
I don't there's any point in reversing the digits before appending the zeros, unless I'm missing something ...
A set is denumerable if it can be put in a one-to-one mapping with the naturals. So by definition, the infinite decimals you've written in the quotation above are denumerable!
You may think you've created all the reals with your mapping (and thus you hope to then apply the diagonalization argument), but this is not so. For instance, you have missed 1/9, a decimal consisting of an infinitude of 1s. All decimals in your construction must have a finite number of 1s. Even though the naturals in your mapping are tending to infinity, you must agree that every individual member of the set of naturals has a finite number of 1s. So you'll never get 1/9.
Hopefully I didn't just add to your confusion 
|
| « Last Edit: Sep 7th, 2003, 10:45pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #10 on: Sep 7th, 2003, 11:48pm » |
Quote Modify
|
But, if we write down a decimal in the following way...
Begin by writing "0."
Then write, next to it, any digit that is different to the 1st digit of the 1st number in my list (1).
Then write next to that, any digit that is different to the 2nd digit of the 2nd number in my list.
Continue this process, concatenating digits that are always different to the nth digit of the nth number in the list.
This process is called the diagonal method and, the result of it, is that my new number cannot be the same as any number in my list. As the list was supposed to be complete, I have demonstated that a new number exists, hence it is not denumerable.
|
| « Last Edit: Sep 7th, 2003, 11:51pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Denumerability Dilemma
« Reply #11 on: Sep 8th, 2003, 2:12am » |
Quote Modify
|
on Sep 7th, 2003, 11:48pm, Sir Col wrote:| As the list was supposed to be complete, I have demonstated that a new number exists, hence it is not denumerable. |
|
As I understand it, the idea of diagonalization is:
1) Assume that a set S is denumerable. Then it can be listed out.
2) Construct a new object x by deviating from the digits on the diagonal of the list. Then x cannot in the list, because it is different from every object in the list.
3) Because x satisfies properties which make it a member of S, the list must not have been complete, since the list missed x. Thus S is nondenumerable.
Okay, now let's carefully characterize the set S of infinite decimals you have constructed. All of these strings have the following form: "0.", followed by some finite number of 0-9 digits, followed by an infinite stream of zeroes. Any string of this form must belong in S.
I believe your argument fails on step 3. Yes, you made a new object that differs from every decimal in the list. But this new object doesn't belong in S anyways, so who cares. Unlike all the elements in S, the new object is not suffixed at some finite index by an infinite sequence of zeroes. The list was just supposed to be a complete listing of all elements in S alone. The fact that a listing of members of S lacks objects that are not members of S doesn't say anything about S's denumerability.
Contrast this to applying the diagonalization argument to the reals in [0,1], in which case it's clear that the newly constructed number is a real [in][0,1], and yet the list somehow missed it. Thus the list is incomplete.
P.S. As my posts regularly demonstrate, I'm very fallible, and not great with math. Perhaps Icarus will be breathing fire on the both of us tomorrow  In any case, I encourage and look forward to even the most nitpicky of corrections, in order to learn more from others.
Edit 11:54 PM 9/8/2003: I asked a math PhD I know if this is the right counterargument, and he agrees. So go me.
|
| « Last Edit: Sep 11th, 2003, 8:51am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #12 on: Sep 8th, 2003, 3:22am » |
Quote Modify
|
on Sep 8th, 2003, 2:12am, william wu wrote:| P.S. As my posts regularly demonstrate, I'm very fallible, and not great with math. Perhaps Icarus will be breathing fire on the both of us tomorrow In any case, I encourage and look forward to even the most nitpicky of corrections, in order to learn more from others. |
|
My thoughts entirely; especially the last part. I continue to think it a privilege to be part of this community of great minds in both breadth and depth of experience and knowledge.
What I enjoy most of all about learning mathematics is how clear and unquestionable concepts appear to yourself until someone points out the obvious, and then you can't understand how you ever thought it to be true or missed an idea in the first place.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Denumerability Dilemma
« Reply #13 on: Sep 8th, 2003, 4:55am » |
Quote Modify
|
on Sep 7th, 2003, 3:49pm, Sir Col wrote:
Suppose then, by the accepted grid method, we have demonstrated the denumerability of the rationals to the set of natural numbers. Clearly, there can be no rational number that exists that is not a member of that set.
Due to the one-to-one mapping I could talk about the nth member of the set, and I could call it member, n. For example, using the grid above, member 4 is 1/3, member 7 is 3/2, et cetera.
I could convert the number, n, into an infinite decimal by placing 0. at the start, reversing the string, and adding an infinite set of trailing zeros after it. For example, member 134 [to] 0.431000...
Clearly each member will be unique, and so there exists a one-to-one mapping between the member number, n, the rational number, and the infinite decimal. |
|
Correct (I think).
Quote:| Equally, for every infinite decimal representation there exists a rational number and corresponding natural number. |
|
Here's where it gets a bit shaky, I'd say.
There exists a rational number and corresponding natural number for those infinite decimals that are constructed in the way you stated.
Quote:| However, by the diagonal method, the list of decimals is not denumerable, and so there will always be another representation we can produce; therefore the list remains incomplete. Hence the rationals are not denumerable. |
|
Now you're talking about all decimals (if I didn't misunderstand you), including irrationals like sqrt(2). However, sqrt(2) clearly cannot be constructed by your method, as it is not rational, so it doesn't have a corresponding natural number.
|
| « Last Edit: Sep 8th, 2003, 4:57am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #14 on: Sep 8th, 2003, 8:33am » |
Quote Modify
|
Okay, I'll lay my cards on the table...
My intuition tells me that the diagonal method of showing that something is not denumerable is flawed.
I believe that the continuous selection of different digits does not produce a real quantity. It is maybe analgous with trying to argue that as [sqrt]2 can be expressed as a continuous fraction, it is a rational number.
I would argue that any number that we attempt to produce by the infinite nature of the diagonal method remains undefined, therefore it is not possible to claim to have found a new number not in the list.
I still think that my demonstration of the non-denumerability of the natural numbers holds. The statement is conversely true: (i) each natural number has its own unique decimal representation, and, (ii) each decimal representation is equivalent to a unique natural number. In other words, both sets are complete, and no member of either set exists without a one-to-one mapping. As the diagonal method seems to produce a number that is not in the list, we are faced with my denumerability dilemma. I believe that this can only be justified by arguing that the new number does not exist and cannot ever be fully defined by the process.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Denumerability Dilemma
« Reply #15 on: Sep 8th, 2003, 9:40am » |
Quote Modify
|
on Sep 8th, 2003, 8:33am, Sir Col wrote:
I believe that the continuous selection of different digits does not produce a real quantity. |
|
Are you saying that what we construct using the diagonal method is not a real number?
Quote:| I would argue that any number that we attempt to produce by the infinite nature of the diagonal method remains undefined, therefore it is not possible to claim to have found a new number not in the list. |
|
I would argue that the number we produce is well-defined if we work in base two. Starting with our supposedly complete table of real numbers r(n) (n [in] [bbn]) in [0;1], we define the nth binary digit of x to be xn = 1-r(n)n, where r(n)n is the nth binary digit of r(n).
It can be shown (but maybe you just believe this) that the number thus constructed is in [0;1]. Furthermore, it is a real number, namely
[sum]n=1oo xn 2-n.
However, it differs from every number r(n) in the (supposedly complete) list at the nth binary digit.
Sorry for reiterating the diagonal method, but I don't really see what you take issue with. Is it the infinite process involved in constructing x?
Quote:| (ii) each decimal representation is equivalent to a unique natural number. |
|
So what about my example of [sqrt]2? You didn't give any natural number it corresponds to. Maybe you can't?
|
| « Last Edit: Sep 8th, 2003, 9:45am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #16 on: Sep 8th, 2003, 10:08am » |
Quote Modify
|
I hear what you're saying, but both of my 'methods' were applied to mapping the rational numbers, in the first instance, and the natural numbers to my infinite decimals, so I never suggested that irrational numbers would be included. I believe that my argument, for the natural numbers, proves that the diagonal method is flawed. It remains undefined as it is an infinite process which can never be completed.
|
| « Last Edit: Sep 8th, 2003, 10:10am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Denumerability Dilemma
« Reply #17 on: Sep 8th, 2003, 10:17am » |
Quote Modify
|
on Sep 8th, 2003, 10:08am, Sir Col wrote:| It remains undefined as it is an infinite process which can never be completed. |
|
Hm, why don't you start one step earlier and question the table of reals (or rationals), indexed by natural numbers? As it's infinite, the table will never be completed either.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Denumerability Dilemma
« Reply #18 on: Sep 8th, 2003, 12:27pm » |
Quote Modify
|
on Sep 8th, 2003, 8:33am, Sir Col wrote:
I still think that my demonstration of the non-denumerability of the natural numbers holds. The statement is conversely true: (i) each natural number has its own unique decimal representation, and, (ii) each decimal representation is equivalent to a unique natural number. |
|
0.111... is a decimal representation, but it does not map back to a natural number.
To denumerate you need a bijection,
All elements of the domain must map to a unique element in the image, and all elements in the image must be mapped to at least once from the domain.
Clearly the natural numbers don't bijectively map to the all decimal representations in the way you propose (because not all decimal representations are mapped to).
They do however nicely map to a subset of decimal representations, but that's not the same thing.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #19 on: Sep 8th, 2003, 1:08pm » |
Quote Modify
|
Good point, again, towr!
But how long is the decimal string, 0.1111....? How long can I make a natural number, 11111...? Perhaps I could redefine my mapping to say that, if all natural numbers terminate then, my decimal strings terminate. Whichever way, I could make the decimal string as wide as the list is tall and it is between these two sets that I claim a one-to-one unique and complete mapping exists.
|
| « Last Edit: Sep 8th, 2003, 1:11pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Denumerability Dilemma
« Reply #20 on: Sep 8th, 2003, 2:00pm » |
Quote Modify
|
yes, but what do you want that to prove?
It certainly doesn't say anything about all rational numbers, or decimal representations thereof, nor about reals or the decimal representation thereof.
And if you apply the diagonal method (if that's what you intend, I'm not quite sure) the resulting decimal won't be in that set, nor is there any reason it should be. Which is different in the case of reals, the number constructed there has to be a real. Doing the same for, for instance, a set of rational numbers needn't give a rational number.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Denumerability Dilemma
« Reply #21 on: Sep 8th, 2003, 8:26pm » |
Quote Modify
|
Because I spent so much time giving my answer to the new posts in the 0.999... thread, I don't have time to review this in detail, but it seems to me that the flaw in your method has been amply demonstrated.
Let's start with your last question: How long is 0.111...: Answer: Infinitely long. I.e. there are an infinite number of decimal places =1.
How long can you make an integer of the form 1111... ? Answer: any FINITE length.
Do you see the difference? The first is a single instance of something of infinite length. The second contains infinitely many objects, and there is no uniform limit to their length, but all the individual objects are themselve finite in length. None of them correspond under your mapping to the infinitely long 0.111...
Thus, all of your natural numbers correspond to terminating decimals, but there is no fixed "width" to them, such as is implied by your last post.
...111 is not a natural number.
You also say that you never included any irrational numbers. But then you try to apply the same logic used to show the uncountability of the Reals to your list. But here is the crux:
The diagonal argument shows that any sequence of real numbers in [0,1] cannot include all real numbers in that interval, because one can be identified which is not equal to any element of the list.
In your case, the exact same is true, the diagonalization procedure produces a real number not in your list. But unlike with the previous argument, we already knew this! There are lots of real numbers not in your list! So we have found one of them - this does not tell us anything new.
Your mistake is that you then assume there is some natural number corresponding to the produced real number. I.e., that the number IS in your list after all. This provides the paradox of the Natural numbers not being denumerable.
But you have not justified in any way this assumption - nor can you; it's not true. The number produced by the diagonalization process on your enumeration has to have an infinite number of non-zero digits. The natural numbers all correspond to decimals with only a finite number of non-zero digits.
The reason you get a contradiction (that there is no bijection (1-1, onto mapping) of the natural numbers onto themselves, which is clearly ridiculous because the identity map is such a mapping) is because this thing you have assumed is false.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Denumerability Dilemma
« Reply #22 on: Sep 9th, 2003, 12:31am » |
Quote Modify
|
on Sep 8th, 2003, 8:26pm, Icarus wrote:| Because I spent so much time giving my answer to the new posts in the 0.999... thread, I don't have time to review this in detail, but it seems to me that the flaw in your method has been amply demonstrated. |
|
You're right, there have been some excellent refutations of my idea – thanks for your patience guys! – but your post has knocked me off my fence of indecision. So it looks like the mathematical community can breathe a sigh of relief for the moment; but, in the words of Arnie... "I'll be back!" 
|
| « Last Edit: Sep 9th, 2003, 12:32am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Denumerability Dilemma
« Reply #23 on: Sep 9th, 2003, 3:47pm » |
Quote Modify
|
on Sep 9th, 2003, 12:31am, Sir Col wrote:| but, in the words of Arnie... "I'll be back!" |
|
Cantor sleeps uneasy!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Denumerability Dilemma
« Reply #24 on: Sep 10th, 2003, 12:46pm » |
Quote Modify
|
Here's a question: how countable is the Cantor set?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print