6 ms·

Are The Reals Really Uncountable?

22 points by profquail 17y ago

RiderOfGiraffes 17y ago
The short answer is yes, and I, like the author, don't really understand why so many people spend so much time trying to show that Cantor's proofs are wrong. Cantor's second proof generalises to show that given any set, X, the collection of functions { f: X -> {0,1} } is of size strictly larger than X. |{f: X -> {0,1}}| > |X| The proof that the reals are uncountable is just this, with the set X as the set of natural numbers.
- yannis 17y ago
  One side of my brain accepts and understands the Maths but another corner of it can never understand the paradox as to how one infinity is greater than the other; since the reals are uncountable that is, there are strictly more real numbers than natural numbers, and both sets are infinite.
  - RiderOfGiraffes 17y ago
    Interesting - thanks. I wonder if the problem is that people try to think of infinity as a number that's just really, really big - bigger than all the numbers. If you think of infinity as being the biggest thing there is, then you've got a problem. You (and others) are not alone. Infinity was a major problem for a very, very long time, with many contradictions and paradoxes arising because of insufficiently careful reasoning. Here's another explanation: http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html?HN http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html... and here's something some people think of as a paradox: http://www.solipsys.co.uk/new/BallsInBarrels.html?HN http://www.solipsys.co.uk/new/BallsInBarrels.html?HN
    - lmkg 17y ago
      I made an interesting observation recently, and I think it's not reinforced enough in the teaching of maths: "infinite" and "infinity" have less to do with each other than you would think. "Infinity" is a particular point in a set. "Infinite" describes the size of a set. There's only one "infinity"[1] but there's (infinitely!) many types of "infinite." By application of the Sapir-Whorf hypothesis, this would be easier for people to understand if we used more separate terms for the two concepts. [1] Well, you can have +/-infinity... or you can make it the same infinity at both ends. This is really the only way to go when you deal with the complex plane instead of the real line. But regardless, the point is in topology, infinity can be treated as singular and definite.
      - RiderOfGiraffes 17y ago
        You have an interesting and perhaps useful conceptual point, but your language is at odds with current usage. The concepts of infinite sizes of sets and point "at infinity" are different, and should be separated. The thing is, there are multiple infinities even in the sense you're thinking about. For example, you can have one at the end of every line in the complex plane. That gives you the projective plane. Again, in topology. The one you're thinking of is the one-point compactification of the plane, but it's not the only one.
        lmkg 17y ago
        Actually, having an infinity at the end of every line on the complex plane just gives you a simple disc. To get the projective plane, you have to associate antipodal points, like associating +/-infinity on the real line to a single infinity, but for every line that runs through the origin separately. But in topology, whether these points are 'at infinity' or not is arbitrary, because the complex plane is indistinguishable from the unit disc, until you start adding some more structure to it like a differential structure. And trust me, you do not want to be doing any sort of calculus on the complex plane with anything other than a single infinity. Conformal mappings really don't work well without that simplification. And with that simplification, everything is magical and you can integrate rainbows to get unicorns and candy canes. Nonetheless, your point is valid, it's possible to have more than a single point at infinity. However, regardless, it's more conventional to think of infinity as a particular point with some unusual properties, and in these cases with multiple infinities they're all basically the same. You don't have classes of infinities the same way you have classes of infiniteness.
    - thaumaturgy 17y ago
      I'd like to chime in here as someone who is math-interested, but never went beyond high school maths (analytical trig, sadly). IIRC, I first got my head around different orders of magnitude regarding infinities with George Gamow's popular "1, 2, 3, infinity" [1]. However -- I think, it's been a long long time since I read it -- that book presented different infinities in exactly the same way that someone who could only count to 20 would compare sets of hundreds of items. That is: assume that space is infinitely bounded, with an infinite amount of matter. You might say that there are infinitely many galaxies, and there are infinitely many stars. However, there are also infinitely many more stars than there are galaxies, because each galaxy contains more than one star. That's a fine trick for developing a simple understanding of infinities, but then apparently in later maths it completely falls over. For example, I'm one of the many people who have a rather primal loathing for the notion that .999 repeating is really equal to 1. (I literally do have a powerful emotional response to this. I hate it. I know it's been proven. I know it's a fact. But I hate it.) [1]: http://www.amazon.com/One-Two-Three-Infinity-Speculations/dp/0486256642 http://www.amazon.com/One-Two-Three-Infinity-Speculations/dp...
- bmm6o 17y ago
  > Cantor's second proof generalises [...] That may be true, but at the time a student first sees this proof, you're trying to convince him that there are different cardinalities of infinity in the first place. In fact, you've probably showed them that there are as many integers as there are even integers, which works to establish an intuition that all infinite sets have the same size.
MarkPNeyer 17y ago
I've always argued that this fact was irrelevant, because although the set of 'all reals' are uncountable, the set of computable numbers IS countable. The fact that there are numbers which cannot be represented by computers is interesting but has 0 practical applications.
- sophacles 17y ago
  So let us look at just what you can fit into a 32 bit floating number. I know you can do reals in other ways, with arbitrary precision libraries, but the point is still the same. Anyway, the 32bit float. The fact that I have a limited amount of precision, means that errors exist as a result of truncation and rounding. For details search google (the main reason for my float example). The cumulative effects of these can be large enough be represented within the given amount of precision. Since we now have a proof that those numbers are innumerably many, we should develop techniques to deal with it, rather than just add precision.
- gabrielroth 17y ago
  From a pure math perspective, the limitations of computers are irrelevant.
phaedrus 17y ago
As a programmer, the thing that bothers me about Cantor's diagonalization (and the whole concept of Real numbers) is that it presumes an infinite number of bits of information can be stored in each number. So it's kind of like saying that you can't enumerate all the values of an infinitely large floating point number using any arbitrarily large, but finite, integer. Of COURSE you can't. Which is kind of Cantor's point, but at least from the perspective of a computer scientist and a mathematical constructivist, it seems a little cheap because I consider the idea of real numbers themselves to be somewhat "overpowered", leading to contradictions inherent in the very idea. I'd make an analogy to the question of can God make a rock so big he can't lift it? Whether you believe in God or not, you can probably recognize that as a faintly ridiculous question; I feel real numbers as a concept are ridiculous in the same way.
- RiderOfGiraffes 17y ago
  Without the reals you can't assume that all limits exist. The reals are the only totally ordered complete field. As such, whether they're "practical" or "useful" is irrelevant. They are a mathematical object worthy of study in their own right. Calculus is easier with the reals than without. The computing you do is an approximation to the reals - trying to do numerical analysis without the reals is horrendous. I've seen so-called "constructivists" attempting it, and I'd rather work with the reals any day.
  - phaedrus 17y ago
    Quote: "Without the reals you can't assume that all limits exist." Oh, I agree completely. I can't assume that all limits exist. Modded you up because I agree with your premises, but I disagree with your conclusion. Both constructivism and "regular" mathematics are systems, but rather than views computable numbers as approximations of reals, I prefer to think of real valued calculus as a degenerate case numerical analysis where delta goes to zero. Here's the thing: most of mathematics was developed prior to computers, and I question how much of what's in mainstream mathematics is influenced by the requirement that ultimately the math had to be tractable to humans without the aid of a computer.
sophacles 17y ago
The paper linked in the article is gem.
- lisper 17y ago
  Yes, especially the last sentence. But don't skip ahead. It would be like listening to the punch line of a joke before hearing the setup.
leelin 17y ago
The first time I saw the proof I was not satisfied because I wondered why you couldn't use the same exact argument to show the integers are uncountable (and back in high school I didn't grasp the quick answer, 'because only reals have infinite digits, any particular integer only has finite digits'). I remember Mark Krusemeyer at MC took a more satisfying approach. He first showed the power set of integers was uncountable, then showed the one-to-one / onto mapping to the reals (and then some bit about power sets of power sets as a way of finding ever larger and more infinite sets). For whatever reason, thinking of the size of power sets seem a bit less abstract than the size of reals, maybe because it feels more discrete and computer science-ish?
gabrielroth 17y ago
I loved loved loved learning the diagonal proof in college. I've done it for friends occasionally, as a demonstration of the idea that math can be awesome. There was one guy in the class who simply wouldn't accept it. He kept saying, "But so then you add that new number to the list!" I didn't know that he was representative of a whole larger set of people. I just posted this to his Facebook page.
- bmm6o 17y ago
  > He kept saying, "But so then you add that new number to the list!" I think if you get down to it, this reveals an interesting point. I think it suggests that the logic behind the proof wasn't made clear enough, that it's not a constructive proof, it's one of the first sophisticated proofs by contradiction that a student sees. Since you aren't disproving a concrete thing - you are showing that some hypothetical number doesn't appear on some hypothetical list - it can seem very unsatisfying. Also, why is it so ridiculous to try to add a missing number to the list? There's an intuition that you're fighting with a proof like this: 0: Create an empty list 1: Find a real number not on your list 2: Add it to the list 3: goto 1 Obviously this process never terminates, but I think you have to think pretty hard before that bothers you. After all, what is fundamentally different if I replace "real" with "integer" or "rational"? (rhetorical) Finally, students are comfortable enough talking about the "set of reals". Showing that there's no such thing as the "list of reals" reveals that there must be some difference between a set and a list - but at the time this proof is presented, has that distinction been made sufficiently clear?
  - gabrielroth 17y ago
    That's a good sketch of some of the complexities involved. I remember that some months after I learned the proof, your rhetorical question 'What is fundamentally different if I replace "real" with "integer" or "rational"?' occurred to me, and I had to spend a few weeks thinking about it before the answer came to me. In other words, I got to have an experience of actual mathematical thinking without learning much higher math. This is why I love the diagonal proof, and the guy who taught it to me: Paul Lockhart, author of the essay 'A Mathematician's Lament.' (http://www.maa.org/devlin/devlin_03_08.html http://www.maa.org/devlin/devlin_03_08.html)
gprisament 17y ago
This diagonal method is also how you can prove the halting problem is unsolvable.
gnosis 17y ago
Infinity is a process, not a number. And, as such, one infinity can not be greater than another infinity, as the relationship of being "greater than" only applies to numbers, not to processes.
- bmm6o 17y ago
  If that's true, you should be able to find a flaw in Cantor's proof. However, your statement falls into the category of "not even wrong".

22 points by profquail 17y ago

The short answer is yes, and I, like the author, don't really understand why so many people spend so much time trying to show that Cantor's proofs are wrong. Cantor's second proof generalises to show that given any set, X, the collection of functions { f: X -> {0,1} } is of size strictly larger than X. |{f: X -> {0,1}}| > |X| The proof that the reals are uncountable is just this, with the set X as the set of natural numbers.

yannis 17y ago
One side of my brain accepts and understands the Maths but another corner of it can never understand the paradox as to how one infinity is greater than the other; since the reals are uncountable that is, there are strictly more real numbers than natural numbers, and both sets are infinite.
- RiderOfGiraffes 17y ago
  Interesting - thanks. I wonder if the problem is that people try to think of infinity as a number that's just really, really big - bigger than all the numbers. If you think of infinity as being the biggest thing there is, then you've got a problem. You (and others) are not alone. Infinity was a major problem for a very, very long time, with many contradictions and paradoxes arising because of insufficiently careful reasoning. Here's another explanation: http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html?HN http://www.solipsys.co.uk/new/CantorVisitsHilbertsHotel.html... and here's something some people think of as a paradox: http://www.solipsys.co.uk/new/BallsInBarrels.html?HN http://www.solipsys.co.uk/new/BallsInBarrels.html?HN
  - lmkg 17y ago
    I made an interesting observation recently, and I think it's not reinforced enough in the teaching of maths: "infinite" and "infinity" have less to do with each other than you would think. "Infinity" is a particular point in a set. "Infinite" describes the size of a set. There's only one "infinity"[1] but there's (infinitely!) many types of "infinite." By application of the Sapir-Whorf hypothesis, this would be easier for people to understand if we used more separate terms for the two concepts. [1] Well, you can have +/-infinity... or you can make it the same infinity at both ends. This is really the only way to go when you deal with the complex plane instead of the real line. But regardless, the point is in topology, infinity can be treated as singular and definite.
    - RiderOfGiraffes 17y ago
      You have an interesting and perhaps useful conceptual point, but your language is at odds with current usage. The concepts of infinite sizes of sets and point "at infinity" are different, and should be separated. The thing is, there are multiple infinities even in the sense you're thinking about. For example, you can have one at the end of every line in the complex plane. That gives you the projective plane. Again, in topology. The one you're thinking of is the one-point compactification of the plane, but it's not the only one.
      - lmkg 17y ago
        Actually, having an infinity at the end of every line on the complex plane just gives you a simple disc. To get the projective plane, you have to associate antipodal points, like associating +/-infinity on the real line to a single infinity, but for every line that runs through the origin separately. But in topology, whether these points are 'at infinity' or not is arbitrary, because the complex plane is indistinguishable from the unit disc, until you start adding some more structure to it like a differential structure. And trust me, you do not want to be doing any sort of calculus on the complex plane with anything other than a single infinity. Conformal mappings really don't work well without that simplification. And with that simplification, everything is magical and you can integrate rainbows to get unicorns and candy canes. Nonetheless, your point is valid, it's possible to have more than a single point at infinity. However, regardless, it's more conventional to think of infinity as a particular point with some unusual properties, and in these cases with multiple infinities they're all basically the same. You don't have classes of infinities the same way you have classes of infiniteness.
  - thaumaturgy 17y ago
    I'd like to chime in here as someone who is math-interested, but never went beyond high school maths (analytical trig, sadly). IIRC, I first got my head around different orders of magnitude regarding infinities with George Gamow's popular "1, 2, 3, infinity" [1]. However -- I think, it's been a long long time since I read it -- that book presented different infinities in exactly the same way that someone who could only count to 20 would compare sets of hundreds of items. That is: assume that space is infinitely bounded, with an infinite amount of matter. You might say that there are infinitely many galaxies, and there are infinitely many stars. However, there are also infinitely many more stars than there are galaxies, because each galaxy contains more than one star. That's a fine trick for developing a simple understanding of infinities, but then apparently in later maths it completely falls over. For example, I'm one of the many people who have a rather primal loathing for the notion that .999 repeating is really equal to 1. (I literally do have a powerful emotional response to this. I hate it. I know it's been proven. I know it's a fact. But I hate it.) [1]: http://www.amazon.com/One-Two-Three-Infinity-Speculations/dp/0486256642 http://www.amazon.com/One-Two-Three-Infinity-Speculations/dp...
bmm6o 17y ago
> Cantor's second proof generalises [...] That may be true, but at the time a student first sees this proof, you're trying to convince him that there are different cardinalities of infinity in the first place. In fact, you've probably showed them that there are as many integers as there are even integers, which works to establish an intuition that all infinite sets have the same size.

MarkPNeyer 17y ago

I've always argued that this fact was irrelevant, because although the set of 'all reals' are uncountable, the set of computable numbers IS countable. The fact that there are numbers which cannot be represented by computers is interesting but has 0 practical applications.

sophacles 17y ago
So let us look at just what you can fit into a 32 bit floating number. I know you can do reals in other ways, with arbitrary precision libraries, but the point is still the same. Anyway, the 32bit float. The fact that I have a limited amount of precision, means that errors exist as a result of truncation and rounding. For details search google (the main reason for my float example). The cumulative effects of these can be large enough be represented within the given amount of precision. Since we now have a proof that those numbers are innumerably many, we should develop techniques to deal with it, rather than just add precision.
gabrielroth 17y ago
From a pure math perspective, the limitations of computers are irrelevant.

phaedrus 17y ago

As a programmer, the thing that bothers me about Cantor's diagonalization (and the whole concept of Real numbers) is that it presumes an infinite number of bits of information can be stored in each number. So it's kind of like saying that you can't enumerate all the values of an infinitely large floating point number using any arbitrarily large, but finite, integer. Of COURSE you can't. Which is kind of Cantor's point, but at least from the perspective of a computer scientist and a mathematical constructivist, it seems a little cheap because I consider the idea of real numbers themselves to be somewhat "overpowered", leading to contradictions inherent in the very idea. I'd make an analogy to the question of can God make a rock so big he can't lift it? Whether you believe in God or not, you can probably recognize that as a faintly ridiculous question; I feel real numbers as a concept are ridiculous in the same way.

RiderOfGiraffes 17y ago
Without the reals you can't assume that all limits exist. The reals are the only totally ordered complete field. As such, whether they're "practical" or "useful" is irrelevant. They are a mathematical object worthy of study in their own right. Calculus is easier with the reals than without. The computing you do is an approximation to the reals - trying to do numerical analysis without the reals is horrendous. I've seen so-called "constructivists" attempting it, and I'd rather work with the reals any day.
- phaedrus 17y ago
  Quote: "Without the reals you can't assume that all limits exist." Oh, I agree completely. I can't assume that all limits exist. Modded you up because I agree with your premises, but I disagree with your conclusion. Both constructivism and "regular" mathematics are systems, but rather than views computable numbers as approximations of reals, I prefer to think of real valued calculus as a degenerate case numerical analysis where delta goes to zero. Here's the thing: most of mathematics was developed prior to computers, and I question how much of what's in mainstream mathematics is influenced by the requirement that ultimately the math had to be tractable to humans without the aid of a computer.

sophacles 17y ago

The paper linked in the article is gem.

lisper 17y ago
Yes, especially the last sentence. But don't skip ahead. It would be like listening to the punch line of a joke before hearing the setup.

leelin 17y ago

The first time I saw the proof I was not satisfied because I wondered why you couldn't use the same exact argument to show the integers are uncountable (and back in high school I didn't grasp the quick answer, 'because only reals have infinite digits, any particular integer only has finite digits'). I remember Mark Krusemeyer at MC took a more satisfying approach. He first showed the power set of integers was uncountable, then showed the one-to-one / onto mapping to the reals (and then some bit about power sets of power sets as a way of finding ever larger and more infinite sets). For whatever reason, thinking of the size of power sets seem a bit less abstract than the size of reals, maybe because it feels more discrete and computer science-ish?

gabrielroth 17y ago

I loved loved loved learning the diagonal proof in college. I've done it for friends occasionally, as a demonstration of the idea that math can be awesome. There was one guy in the class who simply wouldn't accept it. He kept saying, "But so then you add that new number to the list!" I didn't know that he was representative of a whole larger set of people. I just posted this to his Facebook page.

bmm6o 17y ago
> He kept saying, "But so then you add that new number to the list!" I think if you get down to it, this reveals an interesting point. I think it suggests that the logic behind the proof wasn't made clear enough, that it's not a constructive proof, it's one of the first sophisticated proofs by contradiction that a student sees. Since you aren't disproving a concrete thing - you are showing that some hypothetical number doesn't appear on some hypothetical list - it can seem very unsatisfying. Also, why is it so ridiculous to try to add a missing number to the list? There's an intuition that you're fighting with a proof like this: 0: Create an empty list 1: Find a real number not on your list 2: Add it to the list 3: goto 1 Obviously this process never terminates, but I think you have to think pretty hard before that bothers you. After all, what is fundamentally different if I replace "real" with "integer" or "rational"? (rhetorical) Finally, students are comfortable enough talking about the "set of reals". Showing that there's no such thing as the "list of reals" reveals that there must be some difference between a set and a list - but at the time this proof is presented, has that distinction been made sufficiently clear?
- gabrielroth 17y ago
  That's a good sketch of some of the complexities involved. I remember that some months after I learned the proof, your rhetorical question 'What is fundamentally different if I replace "real" with "integer" or "rational"?' occurred to me, and I had to spend a few weeks thinking about it before the answer came to me. In other words, I got to have an experience of actual mathematical thinking without learning much higher math. This is why I love the diagonal proof, and the guy who taught it to me: Paul Lockhart, author of the essay 'A Mathematician's Lament.' (http://www.maa.org/devlin/devlin_03_08.html http://www.maa.org/devlin/devlin_03_08.html)

gprisament 17y ago

This diagonal method is also how you can prove the halting problem is unsolvable.

gnosis 17y ago

Infinity is a process, not a number. And, as such, one infinity can not be greater than another infinity, as the relationship of being "greater than" only applies to numbers, not to processes.

bmm6o 17y ago
If that's true, you should be able to find a flaw in Cantor's proof. However, your statement falls into the category of "not even wrong".