Sunday, March 30, 2008

On Undefinable Numbers

If you are asked to define the biggest number you can, and restricted to only using only 1000 characters of English text, then there are only finitely many things you can write, and only finitely many numbers you can define.

Out of all the numbers nameable with 1000 characters of English text, which is the biggest? Surely, it must be huge -- a lot bigger than "a googol to the power of (a googol to the power of a googol (...and so on, nested a googol times))".

Unfortunately, there is no such "biggest number", because there is no well-defined mapping from English phrases to numbers. In Who Can Name the Bigger Number, Scott Aaronson considers:

"One plus the biggest whole number nameable with 1,000 characters of English text."

This number takes at least 1,001 characters to name. Yet we’ve just named it with only 80 characters! Like a snake that swallows itself whole, our colossal number dissolves in a tumult of contradiction. What gives?

The paradox I’ve just described was first published by Bertrand Russell, who attributed it to a librarian named G. G. Berry. The Berry Paradox arises not from mathematics, but from the ambiguity inherent in the English language. There’s no surefire way to convert an English phrase into the number it names (or to decide whether it names a number at all).

The problem with English isn’t that it’s unsuitable for a discussion of math. On the contrary, it’s too good at discussing math. The Berry paradox shows that if phrases in a language could all be unambiguously interpreted as numbers, then the language wouldn’t be able to refer to itself with anywhere near as much expressive power as English.

The Berry paradox only applies when one attempts to define big natural numbers using natural language. But there is also a second problem when you try to define a real number using any representation: the finite-length strings you use to represent real numbers aren't able to represent them all.

The problem is that the set of real numbers is uncountably infinite, while the set of finite-length strings is countably infinite. (If you don't know what that means, then read the Infinity lesson notes from X-treme Thinking). Thus, the set of real numbers that you can define is only a countable island in the uncountable ocean of reals.

OK now imagine you're given an infinitely long piece of paper with a real number printed on it. It starts like this: 0.821480865132823066470938446095...

As far as you look, the numbers seem completely random. You don't discern any pattern at all. Let's say you have an eternity to look at this number and try to understand it, but when you're done, you have to communicate which number this is to a mortal living in a finite universe. What do you do?

In the general case, this is impossible, because we know that most real numbers are undefinable. So do you just give up? But wait, the number you were given was actually Pi, except with the first 100 decimal digits taken out. You could have just told that to the mortal!

Every real number has infinitely many decimal digits after the decimal point. And in general, it takes an infinite amount of information to communicate which real number you're talking about. But it would be overkill for me to spend my life trying to say infinitely many 3's as in 0.333333... when I could just use a finite shorthand like "one third" or "zero point three three three and so on". Certain real numbers admit to being identified by finite pieces of information. These numbers include Pi, for example, as well as the number 0.56656565556... whose 2nd, 3rd, 5th, and all other prime-numbered digits after the decimal points are 6's, with the composite-numbered digits all being 5's, and way more elaborate constructions than this.

So what kinds of real numbers can't we define? What does an undefinable real number look like? It looks like a number that you can't say what it looks like. In other words, it looks completely and truly random, more random than it's logically possible for finite creatures to understand.

So not only are we unable to talk about "the biggest whole number nameable with 1,000 characters of English text", we also can't say anything interesting about which real numbers are definable. In other words, the vast majority of real numbers are undefinable, but we can't imagine which ones they are, and we wouldn't know them when we see them!

Does it even make sense for us finite humans to talk about the existence of "undefinable real numbers" and the supposedly "infinite amount of information" that they contain? Are we talking about anything at all? It seems like the "ocean of undefinable reals" is really a make-believe ocean, and the "island of definable reals" is really all that's there to talk about.