Does my idea prove that the real numbers are countable?
Pages: 12
In my Discrete Math for Computer Science I class, we recently learned about countability, such as that the rational numbers are countably infinite because you can form a 2D grid of fractions where the numerator and denominator are the x and y coordinates. But we also were taught that the real numbers were uncountable.
I recently thought up a way to count them, similar to the way rational numbers are counted. This assumes you can make every possible real number with:
- an integer number before the decimal point
- an integral number of leading zeros after the decimal place
- an integer number after the leading zeros
I can't think of any real numbers that aren't made this way.
So my way to count real numbers works like this: You have a 3D grid starting at (0, 0, 0) and representing all integers on the x axis and all positive integers including 0 on the y and z axis. At each coordinate, you form a number with the above characteristics with x being the number before the decimal point, y being the number of leading zeroes after the decimal point and z being the number after the leading zeroes. Similar to the way you count rational numbers on the 2D grid, on this 3D grid you form a spiral, filling in a diagonal layer, and then you alternate to negative x and do the same. You can go on like this infinitely hitting every X,Y,Z coordinate and thus counting all real numbers.
This seems like it's too simple, obvious, and intuitive to not have been thought of before, and it also bothers me that it's been proven that the real numbers are not countable. So where is my logic flawed? What invalid assumption have I made?
I recently thought up a way to count them, similar to the way rational numbers are counted. This assumes you can make every possible real number with:
- an integer number before the decimal point
- an integral number of leading zeros after the decimal place
- an integer number after the leading zeros
I can't think of any real numbers that aren't made this way.
So my way to count real numbers works like this: You have a 3D grid starting at (0, 0, 0) and representing all integers on the x axis and all positive integers including 0 on the y and z axis. At each coordinate, you form a number with the above characteristics with x being the number before the decimal point, y being the number of leading zeroes after the decimal point and z being the number after the leading zeroes. Similar to the way you count rational numbers on the 2D grid, on this 3D grid you form a spiral, filling in a diagonal layer, and then you alternate to negative x and do the same. You can go on like this infinitely hitting every X,Y,Z coordinate and thus counting all real numbers.
This seems like it's too simple, obvious, and intuitive to not have been thought of before, and it also bothers me that it's been proven that the real numbers are not countable. So where is my logic flawed? What invalid assumption have I made?
Well, the way you do it could cause many duplicates. A 2D matrix was enough.
Besides this thing, I don't know.
Edit: Perhaps you are right, you need a 3D matrix. Basically ignore me.
Besides this thing, I don't know.
Edit: Perhaps you are right, you need a 3D matrix. Basically ignore me.
Last edited on
I think you can't actually go in a sprial like you say and hit everything at some point. I'll check that in a bit.
EDIT:
You can't do it the way you are describing. You can't "fill in" a diagonal layer since doing so would take an infinite number of counts (if you hold x to be a constant, say 1, you are back at counting the rationals basically).
And I'm not really sure what you mean by "diagonal layer." They way I am looking at it, you are filling in "planes" where you hold x constant and do a normal 2d thing for y/z.
EDIT:
| Similar to the way you count rational numbers on the 2D grid, on this 3D grid you form a spiral, filling in a diagonal layer, and then you alternate to negative x and do the same. You can go on like this infinitely hitting every X,Y,Z coordinate and thus counting all real numbers. |
You can't do it the way you are describing. You can't "fill in" a diagonal layer since doing so would take an infinite number of counts (if you hold x to be a constant, say 1, you are back at counting the rationals basically).
And I'm not really sure what you mean by "diagonal layer." They way I am looking at it, you are filling in "planes" where you hold x constant and do a normal 2d thing for y/z.
Last edited on
| EssGeEich wrote: |
|---|
| Well, the way you do it could cause many duplicates. |
@firedraco: I'd be very interested to understand how you can't count in a spiral like that, maybe I didn't explain it right but it works as I visualize it in my head. It's like submerging the corner of an infinite sponge cube into an infinite sea of water.
If I understand you correctly, a number like 73.0005 would be the point (x,y,z) = (73,3,5). It is true that your scheme as the cross product of the Integers, the Natural Numbers and the Natural Numbers is countable, but you need your z values to be able to represent infinite sequences of digits. For example, 73.000555... has no representation in your scheme.
For a simple proof that the closed interval [0,1] is not countable, assume not. Then there exists a one to one onto function from the Natural Numbers onto [0,1], say f(n).
Consider the real number x whose decimal expansion is defined as follows:
Let k denote the digit of the kth decimal place of x. We set k = 7 if the kth decimal place of f(k) != 7 and k = 4 if the kth decimal place of f(k ) == 7.
Note that the decimal expansion of x consists of only 4s and 7s and is constructed in such a way that it always differs from f(n) in the nth decimal place. Hence x != f(n) for all n, which is a contradiction, so no such function exists.
For a simple proof that the closed interval [0,1] is not countable, assume not. Then there exists a one to one onto function from the Natural Numbers onto [0,1], say f(n).
Consider the real number x whose decimal expansion is defined as follows:
Let k denote the digit of the kth decimal place of x. We set k = 7 if the kth decimal place of f(k) != 7 and k = 4 if the kth decimal place of f(k ) == 7.
Note that the decimal expansion of x consists of only 4s and 7s and is constructed in such a way that it always differs from f(n) in the nth decimal place. Hence x != f(n) for all n, which is a contradiction, so no such function exists.
Ah, you're right about the infinite repetition. What if we add an extra dimension (making this 4-dimensional) to represent how many of the last n decimal places are part of an infinite repetition?
And, can Pi's decimal places fit into a single integer or does the fact that it is an infinite sequence (as far as we know) make that impossible?
And, can Pi's decimal places fit into a single integer or does the fact that it is an infinite sequence (as far as we know) make that impossible?
Last edited on
| I can't think of any real numbers that aren't made this way. |
How about pi? How do you graph the "integer number" that appears after the leading zeroes?
I edited my previous post to ask that very question, I didn't see your post.
Last edited on
Consider x = 0.101001000100001... with the pattern continuing. This number is irrational and has no representation even with a 4th dimension. And it has an uncountable number of brothers and sisters.
NXNXN...XN a finite number of times is still countable, but the cross product of the Naturals with themselves a countably infinite number of times (which is essentially the set of all infinite sequences of Natural numbers) has the same cardinality as the Reals. But the set of all infinite sequences of Natural numbers is the type of thing you need to get the Reals. Adding a finite number of dimensions is not going to help.
NXNXN...XN a finite number of times is still countable, but the cross product of the Naturals with themselves a countably infinite number of times (which is essentially the set of all infinite sequences of Natural numbers) has the same cardinality as the Reals. But the set of all infinite sequences of Natural numbers is the type of thing you need to get the Reals. Adding a finite number of dimensions is not going to help.
@L B your formula generates only a subset of rational numbers. Give me the coordinates of Pi or 1/3 in your system. You can't because those numbers are *not* in your set.
Last edited on
@LB It was just a consideration, not an actual problem.
As I said, just ignore that c:
Rapidcoder, it is possible.
It's:
x 3
y 0
z 1415...
It's just infinitesimal...
Which in fact may break LB's thoughts...
Is it possible?
As I said, just ignore that c:
Rapidcoder, it is possible.
It's:
x 3
y 0
z 1415...
It's just infinitesimal...
Which in fact may break LB's thoughts...
Is it possible?
Last edited on
You're trying to prove Cantor was wrong??
Cantor's diagonal argument
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
Andy
Cantor's diagonal argument
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
Andy
Last edited on
| Rapidcoder, it is possible. It's: x 3 y 0 z 1415... |
No, it's not. As we can see by examining your post with the convenient ellipsis, there is no discrete representation of z which can be used to graph the number.
[edit: ellipses should've been singular.]
Last edited on
I hesitate to reply to a thread that should have been over last night, but there does appear to have been some "piling on" since. Rapidcoder's mention of 1/3 was equivalent to my 73.000555 and his mention of pi had already been mentioned by cire. I replied, not to prove L B wrong (he already knew he was wrong), but rather to answer his question:
His error arose from not realizing that a real number is rational if and only if its decimal representation either terminates or ultimately contains a pattern that repeats ad infinitum and hence none of the irrationals can be represented in his scheme.
I would hope, L B, that you would not be discouraged from posting such questions in the future because of any "piling on" which I don't think was intentional.
I for one, cannot help but admire the thought processes that led to the question, that having learned about countably infinite sets and seen a proof that the rationals are countable, you would try to extend or modify the argument to see why it doesn't work for the reals. It is precisely those types of thought processes, even when they lead to dead-ends, that result in a better understanding of new concepts and how to use them. I believe (just an amateur programmer's opinion here) those same types of thought processes are what a programmer uses in solving programming problems. Haviing thought about these things places you are far ahead of your fellow students who learned the definition of countable and uncountable, saw a couple examples and haven't thought about the ideas since.
I must warn you however, that if you persist in thinking such thoughts and your math professor finds out about it, one day he may ask you to see him after class and say to you:
"L B, have you ever thought about changing your major from computer science to math?"
Best of luck with your studies.
| So where is my logic flawed? What invalid assumption have I made? |
His error arose from not realizing that a real number is rational if and only if its decimal representation either terminates or ultimately contains a pattern that repeats ad infinitum and hence none of the irrationals can be represented in his scheme.
I would hope, L B, that you would not be discouraged from posting such questions in the future because of any "piling on" which I don't think was intentional.
I for one, cannot help but admire the thought processes that led to the question, that having learned about countably infinite sets and seen a proof that the rationals are countable, you would try to extend or modify the argument to see why it doesn't work for the reals. It is precisely those types of thought processes, even when they lead to dead-ends, that result in a better understanding of new concepts and how to use them. I believe (just an amateur programmer's opinion here) those same types of thought processes are what a programmer uses in solving programming problems. Haviing thought about these things places you are far ahead of your fellow students who learned the definition of countable and uncountable, saw a couple examples and haven't thought about the ideas since.
I must warn you however, that if you persist in thinking such thoughts and your math professor finds out about it, one day he may ask you to see him after class and say to you:
"L B, have you ever thought about changing your major from computer science to math?"
Best of luck with your studies.
Last edited on
| Alrededor wrote: |
|---|
"L B, have you ever thought about changing your major from computer science to math?" |
His professor is a douche if he says that.
He should know he wants to be called LB without a space :>
But yes, anyways, LB's got a couple nice topics.
I was wondering, what about making it a 4D array where the last entry choses the recursively running number?
To represent PI, its coordinate could be
3, 0, 0, 1415...
Where 1415 would repeat while building the number itself
And to represent 1/3 it could be
0, 0, 0, 3
| To represent PI, its coordinate could be 3, 0, 0, 1415... Where 1415 would repeat while building the number itself |
Well, the thing is PI doesn't repeat...it's irrational.
Pages: 12