7 ms·

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

58 points by lisper 2y ago

dang 2y ago
Discussed at the time: How many real numbers exist? New proof moves closer to an answer - https://news.ycombinator.com/item?id=27845576 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)
JadeNB 2y ago
The title: > 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.
- dullcrisp 2y ago
  I had the same initial reaction, because in my mind 2^{ℵ₀} is a more fundamental concept than ℵ₁. 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.
  - JadeNB 2y ago
    > I had the same initial reaction, because in my mind 2^{ℵ₀} is a more fundamental concept than ℵ₁. > 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!
    - dullcrisp 2y ago
      I believe that it’s defined as the size of ω₁, the set of wellorderings of the natural numbers. I don’t think there’s any real sense in which that’s less of a concrete set than the power set of the natural numbers, even if it’s harder to picture.
      - JadeNB 2y ago
        > I believe that it’s defined as the size of ω₁, the set of wellorderings of the natural numbers. I don’t think there’s any real sense in which that’s less of a concrete set than the power set of the natural numbers, even if it’s harder to picture. 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.
- billfruit 2y ago
  I find this style of writing from Quanta very jarring and detracting from the usefulness of the article. A factual head line is very much sufficient to get the readers interest.
ajkjk 2y ago
It's a trick! Despite the name, the real numbers aren't real at all. Most of them don't exist... Now the computable reals, on the other hand... maybe.
- skissane 2y ago
  Or the definable reals. Definable meaning you can “name” it uniquely, by writing down some proposition which is true of that real and false for every other. Since there are only a countable number of formulas, there are only countably many definable reals. Definable reals are a superset of computable reals - Chaitin’s constant (for a given computational formalism) is definable but not computable. 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.
  - dullcrisp 2y ago
    For any concrete definition of definable reals and any well-order of the reals, I can refer to the first real that’s undefinable in that system.
    - skissane 2y ago
      If we don’t limit ourselves to formal systems, we can speak about definable in natural language. In which case you just uttered a paradox. 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…
neuroelectron 2y ago
tl;dr: Godel's incompleteness theorem. When you try to create completely self-consistent axioms, it just creates an infinite hierarchy of further unprofitable axioms. Numbers don't really exist, so that was your first mistake. tl;dr^2: Mentally move the hyphen one word to the right.
- bubblyworld 2y ago
  This is a somewhat different situation. Gödel's theorem gives you independent statements but they are highly contrived (containing expressions encoding provability and consistency in an ad-hoc fashion). 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...
  - neuroelectron 2y ago
    Lots of heuristics are useful.
    - bubblyworld 2y ago
      I suggest asking yourself what you think you mean by "exists".
dataflow 2y ago
Meanwhile all I've ever wanted for Christmas was a notion of size that admits (A ⊆ B) ∧ (A ≠ B) ⇒ size(A) < size(B).
- pfdietz 2y ago
  That's a notion that doesn't work for infinite sets.
  - dataflow 2y ago
    Could you expand on why it can't work?
    - heyitsguay 2y ago
      So if N is the natural numbers {1, 2, 3, ...} and E is the even numbers {2, 4, 6, ...}, by the definition you propose, we must have size(E) < size(N), right? 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)?
      - dataflow 2y ago
        Thanks. How I would've imagined this could work (if it could be made to work) is to somehow account for the notion that your "infinity" just got halved (yes I get that infinity is not part of the set, but let me wave my hands here while we're breaking our axioms), and everything "after" it is no longer in the set. Which would imply that "{1, 2, 3, ...}" is no longer a sufficient description for the set of natural numbers; you'd probably need extra information (maybe a "scale factor" for the infinity or something). 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.
qnleigh 2y ago
I wish I understood how mathematicians conceptualize the notion of 'right' and 'wrong' axioms in light of Gödel. I would've thought that the incompleteness theorems would be taken as evidence against Platonism, but clearly this didn't happen. What do people think is the source of 'ground truth'? Is it more than aesthetic appeal? Are there any articles or books that convey it? 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.)
- n4r9 2y ago
  > the incompleteness theorems would be taken as evidence against Platonism 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.
  - dr_dshiv 2y ago
    Platonism is about the reality of math behind the notation and beyond the human mind — 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)
    - n4r9 2y ago
      Right. According to Platonism, a mathematician publishing a result about spherical geometry is in fact exploring an objective reality beyond human minds. Contrast that with, say, intuitionism, according to which they are simply describing the mental activity which arises as a result of considering an object of shared understanding known as a "sphere".
- vlz 2y ago
  This comment from a previous thread https://news.ycombinator.com/item?id=27846084 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 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.
trehalose 2y ago
> But Cantor discovered that natural numbers can’t be put into one-to-one correspondence with the continuum of real numbers. For instance, try to pair 1 with 1.00000… and 2 with 1.00001…, and you’ll have skipped over infinitely many real numbers (like 1.000000001…). You can’t possibly count them all; their cardinality is greater than that of the natural numbers. 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...

58 points by lisper 2y ago

dang 2y ago

Discussed at the time: How many real numbers exist? New proof moves closer to an answer - https://news.ycombinator.com/item?id=27845576 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)

JadeNB 2y ago

The title: > 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.

dullcrisp 2y ago
I had the same initial reaction, because in my mind 2^{ℵ₀} is a more fundamental concept than ℵ₁. 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.
- JadeNB 2y ago
  > I had the same initial reaction, because in my mind 2^{ℵ₀} is a more fundamental concept than ℵ₁. > 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!
  - dullcrisp 2y ago
    I believe that it’s defined as the size of ω₁, the set of wellorderings of the natural numbers. I don’t think there’s any real sense in which that’s less of a concrete set than the power set of the natural numbers, even if it’s harder to picture.
    - JadeNB 2y ago
      > I believe that it’s defined as the size of ω₁, the set of wellorderings of the natural numbers. I don’t think there’s any real sense in which that’s less of a concrete set than the power set of the natural numbers, even if it’s harder to picture. 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.
billfruit 2y ago
I find this style of writing from Quanta very jarring and detracting from the usefulness of the article. A factual head line is very much sufficient to get the readers interest.

ajkjk 2y ago

It's a trick! Despite the name, the real numbers aren't real at all. Most of them don't exist... Now the computable reals, on the other hand... maybe.

skissane 2y ago
Or the definable reals. Definable meaning you can “name” it uniquely, by writing down some proposition which is true of that real and false for every other. Since there are only a countable number of formulas, there are only countably many definable reals. Definable reals are a superset of computable reals - Chaitin’s constant (for a given computational formalism) is definable but not computable. 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.
- dullcrisp 2y ago
  For any concrete definition of definable reals and any well-order of the reals, I can refer to the first real that’s undefinable in that system.
  - skissane 2y ago
    If we don’t limit ourselves to formal systems, we can speak about definable in natural language. In which case you just uttered a paradox. 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…

neuroelectron 2y ago

tl;dr: Godel's incompleteness theorem. When you try to create completely self-consistent axioms, it just creates an infinite hierarchy of further unprofitable axioms. Numbers don't really exist, so that was your first mistake. tl;dr^2: Mentally move the hyphen one word to the right.

bubblyworld 2y ago
This is a somewhat different situation. Gödel's theorem gives you independent statements but they are highly contrived (containing expressions encoding provability and consistency in an ad-hoc fashion). 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...
- neuroelectron 2y ago
  Lots of heuristics are useful.
  - bubblyworld 2y ago
    I suggest asking yourself what you think you mean by "exists".

dataflow 2y ago

Meanwhile all I've ever wanted for Christmas was a notion of size that admits (A ⊆ B) ∧ (A ≠ B) ⇒ size(A) < size(B).

pfdietz 2y ago
That's a notion that doesn't work for infinite sets.
- dataflow 2y ago
  Could you expand on why it can't work?
  - heyitsguay 2y ago
    So if N is the natural numbers {1, 2, 3, ...} and E is the even numbers {2, 4, 6, ...}, by the definition you propose, we must have size(E) < size(N), right? 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)?
    - dataflow 2y ago
      Thanks. How I would've imagined this could work (if it could be made to work) is to somehow account for the notion that your "infinity" just got halved (yes I get that infinity is not part of the set, but let me wave my hands here while we're breaking our axioms), and everything "after" it is no longer in the set. Which would imply that "{1, 2, 3, ...}" is no longer a sufficient description for the set of natural numbers; you'd probably need extra information (maybe a "scale factor" for the infinity or something). 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.

qnleigh 2y ago

I wish I understood how mathematicians conceptualize the notion of 'right' and 'wrong' axioms in light of Gödel. I would've thought that the incompleteness theorems would be taken as evidence against Platonism, but clearly this didn't happen. What do people think is the source of 'ground truth'? Is it more than aesthetic appeal? Are there any articles or books that convey it? 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.)

n4r9 2y ago
> the incompleteness theorems would be taken as evidence against Platonism 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.
- dr_dshiv 2y ago
  Platonism is about the reality of math behind the notation and beyond the human mind — 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)
  - n4r9 2y ago
    Right. According to Platonism, a mathematician publishing a result about spherical geometry is in fact exploring an objective reality beyond human minds. Contrast that with, say, intuitionism, according to which they are simply describing the mental activity which arises as a result of considering an object of shared understanding known as a "sphere".
vlz 2y ago
This comment from a previous thread https://news.ycombinator.com/item?id=27846084 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 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.

trehalose 2y ago

> But Cantor discovered that natural numbers can’t be put into one-to-one correspondence with the continuum of real numbers. For instance, try to pair 1 with 1.00000… and 2 with 1.00001…, and you’ll have skipped over infinitely many real numbers (like 1.000000001…). You can’t possibly count them all; their cardinality is greater than that of the natural numbers. 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...