Hacker News new | past | comments | ask | show | jobs | submit login
Are The Reals Really Uncountable? (rjlipton.wordpress.com)
22 points by profquail on Jan 22, 2010 | hide | past | favorite | 38 comments

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?

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.

> 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.

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.

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:


and here's something some people think of as a paradox:


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.

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.

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.

  > Actually, having an infinity at the end of
  > every line on the complex plane just gives
  > you a simple disc.
Er, judging from the rest of your comment you must simply have misunderstood me. For every line through 0 in the complex plane, take a point and define it to be at both ends of the line. That is doing as you say, associating antipodal points.

And I do do calculus (well, equivalent procedures) on such objects. It's clear from your comments that you know about these things - trust me that I do as well.

So we're agreed that the concept of infinite sized sets and the concept of "points at infinity" are different, and for teaching about "infinity" it might be useful to separate them explicitly.

Interesting observation. Thanks.

Glad we cleared that up, and glad I could provide some insight =).

Also, thanks for being civil in response to my show-off-y reply.

It is also a matter of being clear about some terminology early during discussions, if one says for example that the set of integers is countably infinite and that the set of real numbers is uncountably infinite is easier to understand.

The Aleph Numbers are the terms to describe the types of infinity to which you are referring:


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...

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.

> 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?

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)

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.

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.

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.

Are you offended at the idea that a mathematical thing called a "real" exists, or offended at the idea that somebody thinks real numbers actually exist in the real (no pun intended) universe?

Because nobody thinks real numbers actually exist in a usable manner; whether the base of the universe is "ultimately real" or "ultimately discrete" is an open problem, but also irrelevant since we can't get to real values (if they exist) with infinite precision thanks to the various uncertainty principles.

Ultimately, there really isn't anything to "agree" or "disagree" with when it comes to the reals; they are just a definition, and everyone who knows what they are talking about know they don't actually exist. See also the Axiom of Choice; really there isn't anything to "believe" or "not believe" about it.

(I say "offended" and "believe" but I am not trying to put words into your mouth. I am not satisfied that either of them describe your tone, but I needed something. Please do clarify if those are wrong.)

To answer your first question: Yes. I mean, both. (And no, I'm not offended by your choice of words.)

Since you've restated the discussion on more neutral terms, allow me to rephrase my position in your terms: The article is about how people have trouble swallowing Cantor's argument. Yet clearly Cantor's argument is correct within a framework that includes the reals. And my position is that the existence of Cantor's argument leads me to question the framework itself.

You say that there really isn't anything to agree or disagree with, that we are just talking about definitions. Absolutely, I agree. It's unfortunate that the only words we have to talk about these things also have extra connotations that might be more forceful than what we really mean. We're really just talking about the consequences of manipulating symbols under certain rules.

HOWEVER... Isn't the whole point of math that you expect at some point to analyze the result of the symbol manipulation and "read off" an interpretable meaning from the answer? At that point may you not make a judgement that the combination of the system you choose and your interpretation of it lead to "believable" results? Is it entirely correct to say that there is no such thing as "agreeing" or "disagreeing" with a definition of a mathematical object, if putting it into the system leads to results you don't consider believable?

"Isn't the whole point of math that you expect at some point to analyze the result of the symbol manipulation and 'read off' an interpretable meaning from the answer?'

Ah, and therein lies the rub. In math terminology, I think that that itself is an axiom, in the sense that you can choose it or not choose it, and it will strongly affect the rest of the system. If you accept the axiom, you end up going down the constructivist path. If you do not, you end up in "conventional mathematics" (i.e., what you get for a real math degree in college).

Personally, as a programmer I am also sympathetic to the constructivist viewpoint, but I am happy to settle for everyone involved understanding when they've left the physical universe (real numbers, axiom of choice, etc) and when they haven't. If some people want to screw around in the unreal universe, more power to them, doesn't have to bother me. And they often produce useful approximations for real-life use. As RiderOfGiraffes said, there are proofs that work on reals much better than any actual number, and I observe that in practice the resulting maths work out pretty well in the real world, even if they aren't actually physical.

(We have way larger problems dealing with floating point, monsters of our own creation, than we do in dealing with the fact that our equations of motion are defined based on real numbers that don't actually correspond to anything, where the inaccuracies are typically beyond our measuring ability and dominated by general inaccuracies of the input data which are far larger than the granularity of the universe.)

But I do think maintaining that distinction is definitely important. I further observe that while I can't speak for all of mathematics, the mathematicians are very careful to distinguish what takes the Axiom of Choice and what does not, just to draw one example. They are pretty good about showing their work.

I guess the takeaway is that you certainly aren't alone; many people agree that real numbers are ridiculous in the way you are sensing. But they can be a useful fiction.

  > Isn't the whole point of math that you expect at
  > some point to analyze the result of the symbol
  > manipulation and "read off" an interpretable
  > meaning from the answer?
I've responded to this at greater length here: http://news.ycombinator.com/item?id=1071734

You are absolutely right when it comes to the application of existing math, but in Pure Math that doesn't turn out to be the case.

I offer the proposition that all models are inaccurate, some models are useful, and the usefulness of a model is in the balance between the accuracy and the ease of use.

Compared with floating point numbers in computing, and finite difference types of calculus, the model offered by the reals is much, much simpler to work with, and then modelling them with floating point nubmers is comparatively simple.

Doing the work directly with floats is hard, and detailed analysis and theorems are virtually impossible.

For a sound theoretical basis to many applications, it's easier to work with reals and then approximate with floats than it is to work with floats directly.

I further offer the observation made in another item that working directly with computer calculations is making science unreproducable


Suggesting that we simply do the calculations and then work with the results has its drawbacks.

Finally, I'm doing some huge simulations at the moment, and every now and again they blow up. The results are supremely plausible, but if I didn't have an underlying theory, rigorously developed in the world of pure math, I wouldn't know that.

Interesting observations.

I'd like to write this up - I might later - I don't have time now - here's some material from Feynman ...

Take successive square roots of 10. As you get further and further you spot a pattern, that when e is very small, 10^e ~ 1+c.e for some constant c.

Now take 10^(i.e) where e is very small and i=sqrt(-1). Then 10^(i.e) ~ 1+c.i.e. Take repeated powers and you end up moving in a circle. Following that we end up with the formula e^(i.t) = cos(t)+i.sin(t) where t is a real angle.

None of that works if you don't basically take the reals for granted. Or at least, it's very hard.

Can you say more specifically in what way you feel the reals are 'overpowered' or contradictory? As a mathematician, I'm interested in why people think the concept is odd, because it's not intuitively odd to me and I want to understand this alternative viewpoint. Would I be right in thinking it's related to reals being 'infinitely precise?'

By overpowered, I mean that a model that allows the idea of something having infinite precision leads to apparent paradoxes. For instance you get constructs like Gabriel's Horn that have greater surface area than volume, or the case of choosing a random real number between 0 and 1: the probability of picking any particular real number is (approaches?) zero, yet some number will be picked.

But in the case of the Cantor argument specifically he seems to be encoding an infinite amount of information in one number simply by extending the digits after the decimal point. It's almost like - cheating, or more specifically an "exploit" allowed by what I call reals being overpowered.

(Here I have to make an aside: the value Pi, which is actually a computable number, can also encode any amount of information because any number will appear at some point in the expansion. But you'd have to indicate where in Pi your number starts, and your index values would (on avergage) be so large as to consume at least as many bits of information as it would to simply state the number you want.)

In the physical world, when you do something like measure the voltage on a capacitor you can only measure it to within a certain accuracy & precision. If you wanted to make an analog computer that uses different voltages to represent different values, you'd be limited by the accuracy and precision which you could measure it.

Note that, even if the voltage is infinitely variable, your ability to differentiate those values is still limited, so you still do not have infinite precision. (In Turing's paper on computable numbers, he makes the case that even if a human brain can have infinite states, there would at some point be a threshold of similarity at which the brain couldn't distinguish two similar states from each other.)

So my claim is that real numbers imply the ability to measure something to infinite precision, and that that is contradictory to physical experience.

Reality and measurable reality were separate concepts, until quantum mechanics came along. If the intricacies of the Reals demonstrate the philosophy they come out of, it has as much to do with predating the atom in chemistry and the Heisenberg Principle in quantum mechanics as it does with predating float-point numbers.

I feel that math is intended to appeal to logical intuition rather than physical intuition, so my belief is that adding limits to precision is an unnecessary complication to the number system. By extension, I don't believe that math or numbers reveal 'fundamental truths' of the physical universe, nor are they intended to. I view math as a disembodied exercise in logic, and if we happen to find a physical system that satisfies the hypotheses of a mathematical system, then the results will apply as well. The result of this is that I view the reals as 'purer' math because they have less hypotheses, and numerical approximations as a set of additional hypotheses that are more commonly seen in practice. The natural result is that there's a lot of mathematical ideals with cool properties that are ruled out in practical terms.

I have a few questions for you and your viewpoint (for my own curiosity, not antagonistic).

1. Do you believe that Pi actually does have an infinite number of decimal places, or that it's limited by the precision with which we can measure a circle? I think I read somewhere that 50 decimal places is enough to calculate the radius of the visible universe from the radius to within an atom's width of accuracy.

2. What do you think of the Random Oracle Model in cryptography[1]? I think there's an anology between the ROM vs real hashes, and how I conceive of the reals vs finite-precision mathematics. In particular, simple and (logically) intuitive idealized models have properties that are not held by any possible real approximation. Feel free to ask me more if you're totally confused =P.

3. Do you accept infinite-precision rational numbers? Why or why not? My motivation in asking is that there's a difference between computability and measurability, and you appeal to both as a source of intuition.

[1] http://en.wikipedia.org/wiki/Random_oracle_model

Reals numbers give you the property that if a continuous curve is bigger than zero somewhere, and smaller somewhere else, then it must cross the line at a certain point. You probably want to say that sqrt(2) has a solution. Without reals you don't have this.

I would say that the solution to sqrt(2) is the expansion (to however many finite number of iterations you run it for) of the bits produced by the Turing machine that computes sqrt(2). Sqrt(2) is a computable number, so it exists both in my system and in yours.

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

The paper linked in the article is gem.

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.

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.

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".

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.

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.

From a pure math perspective, the limitations of computers are irrelevant.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact