Are The Reals Really Uncountable?

http://rjlipton.wordpress.com/2010/01/20/are-the-reals-really-uncountable/

by profquail • 17 years ago

22 38 17 years ago

rjlipton.wordpress.com

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.

yannis2• 17 years 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.

RiderOfGiraffes8• 17 years 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...

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

http://www.solipsys.co.uk/new/BallsInBarrels.html?HN

bmm6o3• 17 years 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• 17 years 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.

sophacles2• 17 years 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.

gabrielroth3• 17 years ago

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

phaedrus5• 17 years 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.

RiderOfGiraffes8• 17 years 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.

phaedrus5• 17 years 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.

WilliamLP• 17 years ago

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.

phaedrus5• 17 years ago

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.

lmkg5• 17 years ago

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

phaedrus5• 17 years ago

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.

sophacles2• 17 years ago

The paper linked in the article is gem.

lisper• 17 years 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• 17 years 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?

gabrielroth3• 17 years 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.

bmm6o3• 17 years 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?

gabrielroth3• 17 years 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)

gprisament• 17 years ago

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

gnosis• 17 years 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.

bmm6o3• 17 years 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".

Are The Reals Really Uncountable?

Related Stories