Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Indescribable numbers: The theorem that made me fall in love with math

blog.ram.rachum.com

Post reply on HN
Print view View original

31–40 of 91 posts

Re: Indescribable numbers: The theorem that made me fall in love with math

#31

Post by vbuterin »

xerula wrote: post #16
ColinWright wrote: post #5

Earlier quoted context omitted.

You learned it, but the author worked it out for himself. Good for him - kudos.

He had probably previously encountered Cantor's diagonalization technique for proving the uncountability of the reals. He just saw how to apply the same technique to the question of describability.

It's important to note that the "diagonal argument" used to show countability of rationals or describable numbers is completely different from the one used to show the uncountability of the reals. In fact, the two counting arguments used to show countability of rationals and describable numbers are themselves quite different (I would say the latter isn't even a diagonal argument at all; it just goes through a countable union of finite sets one by one).

Re: Indescribable numbers: The theorem that made me fall in love with math

#32

Post by ukoto »

cool-RR wrote: post #24
ukoto wrote: post #22

They are real numbers, for which we have just proven it is impossible to find a description that will match them. We have proven that no description will ever describe them. Of course you can describe them. But describe them in terms of what? I think that's the key. Let's say you have a pencil and you want to describe its length, which will be a unit multiplied by a number. If I were to try to describe the true lengt…

"describe them in terms of what?" Decimal system :) Interesting philosophical point though.

Decimal system (well, numbers in general) is a great way to describe things as they provide infinite accuracy both in positive and in negative directions. But you must describe them relative to something - some kind of unit.

So your balloon, to fully described its length, you have chosen to describe it relative to meters. Here's the kicker - how well you can measure the length of the balloon depends also on how well you can measure a meter. In the real world, if you try to measure both, the decimal number that describes how relative a meter is to your balloon will only be limited by how accurate your methods of measuring are. You can develop better measuring technology that will forever approach but never reach the True value (only God knows). It is if you try to measure an analog signal, you can only get a digital estimation. But extracting knowledge requires energy, so you need greater computing power to measure an analog signal but all the computing power in the universe couldn't acquire the True value. This is the result of the real world being nondiscrete and containing infinite knowledge. You can measure things by proportion (such as tau (2*pi) being the relative constant of circle circumference to radius); these numbers are transcendental and we don't know their True value. Your "indescribable" numbers are as indescribable as transcendentals. So yes the decimal goes on forever, but you can still describe it in terms of itself and just give a constant name (like pi).

Re: Indescribable numbers: The theorem that made me fall in love with math

#33

Post by AnthonyMouse »

exit wrote: post #12

reminds me of the berry paradox from wikipedia: "an expression like 'the smallest positive integer not definable in fewer than twelve words' (note that this defining phrase has fewer than twelve words)"

See also Godel's incompleteness theorem (i.e. "this statement is false.")

Re: Indescribable numbers: The theorem that made me fall in love with math

#34

Post by ackien »

ukoto wrote: post #22

They are real numbers, for which we have just proven it is impossible to find a description that will match them. We have proven that no description will ever describe them. Of course you can describe them. But describe them in terms of what? I think that's the key. Let's say you have a pencil and you want to describe its length, which will be a unit multiplied by a number. If I were to try to describe the true lengt…

What you've shown is that that particular number (0.0178.../the length of the pencil in metres) is describable. This isn't the same as showing every real number is describable. There are some numbers which are not the length of anything (in metres), or the mass of anything (in kilograms), or the square root or sin of anything. You could try to capture more numbers by using descriptions like "the length of this pencil in feet" and other made-up units of measurement, but you'll never describe them all.

Re: Indescribable numbers: The theorem that made me fall in love with math

#37

Post by AnthonyMouse »

This is actually an information theory problem which follows directly from the existence of incompressible numbers.

The simple explanation for incompressibility goes something like this: Compression means reversibly mapping longer bitstrings to shorter bitstrings. For each bit you add to the length of a string, you multiply the number of values it can represent by two. That means you cannot uniquely (i.e. reversibly) represent each bitstring having n bits with a bitstring having m bits where n > m, because you run out of unique values of the shorter bitstrings before you have a representation for each of the longer bitstrings. QED.

Now you just apply that to numbers with infinite precision. The number "exactly 4.5" is really 4.5000000… meaning "4.5" followed by an infinite number of zeros. That number, despite having infinite precision, is one we compress into less than infinite storage. Various other numbers (like four and one third) are likewise. But as we just proved, there have to exist some numbers with infinite precision that we don't represent with anything less than an infinite number of symbols.

The interesting thing about this is that you can never say that any specific number is incompressible and thus indescribable. You can take any bitstring (but not all bitstrings) of any length, including infinite, and assign a specific shorter (and finite) bitstring to represent it. You then have a finite encoding for that specific infinite sequence of symbols which can henceforth be used to describe it. You just can't do it for every infinite bitstring because you have insufficiently many finite bitstrings with which to represent them.

Re: Indescribable numbers: The theorem that made me fall in love with math

#38

Post by yk »

DanielBMarkham wrote: post #2

This is good. I really liked it. But just to continue the mind-games, yes there are an infinity more indescribable numbers than there are describable ones, but should there be ? Given the balloon example, he makes the case that as an imaginary god: "...stare imploringly into the siren call of the final ellipsis, for you know that no matter how often you expand it, I will always smile when giving you more and more dig…

I think you have your argument backwards, we use math to describe reality. So whatever axiom system you choose to build your physical theory, there is then some correspondence between the objects of your axiom system and reality. And if you somehow manage to construct a physical theory with integers alone, then there will only be integers in your description.

Interestingly: Indescribable numbers do not appear in physical theories.

Proof: The number would need to be described by the theory in order to have a correspondence to nature.

( None of the above should be constructed as a statement about the existence of Platonic ideals.)

Re: Indescribable numbers: The theorem that made me fall in love with math

#39

Post by [deleted] »

tripzilch wrote: post #11
DanielBMarkham wrote: post #2

This is good. I really liked it. But just to continue the mind-games, yes there are an infinity more indescribable numbers than there are describable ones, but should there be ? Given the balloon example, he makes the case that as an imaginary god: "...stare imploringly into the siren call of the final ellipsis, for you know that no matter how often you expand it, I will always smile when giving you more and more dig…

What you describe has to do with mathematical constructivism[0], and also with the Axiom of Choice, and it's really complicated (to me, I'm not a mathematician, and I only sort-of get it). You may have heard about the Banach-Tarski paradox[1], which tells you that if you assume "Real numbers" are actually reality, and the Axiom of Choice, you can divide a sphere into five pieces (one of which is just a point) and rea…

[deleted]
Post reply on HN