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

41–50 of 91 posts

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

#41

Post by tome »

graycat wrote: post #19
tome wrote: post #17

Earlier quoted context omitted.

> In particular, man made the real numbers to be complete which means that every sequence that appears to converge, that is, meets, the Cauchy criterion, actually does converge. Indeed, but by the same argument as the author's, there are more Cauchy sequences than can be described, so it looks like the real numbers are much bigger than necessary to do mathematics :)

No, to "do mathematics", e.g., show that the Riemann integral exists, that e and pi exist, etc., we want completeness. Then we are done: The reals are the only complete Archemedean ordered field! So, we have no choice!

I'm afraid I'm not a good enough logician to answer your objection properly, but there are, I believe, credible approaches to doing mathematics on a countable carrier set, for example:

http://arxiv.org/pdf/math/0509245

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

#42

Post by ColinWright »

justinpombrio wrote: post #28
graycat wrote: post #19

Earlier quoted context omitted.

No, to "do mathematics", e.g., show that the Riemann integral exists, that e and pi exist, etc., we want completeness. Then we are done: The reals are the only complete Archemedean ordered field! So, we have no choice!

On the contrary, we do have a choice! We could use computable numbers instead of reals. A computable number is any number which is output by some Turing machine, or, equivalently, any number which can be found by some algorithm. e and pi are computable. You are right that Riemann integrals won't exist, but if you modify definitions somewhat, derivatives and integrals can be defined just as easily for computable numbe…

Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc.

Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration.

The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound.

And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers.

This proves the computable numbers are not complete, and that makes analysis really messy.

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

#43

Post by csense »

I didn't think that dating this theorem to the 1940's was accurate. This was originally proved by Cantor in 1874 [1]. Cantor's work was well-known (and highly controversial) during his lifetime [2].

[1] http://en.wikipedia.org/wiki/Uncountability_of_the_real_numb...

[2] http://en.wikipedia.org/wiki/Georg_Cantor

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

#44

Post by cousin_it »

xyzzyz wrote: post #20

The interesting thing here is that it's much harder to put this problem properly into mathematical terms than it is to solve it. The whole insight here is that you a "description" of number is just some finite sequence of symbols from a finite alphabet. Now, if you understand why cardinality of continuum is greater than aleph null, it's totally straightforward to show that there are only countably many descriptions,…

Interestingly, for any method of describing real numbers (i.e. mapping from finite strings to real numbers), the diagonal argument gives an explicit description of a single number that's undescribable by that method. Just out of reach, so to speak.

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

#45

Post by cousin_it »

mkl wrote: post #10
[deleted] wrote: post #7

[deleted]

The point is that there are more real numbers than possible finite descriptions, so some real numbers must be indescribable. Related (and more precisely defined) concepts include (non)definable and (non)computable numbers, http://en.wikipedia.org/wiki/Definable_number and http://en.wikipedia.org/wiki/Computable_number respectively.

Cool, I only just realized that applying the diagonal argument to computable numbers leads to the halting problem, and applying the diagonal argument to definable numbers leads to Tarski's undefinability of truth.

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

#48

Post by chinpokomon »

ColinDabritz wrote: post #13

Excellent article. If you like this sort of thing, you may enjoy Busy Beaver numbers, my favorite treatment of which is the essay "Who Can Name the Bigger Number?" http://www.scottaaronson.com/writings/bignumbers.html

Thank you for this resource. I hadn't formally been exposed to tetration, but I had recently been pondering the concept, I guess in the same way Ackermann came up with his sequence. I'm so glad to know that this isn't uncharted territory in mathematics, and I now have more knowledge with which to frame my thought experiments.

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

#49

Post by ColinWright »

csense wrote: post #43

I didn't think that dating this theorem to the 1940's was accurate. This was originally proved by Cantor in 1874 [1]. Cantor's work was well-known (and highly controversial) during his lifetime [2]. [1] http://en.wikipedia.org/wiki/Uncountability_of_the_real_numb... [2] http://en.wikipedia.org/wiki/Georg_Cantor

The theorem(s) about uncomputable numbers do date back only as far as the 1940's, because that's when computability was first being discovered/invented. Yes, the point about there being uncountably many reals dates back to Cantor, but that's a different theorem, and a different proof. The existence of uncomputable numbers follows as a corollary from Cantor's first proof of 1874, but the conclusion must be drawn - it wasn't there in Cantor's work.

Specifically:

We can prove that there are uncomputable numbers simply by noting that the number of Turing machines is countable, so the number of computable numbers is countable. Since there are uncountably many reals (by Cantor - 1874) then we can conclude that there are numbers that cannot be produced by a Turing machine.

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

#50

Post by ColinDabritz »

chinpokomon wrote: post #48
ColinDabritz wrote: post #13

Excellent article. If you like this sort of thing, you may enjoy Busy Beaver numbers, my favorite treatment of which is the essay "Who Can Name the Bigger Number?" http://www.scottaaronson.com/writings/bignumbers.html

Thank you for this resource. I hadn't formally been exposed to tetration, but I had recently been pondering the concept, I guess in the same way Ackermann came up with his sequence. I'm so glad to know that this isn't uncharted territory in mathematics, and I now have more knowledge with which to frame my thought experiments.

Graham's number - for a while, the largest number used in a proof: https://www.youtube.com/watch?v=XTeJ64KD5cg

There are faster growing sequences as well, see: http://math.stackexchange.com/questions/2497/what-is-the-big...

both fun as well.

But busy beaver consumes them all.

Post reply on HN