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

101–110 of 359 posts

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

#101

Post by lupire »

bmitc wrote: post #47
thom wrote: post #27

Earlier quoted context omitted.

Why does “the set containing the natural numbers and a sandwich” not have cardinality between the two?

The non-sandwich analogy is called Hilbert’s hotel. Saying that two sets have the same cardinality is equivalent to them having a bijection between them. So the claim is that the natural numbers and the natural numbers plus a sandwich have the same cardinality. This can be proved by the bijection: 0 -> sandwich 1 -> 0 2 -> 1 3 -> 2 . . . n -> n-1 . . . There is actually more though! If you had an infinite but countab…

Don't stop there! Let's have a countably infinite variety of sandwiches, with a countably infinite number of sandwiches of each variety.

Still enough natural numbers to eat them all, one per.

But still not enough sandwiches to feed all the (so-called) real numbers one sandwich each!

But if sandwiches grew on trees, and we had an infinite branching tree with two branches at each branching point, and every branch has a (pair of) sub-branches, then natural numbers could not eat all the sandwiches, and the sandwiches could feel all the (so-called) real numbers.

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

#102

Post by rssoconnor »

lupire wrote: post #90
rssoconnor wrote: post #65

Earlier quoted context omitted.

> but at the same time there is no "right answer"—all of these axioms, after all, are independent of ZFC, and it's "ok" to add any of them. Minor quible: Just because a potential axiom is independent of ZF(C) doesn't make it necessarily "okay" to add. Potential axioms can be unsound, for example if they prove new / untrue Sigma_1 statements. As an example, even in the likely circumstance that ¬Con(ZFC) is independent…

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

Mostly because it implies that some Turing machines halt that actually do not halt. That is unless you are willing to accept that a Turing machine can halt in some number of steps that is beyond any number that can be written. And I don't mean can't be written in the sense that we don't have enough paper. Just cannot be written in principle at all by our notation for numbers.

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

#104

Post by lupire »

pjfin123 wrote: post #64
jaywalk wrote: post #8

I'm not trying to be flippant, although it may come off that way: why does any of this matter?

I understand the diagnol proof but not a lot of the rest. If you assume only computable numbers exist though a lot of this seems to really not matter.

Even if only computable numbers exist, it's inconvenient, to do math on them in bulk, so it helps to have a set of virtual/potential numbers (misleadingly named the "real" numbers, even though almost all of them (100%) will never be realized in any way).

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

#105

Post by scapp »

btilly wrote: post #88

As a constructivist I'll be over in the corner that says that there are only a countable number of real numbers, and the unimaginable number of unimaginable infinities that classical mathematics insiste exists is all made up nonsense. That, in fact, things that can't ever be named, even in principle, don't actually exist. What is interesting is that as shocking as constructivism may be, there is no logical flaw in it…

You sound like you need to read this [0] answer to the question "Are real numbers countable in constructive mathematics?".

> You are using the word "constructive" in an unusual way. It is true that, in ZFC, the set of computable real numbers is countable, but that is not directly a statement about constructive mathematics.

> Not every school of constructive mathematics identifies real numbers with algorithms; that's a characteristic of the "Russian" school as I understand it. In other schools of constructivism that I am more familiar with, real numbers are coded by elements of 2^ω, or by a certain type of Dedekind cut on the rationals. In such schools it is not universally assumed that every real number is associated with a finite algorithm.

> Even in the Russian school, they would not say that the set of real numbers is countable. Because, if you identify real numbers with algorithms, there is no computable enumeration of computable reals that lists all computable reals, and so the translation of "the real numbers are countable" into this setting is false.

> That phenomenon also occurs in classical computable analysis. The subsystem RCA0 of second-order arithmetic has a model in which every real number is computable. But this subsystem still proves that there is no surjection N -> R.

---

It's worth noting that another answer to that question (Andrej Bauer's) gives a constructive proof that the real numbers are uncountable using with the axiom of countable choice. The question of whether it's provable without the axiom of countable choice is open (though see this [1] fairly recent paper on a proof for MacNeille reals).

[0] https://mathoverflow.net/questions/30643/are-real-numbers-co...

[1] https://arxiv.org/abs/1902.07366

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

#106

Post by Hamlet42 »

jaywalk wrote: post #8

I'm not trying to be flippant, although it may come off that way: why does any of this matter?

Some math problems seem uselees when first encountered until they become useful some dacades later. An example of this is knot theory and medicine[1]

[1] https://science.sciencemag.org/content/255/5043/403

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

#107

Post by dwohnitmok »

dogecoinbase wrote: post #95
lupire wrote: post #90

Earlier quoted context omitted.

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

Soundness in this sense (sigma_1 soundness) is defined by equivalency to the standard model (specifically, all sentences provable in the system must be provable in the standard model).

It is defined by equivalency to a standard model. Whether there is a single standard model is a philosophical question (which granted most, but not all, set theorists tend to agree with). Hence sigma_1 soundness is from a purely mathematical point of view a relative statement.

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

#108

Post by kevinventullo »

schoen wrote: post #77
sillysaurusx wrote: post #69

Earlier quoted context omitted.

That was another question in the back of my mind -- famously, the four color theorem was proved by computers through exhaustive analysis (checking every possibility). At the time, it was controversial as a "proof" since it didn't really take the usual form of a proof. I've often wondered "Why can't we do something like that, but for all instances of things like the Collatz conjecture?" Of course, it's computationally…

The four-color theorem had the preliminary challenge of creating a method to identify all the relevant cases. That also required a mathematical theory. (I don't actually understand how it was done!) If you didn't have that, you would have an infinite search for possible maps that violate the conjecture, because you wouldn't be able to divide them into a finite number of equivalence classes, or enumerate a finite numb…

As an interesting example where we did have a finite bound that was still out of reach to computationally exhaust, see the Weak Goldbach Conjecture:

https://en.m.wikipedia.org/wiki/Goldbach%27s_weak_conjecture

It was known to have at most finitely many counter-examples by the 1930’s, and by the 1950’s it was known that the largest counter-example had to be Only in 2012 was an unconditional proof given.

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

#109

Post by mmmBacon »

Maybe I misunderstood the article but if the set of real numbers is finite then it should be countable. But I can easily prove that the set of real numbers or any subset of real numbers is not countable. Been a really long time since I’ve thought about this but wondering what I’m missing.

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

#110

Post by dwohnitmok »

lupire wrote: post #90
rssoconnor wrote: post #65

Earlier quoted context omitted.

> but at the same time there is no "right answer"—all of these axioms, after all, are independent of ZFC, and it's "ok" to add any of them. Minor quible: Just because a potential axiom is independent of ZF(C) doesn't make it necessarily "okay" to add. Potential axioms can be unsound, for example if they prove new / untrue Sigma_1 statements. As an example, even in the likely circumstance that ¬Con(ZFC) is independent…

why is that "unsound"? what's wrong with an unwritable natural? Almost all reals are unwritable.

This is not unsound in the usual sense of "logical soundness" (which applies to logical systems such as first-order logic, rather than specific theories in the system such as ZFC).

This is unsound in that it runs counter to certain philosophical commitments, namely that there should be some tangible, physical realization of all the natural numbers (although if you really go far in that direction you end up with ultrafinitism, which most set theorists would find unpalatable, so the philosophical implications of all this are rather tricky).

Post reply on HN