notes-math-uncountable

The cardinality of a set of numbers in any line segment of the reals is uncountable ( http://en.wikipedia.org/wiki/Cardinality_of_the_continuum ). The fact that the real number line is infinitely long isn't even needed for its uncountability.

The cardinality of a set of all finite (but arbitrarily long) strings over a finite alphabet is countable.

But, since we know that the cardinality of reals over any line segment is uncountable, the cardinality of decimal expansions over any line segment is uncountable. That is, this is a set of infinite length strings over a finite alphabet.

What is the information present in this set that is not in a set of arbitrarily long but finite strings? It's all those irrational numbers, which can have patterns that are infinitely informative, that is, that go on forever but stay unpredictable and possibly even 'interesting'.

Now, is this physically real?

Well, physically, for practical, and possibly physical, reasons, we can only reach things that are a certain minimal size. But let's give you a superpower.

Let's imagine that you have a spaceship that you can get and that allows you to "zoom in" and "zoom out", making yourself smaller or larger. You can set the speed of the zooming to any arbitrarily high integer. Each zoom you arrive at another decimal place and can choose which number to assign to this place; think of this like moving a little to the left or to the right as you zoom in (navigating). Imagine those Mandelbrot fractal programs. As you 'zoom in' farther and farther, you pass more and more of the rational numbers, as their decimal expansions peter out. But the space around you is still densely populated by those irrationals.

If you selected some particular interesting fractal set of irrationals and viewed them through your spaceship window, you would see a complicated image that would change as you zoomed in, just like those Mandelbrot programs. If you picked the right set and avoided the boring trajectories, it could always change and never repeat itself. A tiny navigational difference at any decimal point might change what you will see past that point, forever.

In order to hit a particular irrational, you would have to (a) zoom in (countably) forever, (b) navigate JUST RIGHT at each of these steps.

Assuming you have a finite lifespan, you'll never reach one.

OK, we'll give you another superpower. What if you had a 'hyperdrive' that lets you zoom in a countably infinite amount in the blink of an eye (infinite speed zooming)?

You still can't hit an irrational, because you can't navigate; when you turn on the hyperdrive you just go in a straight line. How could it be otherwise, since your spaceship doesn't know which choice you want to make at each navigation junction (each decimal place).

OK, another superpower. You can have a computer program, an autopilot. You are not conscious during the hyperdrive, but the computer can still operate, so you can program it to navigate for you. Now you can reach some of these irrationals, like pi.

But you have to type in the computer program by hand, so its length must be finite, so its finite string over a finite alphabet, so there are only countably many possible computer programs. So you can still reach only countably many numbers, even with your spaceship, even with hyperdrive, even with autopilot.

All the uncountableness in the reals is coming from those UNreachable (undefinable) irrationals. Those infinitely long strings of digits that cannot be compressed to any computer program.

Is this real?

I can't say for sure that it's definitely NOT real. But i don't think i can say for sure that it's real, either. This seems to give some ammo to classical finitism ( http://en.wikipedia.org/wiki/Finitism#Classical_finitism_vs._strict_finitism ); that is, maybe we should avoid relying upon uncountable cardinalities in mathematics.

Now, an argument on the other side is that the powerset of the integers is uncountable, and what's so bad about a powerset? But you can visualize the powerset using similar metaphors as above (at each step of your journey towards a possibly infinite subset, decide if this integer is in the subset or not); if you have a powerset over an INFINITE set, then almost all of the subsets of this set will themselves be infinitely long and undefinable.

A philosophical argument for uncountables is that, say that the physics of our universe is determined by at least one fundamental constant, and this constant may be irrational. We'd have to at least consider the possibility that it is uncomputable. In which case, our knowledge about it is just that it is a real number.

However, if it is computable and we eventually discover that, then there will have been no need to go thru all that. And if it is not computable, we'll never know for sure, because anything we observe could be approximated by computables. So perhaps any knowledge we gain by thinking of this constant as a real is purely hypothetical and hence we can avoid that.

On the other hand, there could be great cognitive economy gained by thinking in this fashion. What if we discover what seems to be a physical instantiation of a halting problem oracle? We'll never know for sure that that's what it is; maybe someday it'll be wrong. But if it is never observed to make a mistake, it's simpler to assume that it actually is this thing, rather than just a very good approximation.

In that particular example, i think Turing jumps are included in ACA_0, although i'm not sure (see https://en.wikipedia.org/wiki/Second-order_arithmetic ). Could it be that all such phenomena that 'seem like reals' can in fact be captured by something weaker than second order arithmetic?

hmmm... maybe what i want is the definable subset of the reals. Which is countable.

another argument for uncountables is that different sensible-sounding constructions of the reals don't include each other until you reach infinite precision. E.g. rationals vs. surreals; the surreals only include rationals whose denominator is of the form 2^x until you reach infinite precision. So 1/3 isn't in the surreals until then. But at that point in the surreal construction you get all the reals (i think; doublecheck that).