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

71–80 of 91 posts

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

#71

Post by tome »

graycat wrote: post #63
tome wrote: post #41

Earlier quoted context omitted.

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

"Credible", likely yes. Likely also awkward. To weasel out, I just said we "want completeness". When you look at the alternatives, you may conclude that you still want completeness and, thus, are stuck with the reals with no alternative you "want"!

Awkward I would agree with, but probably only because we're much more used to the usual approach (cf the "awkwardness" of Haskell).

Still, you'll see in that paper that the reals he constructs are complete. The get out clause is that they are not a set, but a class.

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

#72

Post by saraid216 »

graycat wrote: post #62
garysweaver wrote: post #55

Earlier quoted context omitted.

> God made the integers. All else is man made. "God made natural numbers; all else is the work of man" - Leopold Kronecker. Possibly misquoted by Raymond Ayoub in "Musings of the Masters: An Anthology of Mathematical Reflections".

Thanks! I wanted to say natural numbers but thought that the original quote was the integers. No excuse! Should have at least tried to Google the quote instead of just typing quickly from undergraduate school memory!

Stephen Hawking appears to disagree with garysweaver:

http://en.wikipedia.org/wiki/God_Created_the_Integers

Not that Hawking is intrinsically more qualified.

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

#73

Post by xyzzyz »

gjm11 wrote: post #59
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,…

> it was proved by Cantor and Cohen Goedel and Cohen. Goedel proved it might be (constructible universe); Cohen proved it might not be (forcing). I think Cohen's on record as saying he suspects that with the "right" axioms, mathematicians might come to think that CH is obviously false .

Ah, of course, I don't know why I have written Cantor. It's too late to edit now.

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

#75

Post by ColinWright »

csense wrote: post #65
ColinWright wrote: post #49

Earlier quoted context omitted.

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…

You're misunderstanding the theorem the author proved. Theorem A (author's theorem): No mapping from finite-length strings to real numbers will hit all the real numbers. Theorem B (your theorem): Let's map strings of finite length to real numbers as follows: Consider the string as the specification for a Turing machine. If the specification is syntactically OK as a Turing machine description, and the output is syntac…

You're right, although I wasn't so much misunderstanding, as misremembering. As so often happens, there's been a flurry of similar comments, and I mis-remembered what had been said, and hadn't re-read before commenting.

Apologies.

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

#76

Post by waterhouse »

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)"

I thought of that too. Which leads me to think that the proof status of the OP's "theorem" is less clear. You cannot exhibit a deterministic algorithm that maps every English phrase to the integer that phrase describes, unless you are prepared to accept that some phrases like "the smallest positive integer not definable in fewer than twelve words", are meaningless or illegal. (The thing is, once you exhibit such a mapping, that phrase immediately obtains an obvious meaning, and so it "should" be included in the domain, which would then lead to a contradiction... so you will be stuck with an obviously deficient mapping.)

In that case, I'm not sure if you could write a formally rigorous proof in English. You might come up with some rule to monster-bar such meta-descriptive phrases as "the smallest positive integer not definable ..."; I suspect many such rules, perhaps all of them, would rule out the meta-descriptive language needed to state the conclusion. (How do you formally define "describable" without exhibiting an algorithm that computes integers from their descriptions? Perhaps you'd be satisfied by merely constraining what "describable" could mean...) Even if there are a few such rules under which the proof is valid English, is it not kind of arbitrary which rule you choose, and kind of empty to say "I proclaim this choice to be the right one, and then my proof is valid"?

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

#77

Post by aufreak3 »

The charming bit of this story shows something I think should be part of any education - the most fun we have is when we go out and think about things and discover stuff on our own. Getting on to this path is the sure fire way to get out of the "grades game" that college can get you into playing.

I have notes of discovering[1] the Cauchy-Riemann equations for f(z) before I had any clear notion of analyticity or whatever. Gosh! What adrenaline flows!

[1] Deliberate choice here, instead of "rediscovering".

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

#78

Post by VLM »

The social-cultural construct of the whole EE to Math conversion makes the story interesting, and has not been commented on.

An EE who focuses on infinite decimal places doesn't belong in EE at all. That push out is at least as strong as the attraction into math that everyone else caught.

To qualify the push out, an affection for unreasonable / ridiculous sig figs leads to junior EEs having arguments like "I'm not going to approve this power on indicator LED bias resistor value unless its precisely 72.66 ohms using a 0.01 precision resistor because that's what I got with a SPICE run using datasheets, none of this preferred value "82 ohm 10% tolerance 1/4 watt metal film" stuff". You can tell those guys in the lab, because they use uncalibrated three digit multi meters but write down all 10+ digits off their calculator.

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

#79

Post by tripzilch »

tel wrote: post #26
tripzilch wrote: post #11

Earlier quoted context omitted.

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…

Constructivism is significantly more fundamental than AC. AC is notable for being famously perplexing, less foundationally perplexing. For a more graspable investigation of the perplexities and arbitrariness of our choice of foundational set theory, take a look at Vicious Cycles where the author investigates what happens when set theory does not assume a terminating world (and thus introduces a lot of things that we…

"Costa, not data", what does that mean?

And Vicious Cycles is a book, I presume? Who is the author?

Post reply on HN