How many real numbers exist? New proof moves closer to an answer (2021)
quantamagazine.org
quantamagazine.org
How many real numbers exist? New proof moves closer to an answer - https://news.ycombinator.com/item?id=27845576 - July 2021 (344 comments)
(Reposts are fine after a year or so! especially for a great article like this. Links to past threads are just to satisfy extra-curious readers)
> How many real numbers exist? New proof moves closer to an answer
and the subhed:
> For 50 years, mathematicians have believed that the total number of real numbers is unknowable. A new proof suggests otherwise.
both suggest a mystery that isn't there. Not that there isn't a mystery—there is!—but I think it's unreasonable to describe it as the title and subhed do.
As the rest of the article, which is at Quanta's usual excellent expository standard, explains, there is absolutely no debate about the number of real numbers; it is 2^{\aleph_0}. You don't have to know what that is, but it is important to know that it is a definite, precise answer. You can ask whether it's the same as \aleph_1, and that's something we don't know. But that doesn't mean that we don't know the answer to how many reals there are, only that we don't know whether some other potential answer is also the answer.
But the notation, and probably the theory, suggest otherwise, in which case saying there are 2^{ℵ₀} reals might be a bit like saying that there are |ℝ| reals. But I feel like I’m being pedantic regardless.
> But the notation, and probably the theory, suggest otherwise, in which case saying there are 2^{ℵ₀} reals might be a bit like saying that there are |ℝ| reals.
That's a good point, but, interestingly, and as you doubtless know, this article points out a rigorous sense in which it's the other way around: we know very explicitly at least two sets whose size we know is 2^{\aleph_0}, whereas we don't know any whose size we know is \aleph_1!
The definition with which I am familiar is that \aleph_1 is the least cardinal that is strictly greater than \aleph_0, but, of course, one can use any of an equivalent collection of properties as the definition.
Nonetheless, at least any definition in line with usual mathematical practice should probably not provably require that \aleph_1 is at least 2^{\aleph_0}, which I claim that your definition does. Let me refer to positive integers, and non-negative integers, to avoid having to commit to what the natural numbers are. I define a function from the power set of the positive integers to the set of total orderings of the non-negative integers as follows. For every power set A, write B for the complement of A in the positive integers, and let <_A be the order that restricts to the usual order on A and on B (though not on their union), and that declares 0 to be greater than every element of A and less than every element of B. Since the usual order on the positive integers is a well order, so is <_A. Clearly, A may be recovered from <_A (as the set of elements preceding 0), so the function is injective.
A factual head line is very much sufficient to get the readers interest.
Now the computable reals, on the other hand... maybe.
There is not a single set of definable reals, since different formal languages produce different sets (e.g. there are reals definable in second order logic but not first order logic). But, given any formal language composed of finite sentences from a finite alphabet, the set of sentences in the language is countable so the corresponding set of definable reals is too.
The definable reals are all the reals we can talk about individually. (Well, there are some definable reals we can’t in practice talk about individually-e.g. those for which the shortest sentence uniquely identifying them is too long to fit in this physical universe.) Undefinable reals are an uncountable amorphous mass we can only discuss collectively, we can’t refer to any of them as individuals.
Now, you can object to “natural language definability” as lacking “concreteness” since maybe it can’t be formalised, but then the claim in your comment can’t be formalised either…
Actually, are we sure natural language can’t be formalised? Obviously any formalisation of natural language has to be paraconsistent (maybe even dialetheic) rather than consistent, but granted that…
But still my intuition is that for any consistent formal system I should be able to find a more powerful system that can express strictly more things, even if my argument above was silly. But I don’t think we can talk about the set of things that can be defined in natural language in any meaningful way.
The problem with defining more and more powerful systems is that we have an arbitrary selection of axioms to choose from. For example, if we start with the Peano axioms and define a Goedel sentence (i.e. a specific instance of "this sentence cannot be proven"), then we can choose to extend that system either by adding that sentence as an axiom, or adding its negation as an axiom. Both would result in a consistent system. Then we can define a Goedel sentence in that system, and make a more powerful system by making that or its negation an axiom. And so on.
This process of choosing new axioms does make our formal system strictly more powerful (it can prove/refute sentences which were unprovable in the weaker systems, and their consequences); but it's not very useful or interesting, since we're just arbitrarily choosing whether those extra sentences should be provable or not.
This is related to the fact that any particular formal system can only compute a few digits of Chaitin's constant (since we can only ever solve the halting problem for a subset of all possible programs). We can consistently extend our chosen system by specifying subsequent digits as axioms, but that doesn't really tell us anything; we're just asserting it, for no particular reason one way or another.
Relating that to "definable" numbers, it seems I've probably missed some subtlety with Chaitin's constant: since (a) defining extra digits via axioms seems to be adding (algorithmic) information to our system, so defining all of its digits seems to give infinite information; yet (b) it's trivial to do this in a finite way, like "all subsequent digits are zero". Maybe I'll think about this more, but it seems like my intuition is a bit off (this area of mathematics is notoriously nuanced).
It seems to run into the same sort of thing that led to ZF axioms, namely that you can have a language that is a bit too "loose" and therefore leads to contradictions. I think Kurt Godel showed that any non-trivial language is going to have something like that.
Like, what is the first positive real?
If you have to involve infinitesimals or something, I think it's perfectly fine for you to be able to take the definable reals and then extend them in that way. it doesn't invalidate the idea of a "definable" real.
Though the (im)possibility of well-ordering all reals doesn't really matter here. Computable reals can by sorted by their programs, and definable reals can be sorted by their definitions. So if you have a "concrete definition of definable reals", then the system you use gives you ways to well-order them. And if you want to "refer to the first real that’s undefinable in that system", you can make a new system2 that encapsulates the old system1.
That might prove we can't have a universal system for defining things, which would be disappointing but workable.
Or maybe it's just that "the first real that's undefinable in system1" is not concrete, so we can reject it as a description of a number, and then the consequences are much smaller.
One can even (consistently) append the negation of the axiom of choice to ZF, in which case this theorem is false. Mere negation of the axiom of choice is not a very interesting addition, but there are some interesting alternative axioms, such as the axiom of determinacy, which have negation of the axiom of choice as a consequence
People who are fixated on definable/computable reals generally have constructivist sympathies, and many (but not all) constructivist mathematicians reject the axiom of choice. So relying on it in arguments in this context is questionable.
https://mathoverflow.net/questions/119561/mathematics-with-t...
In general, you also can’t use Cantor’s diagonal argument on the list of definable reals because there are numbers in there that aren’t computable.
If a number can be defined in a language but you can't tell me if it's different from another number that I have in finite time, then it is not very interesting to me.
Consider an irrational number, where the fastest possible algorithm (given a standard Turing machine) to compute its nth digit requires (10^(10^100))*(n+1) operations. Now, by the standard definition, such a number is computable – but in practice, we will never be able to compute even its first digit. In practice, its first digit is just as unknowable to us as the first uncomputable digit of (any instantiation of) Chaitin's constant is.
"Computable" by the standard definition is unphysical, because it includes computations that require unphysically large amounts of time and space. Now, many uncomputable (by the standard definition) numbers can be computed by a hypercomputer (such as a Turing machine with an oracle, or a computer which can execute supertasks) – hypercomputers are unphysical, but "standard" computers (in the mathematical sense) are unphysical too. Why denounce one form of unphysicality but not another? It would seem to be more consistent to either embrace the unphysicality of mathematics and imbibe the psychedelic broth of the Cantorian paradise, or else reject unphysicality entirely and embrace ultrafinitism. The "infinity is verboten but unphysically large finitudes are A-okay" approach of (non-ultrafinitist) construcitivsm/intuitionism seems rather arbitrary.
> If a number can be defined in a language but you can't tell me if it's different from another number that I have in finite time, then it is not very interesting to me.
If a number can be defined in a language but I can't tell you whether it's different from another number that you have in a physical amount of time (let's say less than the age of the universe), is it interesting to you?
There can be no such number. You can always make a Turing machine output initial digits faster by adding some more states to do so.
Let's denote the nth prime by P(n). Now, consider the real number Q, where 0.0 < Q < 1.0, and the nth decimal digit (after the decimal point) of Q, Q(n), is given by Q(n) = P(10^(10^100) + n) mod 10. Q, as defined, is computable, but (unless we discover some mathematical "shortcut" for computing the last digit of a prime number), I doubt we are ever going to know what even its first digit is (well, we know it must be 1, 3, 7 or 9–but which of those four?). And even if some such "shortcut" were discovered, I'm sure someone could cook up another such number for which there is no known "shortcut".
How about this: let N(n) be any FNP-complete [FNP is to function problems what NP is to decision problems] computable endofunction of the natural numbers (there are many to choose from, pick any), then define:
Q(n) = P(N(10^(10^100) + n)) mod 10
You actually think we'll ever know the first digit of the real number so defined?
The reason I've latched onto it is that I read about the idea that in constructive mathematics all functions are continuous, basically because you can't tell that they're not continuous (because to tell that would imply you could inspect infinite digits of function's inputs and tell that they lead to discontinuities in the outputs). I quite like that idea because it rhymes with the intuition that nature doesn't care about later digits of numbers either, and that properties of the real numbers like being uncountable, dense, etc cannot show up in any physical system and therefore aren't "real".
But I'm definitely looking for a better way of understanding this, so curious if you can suggest anything.
From what I understand, it is more that most systems of intuitionistic/constructive logic can't prove the existence of a discontinuous real function – but nor can they disprove it. They have models both in which such functions exist, and also models in which they don't.
https://math.stackexchange.com/questions/176279/all-real-fun...
It always seemed like it should matter that the constructable formula strings include strings that define multiple numbers (e.g. "three; also pi squared") which at least seems like it should be aleph one rather than aleph nought, but smarter people than me assure me it doesn't work that way for (reasons)
and countable infinity is already the smallest one, so you can't get smaller
But for any particular real it is much more tenuous. You can't produce any physical system that demonstrates almost all real numbers in any way. Some of them obey equations so you can talk about 'the solution to this equation', which is real enough. But most of them are inaccessible, even in principle, and I think the only reason people default to thinking they have the same existence as like, integers, is because we're taught them early enough that we don't question it.
I take issue with this paragraph. It makes it sound like the infinitude of reals between 1 and 1.00001 is proof there are more reals than naturals. One might think this same fact proves that there are more rationals than naturals...
I've talked to a friend with a doctorate in algebraic geometry about this several times, but all I've really gotten out of her is that if I studied a lot more math, I would gradually get the same sense.
(For reference, I have about as much mathematics background as a US student who minored in maths.)
I wonder if this is a map/territory thing. Incompleteness theorems apply to models (axiomatisations) of mathematics, e.g. ZFC set theory. Platonism applies to the actual act of doing mathematics, i.e. persuading other mathematicians that certain statements about abstract entities are true or false.
Like that spheres are real even though there is no perfect sphere in the material world.
This is a common opinion among mathematicians and physicists even though it seems unscientific (as it poses reality beyond matter)
https://news.ycombinator.com/item?id=27846084
links to a two-part paper called "Believing the axioms", part 1:
https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf
I have only taken a short look and am not qualified to summarize, but it seems this would have an answer if there is one.
I don't think they really are evidence against it. The first incompleteness theorem says (to put it simply) there are truths about the natural numbers you can't prove, and (if we equate proof with knowledge) can't know. I don't know why a Platonist would find that objectionable. I mean, naïve materialism would imply there are lots of facts about the material world we are never going to be able to know (e.g. the particular arrangement of rocks on a lifeless planet in a distant galaxy right now, or as close to right now as relativity permits). If unknowable truths isn't evidence against materialism, why would it be evidence against Platonism?
Really, Gödel's theorems were a much bigger problem for formalism than Platonism. Formalists wanted to identify mathematical truth with provability, and Gödel shattered that dream. Platonists never dreamt the dream, so its destruction didn't discourage them.
But now let's divide each element of E by 2 to produce a set D. Now that set D is {1, 2, 3, ...} aka N the natural numbers. But we just applied a function to each element of E, so how can D have a different size than E? Each element of E maps to exactly one element of D: 2 -> 1, 4 -> 2, 6 -> 3, etc. So does size(D) = size(E)? Or does size(D) = size(N)?
I imagine you're right that this leads to a contradiction somewhere, but I (obviously) haven't thought it through. I just would love to see someone try to break enough axioms to make it work and see what comes out of it, or show that it contradicts either itself or something we see in the real world if we do that.
But yes, the ordinals might be more to your liking. If you equip your sets with more structure you can say more things about them.
You are assuming that this doesn't change the size and certainly that's how the normal notion of size works. But the question is whether we can create any order relationship on the sets with the desired properties.
The properties he mentioned defines a partial order and partial orders can be extended to total orders (given axiom of choice). So it is in fact possible.
But a partial order of all sets? How is this function "size" even defined? Functions don't have a domain of all sets in conventional set theory.
There are also ordinals, which are much finer than cardinals but have the disadvantage that they only apply to well-ordered sets, and ordinal arithmetic works very different to the naturals.
And then a final one - exotic models of the real numbers like the surreals contain infinite quantities of different sizes that can be compared, divided, added just as you like and the order relation works intuitively. The disadvantage here is that they are generally harder to define and reason about than the ordinary reals. The reason people like them is that you they contain infinitesmals too, which you can use to formalise an alternative foundation for calculus.
(although strictly speaking this last one isn't about sets and sizes, it's in a similar cluster of ideas about infinite arithmetic)
tl;dr^2: Mentally move the hyphen one word to the right.
This is talking about the cardinalities of very basic sets, and it was (is? haha) extremely unclear to what extent statements about them are independent, if at all. I would personally be shocked if you can prove independence of CH directly from the incompleteness theorem, though I would love to be wrong! It required a lot more delicate machinery to be developed (Cohen's forcing method).
Numbers certainly exist in a useful sense - they model real properties of the universe. But I agree that higher set theories may be moving away from that...