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

How many real numbers exist? New proof moves closer to an answer

quantamagazine.org

Post reply on HN
Print view View original

271–280 of 359 posts

Re: How many real numbers exist? New proof moves closer to an answer

#271

Post by alanbernstein »

DangitBobby wrote: post #244
plus wrote: post #188

Earlier quoted context omitted.

> The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? If it was possible to construct your mapping, then there would be a well-defined sorting of the reals between 0 and 1 based on their integer representation (e.g. we could sort the set {0.05, 0.1, 0.2} => {50, 1, 2} to [0.1, 0.2, 0.05] => [1, 2, 50]). Ho…

> then there would be a well-defined sorting of the reals between 0 and 1 based on their integer representation Why is that?

Because the integers are ordered?

Re: How many real numbers exist? New proof moves closer to an answer

#272

Post by phkahler »

perfunctory wrote: post #264
phkahler wrote: post #163

You can map all the real numbers to the interval 0 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.

> simply write it's trailing digits in reverse order so how do you map say pi/4? Which digit do you start with?

That would be:

...61893587

We start writing the digits right to left an pi/4 is about 0.78539816...

Re: How many real numbers exist? New proof moves closer to an answer

#273

Post by sharpener »

curtisf wrote: post #224
sharpener wrote: post #184

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finit…

This presents a confused understanding of Cantor's diagonalization argument. You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic…

> Theorem: There is no bijection between ℕ and {0, 1}*.

So no bijection between \bb{N} in an unspecified number base and some binary strings that could represent integers? That's a nonstarter for me.

Please read my article. Thanks.

Re: How many real numbers exist? New proof moves closer to an answer

#274

Post by myWindoonn »

sharpener wrote: post #273
curtisf wrote: post #224

Earlier quoted context omitted.

This presents a confused understanding of Cantor's diagonalization argument. You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic…

> Theorem: There is no bijection between ℕ and {0, 1}*. So no bijection between \bb{N} in an unspecified number base and some binary strings that could represent integers? That's a nonstarter for me. Please read my article. Thanks.

You misread their type. There is no bijection N -> (N -> 2); {0,1}* = 2* = N -> 2.

Note that the given proof is a version of Lawvere's fixed-point theorem. The trick is noticing that for some x : N, f : N -> (N -> 2) can be applied onto it twice, giving f(x) : N -> 2 and f(x)(x) : 2.

Note further that infinite binary strings don't just represent natural numbers. Indeed, every natural number has a finite binary string, and that is the bijection that you're imagining. The question is, which natural number is represented by 111...? This leads to the difference between the natural numbers, their one-point compactification, and Cantor space in terms of searchability. Escardó has an article on this: http://math.andrej.com/2007/09/28/seemingly-impossible-funct...

Please read Lawvere's article. Thanks.

Re: How many real numbers exist? New proof moves closer to an answer

#275

Post by myWindoonn »

sharpener wrote: post #260
curtisf wrote: post #224

Earlier quoted context omitted.

This presents a confused understanding of Cantor's diagonalization argument. You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic…

> Define a function z(n) = 1 - f(n)(n). I don't understand the notation f(n)(n). Is it related to f_{nn} in LaTeX notation? Your later text suggests maybe it was aiming at f(n,n) so I will assume that. I recognise a form of this argument and I might have tackled it in the supplementary materials I created that are referenced in the article. Let me know. > However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).…

For future readers: z cannot return 0.5. z can only return 0 or 1. This is because z is closed over a function which returns 0 or 1, and inverts it to return 1 or 0.

This should remind folks of both Turing's Halting problem and Russell's paradox. z takes some f which claims to be a bijection (claims to Halt, claims to be a set of all sets) and finds a way to call f against a witness constructed from f.

Re: How many real numbers exist? New proof moves closer to an answer

#276

Post by perfunctory »

phkahler wrote: post #272
perfunctory wrote: post #264

Earlier quoted context omitted.

> simply write it's trailing digits in reverse order so how do you map say pi/4? Which digit do you start with?

That would be: ...61893587 We start writing the digits right to left an pi/4 is about 0.78539816...

So you found a flaw in Cantor's diagonal argument?

https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Re: How many real numbers exist? New proof moves closer to an answer

#277

Post by HotHotLava »

BoiledCabbage wrote: post #28
pavpanchekha wrote: post #4

Great article. Since it looks like a lot of folks are interested in this article, some extra background. First, what is forcing? The article actually has a great description of ultrapowers (a key part of the construction) but it goes by a little fast, so you might like Tim Chow's "A beginner's guide to forcing" [1] which does a good job not only laying out the mathematical details at a high level, but also really cle…

Why does forcing work? To me it seems flawed (which obviously means I don't understand it fully). For diagonalization argument: 1) Assume every real can be assigned a natural number. 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then…

The illustration in the article doesn't start with the whole set of all real numbers, but with just "a" set containing an uncountable number of reals, so there is no contradiction in that sense.

I'm assuming there's some unmentioned technical condition on which sets you are allowed to choose in order for the procedure to work, otherwise the argument would indeed seem to lead to a contradiction when choosing the set of all real numbers.

Re: How many real numbers exist? New proof moves closer to an answer

#278

Post by sharpener »

myWindoonn wrote: post #217
sharpener wrote: post #184

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finit…

Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 explains with many examples. Hi…

I'm not seeing this yet. Perhaps you could explain it to me in plain terms.

Re: How many real numbers exist? New proof moves closer to an answer

#279

Post by kkylin »

Those with a bit more math background may enjoy Cohen's own perspective on the discovery of forcing: https://projecteuclid.org/journals/rocky-mountain-journal-of...

(Not technical as these things go, but helps to have a little knowledge of logic / set theory and some amount of "mathematical maturity.")

Re: How many real numbers exist? New proof moves closer to an answer

#280

Post by bonoboTP »

IshKebab wrote: post #269
dwohnitmok wrote: post #156

Earlier quoted context omitted.

The Continuum Hypothesis and its negation are both proven to be consistent with ZFC (this is what the article is talking about RE forcing and Godel's proof of the consistency of CH). There is no contradiction to assume one or the other alongside ZFC. The article is really talking about Platonic truth when it talks about something being true or false. > Individually, or independently, axioms have no truth value. Indee…

Isn't that what an axiom is though? Something you have to define as true? The way you've described it, Platonism makes no sense. Maybe there's a missing part of the explanation...

Platonists think you can define them wrong if you're careless.

Imagine having a spreadsheet with the population of each country. I can go and enter 1 billion for the US, and the spreadsheet will happily recalculate all the cells about, say, GDP per capita etc. based on my incorrectly modified input. Clearly just because I've set the US population value in my spreadsheet to 1 billion the actual population did not change. There is a real population count and if we don't use the correct one then all our output will be garbage too: garbage in, garbage out.

Mathematics is like this spreadsheet, its input are the axioms and the outputs are various interesting theorems. Feed in wrong axioms and you get wrong theorems.

Platonists believe in a realm of ideas, that math talks about something real, just like the spreadsheet talks about real human populations. Even though within the spreadsheet everything remains fine and consistent if I tweak the US population. It just doesn't correspond any more to reality.

I myself am not a mathematical Platonist, I more of an engineer/practical person and see math as a survival tool of a bunch of primates on a rock floating in space, not something that taps into anything mystical.

But the Platonist worldview also seems coherent.

Post reply on HN