Are The Reals Really Uncountable?
rjlipton.wordpress.com
rjlipton.wordpress.com
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?
Cantor's second proof generalises to show that given any set, X, the collection of functions
{ f: X -> {0,1} }
|{f: X -> {0,1}}| > |X|
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:
[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.
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.
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.
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.
Also, thanks for being civil in response to my show-off-y reply.
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...
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.
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.
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?
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)
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.
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.
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.
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.)
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?
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?
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.
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
http://news.ycombinator.com/item?id=1069808
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.
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.
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.