12 ms·

The countable set of real numbers [video]

42 points by ogogmad 4y ago

still_grokking 4y ago
Stupid question form a ignorant person (me): Are reals actually real? Do they even exist? Almost all reals (besides some countable subsets, which are irrelevant compared to the many many more reals that aren't part of those sets) have infinite many non repeating decimal places, and what's even more annoying, almost all of them aren't computable. The physical universe we can experience is finite. How can more than infinite many "unspeakable" things "exist" in that universe? How does this make sense? You can't express most reals in any meaningful way! Not even by constructing imaginary "infinite" computers. So, when almost all reals aren't anything we could ever experience, or even name in any meaningful way, why do people believe they "exist" in the first place? I have no issue to imagine infinite things as long as I can construct some algorithm to name them. But when there is no such algorithm, how can we know that the thing that can't be named actually exists? I'm not trolling. It's a genuine question I have since some time but didn't have the chance to talk to some mathematicians to get things explained. Maybe someone here could try to explain why we should believe in the existence of real numbers, even there is nothing in the whole universe that relates to most of them? (Especially as the possibility to subdivide any interval infinitely gives rise to phenomenons like the Banach–Tarski paradox. But most people would agree: You can't make something out of nothing. This is imho another strong pointer that reals are an illogical idea in the end. They give rise to contradictions to basic things we assume to know about reality).
- nh23423fefe 4y ago
  > why we should believe in the existence of real numbers, even there is nothing in the whole universe that relates to most of them? Seems like you are defining existence here. Supposed I asked you if 7-dimensional triangles (simplex) exists what would you say? What do the reals have to do with the physical universe?
  - still_grokking 4y ago
    One can construct 7-dimensional triangles. So they surely exist (somehow). > What do the reals have to do with the physical universe? That's kind of a tangent, but the point is: There is absolutely nothing in the universe that relates to most reals! Most reals don't "exist" in any meaningful way. So why should we believe they "exist" at all? (Subsets exist for sure, but that's not the point). Triangles and dimensions exist. One can easily extend this kind of existence to more dimensions. So one can create 7-dimensional triangles. But in contrast one can't, by no means, construct most reals. So my question is: Why should I believe that something that can't be ever "observed" "exists". That's like someone trying to convince me to believe in God… The relation to the physical world is: If someone would say that "there is something" but it can't be even named (out of principle!), not to mention described meaningfully, most people would likely ignore such a purely made up "thing". Because it would have exactly zero influence on anything that may exist in fact. The whole idea that there is something like "smooth space" is absurd given how "the true reality" works. Quantum physics tells us that there is no smooth space, and smooth space is actually impossible. But mathematicians seem to still want to use a "leaky abstraction" that has absolutely nothing in common with reality. Like I said, that's like they would strongly believe in God. Or to phrase it differently: Something that can't be, just can't be. Nobody can construct most reals. That's by definition. So one would need very very strong arguments to still assume that they "exist" (somehow). But there is no such argument at all afaik. That's what I'm asking actually: Does anybody know any, even remotely, valid argument why we should believe in reals? I didn't find any while researching that. Mathematics started as a way to precisely describe "what can exist". But most reals can't be described in any way. So my conclusion would be that they're not part of any valid description of "what can exist". But as most mathematicians seem to believe in reals I wanted to know why it's like that. What do I miss? Where does this faith come form?
    - nh23423fefe 4y ago
      Lots of things are unobservable though. Amplitudes of a wave function are unobservable. What does your idea of existence and relevance say about that? Why is constructibility of elements relevant for belief in a whole. You will never observe an amplitude, is the wave function then "non-real"? The inside of black hole is unobservable from beyond the event horizon. Does that mean the space isn't real? Why is this property of observability or constructibility of individual elements relevant for the existence of a set. Concretely. I believe in the reals because of taking analysis. I guess I don't understand the leverage of calling the reals a "leaky abstraction", it just reads like a skeptical argument taken too far. I hand you a box and say, "these are the reals, they behave this way". You respond, "I've looked in the box and almost all the elements have no recipe, this box doesn't exist." It seems like a non-sequitur to me.
- Delk 4y ago
  I'm not a mathematician, but what you're asking is a valid question in philosophy of mathematics. Generally, mathematical realism sees mathematical objects as existing independently of the human mind while anti-realist schools of thought don't.
  - still_grokking 4y ago
    I came across this. As non-mathematician and non-philosopher I have no strong opinion on that question. It's not important to me whether something exists "only in my mind" (because I could imagine it form some principles) or whether it exists "in general". (In the end "reality" only ever exists in someones mind, because that's how our minds work. But that's not relevant here, imho). The question would be more relevant to the divide between mathematical intuitionism and realism. But the question about reals is imho deeper: I have no strong feelings about, say, the "law of excluded middle". Both sides of the debate have good arguments. You can e.g. "logically claim" that excluded middle must hold, or, equally, needs to be refuted. But I didn't find anything similar regarding the "existence" of reals. There seems to be no logic form which one could derive their "existence". The point is: I don't know any method by which one could even "sense" most reals. It is just assumed that there "are" between any two constructible numbers infinite many (non constructible) reals. But nobody ever seen them, nobody ever will see them, not even if you would have an infinitely powerful computer and know anything that is knowable (which would amount to be like a "god"; so not even a god can "see" most reals). The question around the existence of most reals is like asking "What's 'between' two points in space-time which are less than half a Planck unit away?". A physicist would most likely answer with: "Even asking such a question does not make any sense". (That's once again the mentioned tangent to physical reality). But mathematicians seem to happily answer such a question with "There are just more reals. Never mind that you can't see them". Completely unrealistic things like Banach–Tarski get accepted than as a consequence without much fuss… People are still riddled by things like the continuum hypothesis… But what if there isn't any "continuum" at all? In physical reality there is also nothing like that! (Which was an unexpected and deeply concerning discovery, the consequences of which we still don't understand; but we're quite sure by now that this new picture, a discrete description of reality, is closer to what's actually out there than the "naïve" description that assumes some "continuous smooth space").
fdupress 4y ago
The title of the video and talk is "The countable reals." There are plenty of countable sets of real numbers (Q and all its subsets, for one infinity), and the set of all real numbers is not countable, so there is no interpretation of the current submission title that makes sense.
- defrost 4y ago
  It's a literal assertion that the reals (all reals) ARE countable .. subject to taking issue with aspects of Cantors argument. It opens: > In 1874 Georg Cantor published a theorem stating that every sequence of reals is avoided by some real, thereby showing that the reals are not countable. > Cantor's proof uses classical logic. > There are constructive proofs, although they all rely on the axiom of countable choice. Can the real numbers be shown uncountable without excluded middle and without the axiom of choice? >An answer has not been found so far, although not for lack of trying. > We show that there is a topos in which the real numbers are countable, i.e., there is an epimorphism from the object of natural numbers to the object of Dedekind reals. > Therefore, higher-order intuitionistic logic cannot show the reals to be uncountable.
  - fdupress 4y ago
    That is an assertion about one particular construction of the reals, in a particular topos, which implies something on the constructed set in that topos. I'd argue that that set, resulting from carrying out Dedekind cuts in a particular topos, is not in fact the set of real numbers. But I also agree that it means the property of uncountability for the set of real numbers as we understand it in set theoretic terms cannot be proved intuitionistically. And I'm fine with that.
    - fdupress 4y ago
      Just a quick addition: note the care taken to avoid using the word "set" in your excerpts. My objection was with the submission's current title ("The countable set of real numbers"). It still stands.
    - 4y ago
deleted 4y ago
[deleted]
sn41 4y ago
I think Skolem's initial intent in showing the Lowenheim-Skolem theorem (that every structure which has an infinite model has a countably infinite model) was to develop a theory of reals which did not use uncountability.
ogogmad 4y ago
There's more than one way to prove the real numbers uncountable. All of them assume something though! https://link.springer.com/content/pdf/bbm:978-1-4614-8854-5/1.pdf https://link.springer.com/content/pdf/bbm:978-1-4614-8854-5/... There's a recursive subdivision approach that goes back to Cantor. If the subdivisions form a disjoint cover, then the Law Of Excluded Middle (actually, the weaker Limited Principle Of Omniscience) gets used. This proof is equivalent to the popular decimal-digits proof. The problem is that the decimal digits of a real number may not be computable, so there is a dependence on Excluded Middle. If the subdivisions form an open cover, then Dependent Choice gets used to resolve the ambiguity created by open sets overlapping, but LEM gets avoided. This forms an algorithm you can do on a computer, to produce a real number not in a given sequence. The dependence on Dependent Choice can be improved to Countable Choice, which effectively parallelises the algorithm. There's another approach based on the fact that countable sets have measure 0. This then implies that the reals have measure 0. To actually get a rigorous contradiction, you need to use the compactness of the interval [0,1]. In constructive logic, this is a consequence of Open Induction (but can be improved to use the "Fan Theorem"). So you need either LEM (really, LPO), Dependent Choice (really, Countable Choice), or Open Induction (really, Fan Theorem). The Dependent Choice approach even determines an explicit algorithm. But there's no unconditional proof. And if the result in the video is correct, there can never be one, because it's possible that the real numbers are countable.
- mjburgess 4y ago
  It's "possible" presumably only in the sense in which one can assign a True/False value to any proposition. I guess one could see a logic as deciding if a set of propositions is inconsistent. And one could imagine a "trivial logic" which says "Yes" for any set, consistent?(props | logic) = Yes. Then as we add more structure to the logic, more sets become inconsistent: consistent?(CountableReals | LawExMiddle) = No. What value is there to saying the reals are "possibly" countable when it seems we're basically enforcing no consistency in the set of propositions which would constitute a "proof" of such a thing?
  - chriswarbo 4y ago
    Euclidean geometry is a common example of this: if we remove the parallel postulate, we get a weaker theory; unable to prove various "facts". However, this weaker theory is also more general, applying to curved spaces too; where those facts are not true. It turns out that the physical universe is curved, and hence those original "facts" don't hold in the 'real world'. It seems like a similar thing is happening here: we can prove that the set of reals is uncountable, but only if we use classical axioms which don't account for computability. Using a weaker (intuitionistic/constructive) theory prevents us proving that the reals are uncountable; that turns out to be necessary, because some of the alternatives cause the reals to be countable. Since the physical universe is computable (or at least, computably indistinguishable from being computable), these alternatives may be better descriptions of the 'real world' than classical logic.
H8crilA 4y ago
If you want an explanation: the set is countable from "outside", that is the entire model is countable. But inside the model there really isn't a bijection between the sets of naturals and reals. This function is not an element of the model, and had you manually added it you'd experience serious problems. It's not too surprising, after all the set of reals that can be named is obviously countable (there is at most one real number per name), regardless of the complexity of the naming scheme. This theorem is a solid mathematical take on the old trope of "perhaps it's all a simulation".
- ogogmad 4y ago
  > But inside the model there really isn't a bijection between the sets of naturals and reals No. Inside the model, there is exactly such a surjection. We don't care what happens outside of it. Maybe you already knew this, but to clarify: "Countable" means that there exists a surjection, not necessarily a bijection. For instance, the set {a,b,c} is countable, but there is clearly no bijection Nat -> {a,b,c} as one set is infinite and the other's finite. > It's not too surprising On the contrary: It's a ground-breaking result IMO.
  - deleted 4y ago
    [deleted]
  - drdec 4y ago
    As always, this depends on your definitions, e.g. see https://encyclopediaofmath.org/wiki/Countable_set https://encyclopediaofmath.org/wiki/Countable_set
    - fdupress 4y ago
      By the definition you link, combined with its subdefinition for uncountable, finite sets are uncountable. That is a pretty big leap from accepted terminology.
- ComplexSystems 4y ago
  I think it's a little deeper than that. The new idea here is that if we change the background logic from classical to something else, we can get a logic in which Cantor's theorem doesn't hold, since it apparently requires something like excluded middle.
shkkmo 4y ago
This seems to sort of line up with something I've been thinking recently: the difference between nameable and unnameable reals. Some "real" numbers may have no finite definition (i.e. there exists no finite algorithm by which any finite digit can be calculated in finite time), I tend to think of these as cthulu numbers. The total number of possible names for real numbers seems easily countable (just list the possible papers describing the proof that a specific one is nameable, by length and alphabetically), and the real numbers that actually have names are just a subset (though determining which ones those are is an exercise left to the reader.) Thus the uncountable portion of the reals seems to me to be comprised of cthulu numbers. That or the nameable numbers are what we mean by the reals and these cthulu numbers are something else entirely.
- ComplexSystems 4y ago
  The "Cthulhu numbers" are basically, informally, just "random" numbers. The easiest way to build one is to choose a number at random in the interval [0,1], i.e. by flipping a coin countably many times and choosing each bit in the binary expansion based on the result. With probability one, the number you get will not be the output of any Turing machine, nor described by any particular formula, etc - it will just be a random string of bits whose bits are chosen "for no logical reason." This means it will be one of your Cthulhu numbers. Do we really want to get rid of these and only have non-random structured numbers? Because it's certainly a useful idea to have idealized infinite strings of structureless random bits in plenty of situations. But if you like, you can always try Gödel's constructible universe L.
- OscarCunningham 4y ago
  One complexity is that it's impossible to define 'definable'. Otherwise you could apply Cantor's construction to define an undefinable number.
- jbaber 4y ago
  You're noticing the algebraic numbers + all the transcendentals that you happen to need throughout your life (\pi, e, etc.) are countable. Sounds kind of deep, but plenty of proofs apply to uncountable sets. We finite little humans just live, necessarily, in a countable world.
denton-scratch 4y ago
My understanding of "countable" is that it's reasonable to ask which is the "next" in sequence. You can't do that with reals. /me didn't watch the video.
- denton-scratch 4y ago
  Hey, I don't mind being downvoted at all. But if I'm wrong, then can you please explain how? I thought only sequences could be counted. If I'm downvoted for not watching the video, I think that's mean. I was interested in the subject, but I'd prefer a transcript to a video.
  - gjm11 4y ago
    A set is countable iff there is a sequence that counts it. That doesn't require that there be One True Notion of next-ness in the set itself. For instance, if I give you the rational number 337/912 and ask "what's the next rational number?" there isn't a canonical answer. But the rational numbers are countable. So the fact that there isn't a canonical answer to "what's the next real number?" doesn't tell us anything about whether or not the real numbers are countable. (For the avoidance of doubt: in ordinary set theory with ordinary logic, the reals are definitely not countable. The research being reported on here looks at what happens when you weaken your logic, by throwing out the "law of the excluded middle", and weaken your set theory, by not having any form of the "axiom of choice". It turns out that in this case there are multiple things you might reasonably mean by "the real numbers", and for at least one of these you can no longer prove that they're uncountable, and we can tell this because there's a so-called topos in which "the real numbers" are countable. A topos is a sort of generalized "notion of what a set is", and if something is provable intuitionistically and without any version of the axiom of choice then it is true in every topos. I think. Something along those lines, anyway.)
    - denton-scratch 4y ago
      THank you. I had no idea there were different ideas of what "real" meant, and it's my first encounter with the notion of a topos (other than a place: the "topos" was the toilet, the place where the boys went to piss at my boarding school). [Edit] Also, I hadn't grokked that rationals were countable; but now you point it out, I guess they must be. Does countable imply enumerable?

42 points by ogogmad 4y ago

Stupid question form a ignorant person (me): Are reals actually real? Do they even exist? Almost all reals (besides some countable subsets, which are irrelevant compared to the many many more reals that aren't part of those sets) have infinite many non repeating decimal places, and what's even more annoying, almost all of them aren't computable. The physical universe we can experience is finite. How can more than infinite many "unspeakable" things "exist" in that universe? How does this make sense? You can't express most reals in any meaningful way! Not even by constructing imaginary "infinite" computers. So, when almost all reals aren't anything we could ever experience, or even name in any meaningful way, why do people believe they "exist" in the first place? I have no issue to imagine infinite things as long as I can construct some algorithm to name them. But when there is no such algorithm, how can we know that the thing that can't be named actually exists? I'm not trolling. It's a genuine question I have since some time but didn't have the chance to talk to some mathematicians to get things explained. Maybe someone here could try to explain why we should believe in the existence of real numbers, even there is nothing in the whole universe that relates to most of them? (Especially as the possibility to subdivide any interval infinitely gives rise to phenomenons like the Banach–Tarski paradox. But most people would agree: You can't make something out of nothing. This is imho another strong pointer that reals are an illogical idea in the end. They give rise to contradictions to basic things we assume to know about reality).

nh23423fefe 4y ago
> why we should believe in the existence of real numbers, even there is nothing in the whole universe that relates to most of them? Seems like you are defining existence here. Supposed I asked you if 7-dimensional triangles (simplex) exists what would you say? What do the reals have to do with the physical universe?
- still_grokking 4y ago
  One can construct 7-dimensional triangles. So they surely exist (somehow). > What do the reals have to do with the physical universe? That's kind of a tangent, but the point is: There is absolutely nothing in the universe that relates to most reals! Most reals don't "exist" in any meaningful way. So why should we believe they "exist" at all? (Subsets exist for sure, but that's not the point). Triangles and dimensions exist. One can easily extend this kind of existence to more dimensions. So one can create 7-dimensional triangles. But in contrast one can't, by no means, construct most reals. So my question is: Why should I believe that something that can't be ever "observed" "exists". That's like someone trying to convince me to believe in God… The relation to the physical world is: If someone would say that "there is something" but it can't be even named (out of principle!), not to mention described meaningfully, most people would likely ignore such a purely made up "thing". Because it would have exactly zero influence on anything that may exist in fact. The whole idea that there is something like "smooth space" is absurd given how "the true reality" works. Quantum physics tells us that there is no smooth space, and smooth space is actually impossible. But mathematicians seem to still want to use a "leaky abstraction" that has absolutely nothing in common with reality. Like I said, that's like they would strongly believe in God. Or to phrase it differently: Something that can't be, just can't be. Nobody can construct most reals. That's by definition. So one would need very very strong arguments to still assume that they "exist" (somehow). But there is no such argument at all afaik. That's what I'm asking actually: Does anybody know any, even remotely, valid argument why we should believe in reals? I didn't find any while researching that. Mathematics started as a way to precisely describe "what can exist". But most reals can't be described in any way. So my conclusion would be that they're not part of any valid description of "what can exist". But as most mathematicians seem to believe in reals I wanted to know why it's like that. What do I miss? Where does this faith come form?
  - nh23423fefe 4y ago
    Lots of things are unobservable though. Amplitudes of a wave function are unobservable. What does your idea of existence and relevance say about that? Why is constructibility of elements relevant for belief in a whole. You will never observe an amplitude, is the wave function then "non-real"? The inside of black hole is unobservable from beyond the event horizon. Does that mean the space isn't real? Why is this property of observability or constructibility of individual elements relevant for the existence of a set. Concretely. I believe in the reals because of taking analysis. I guess I don't understand the leverage of calling the reals a "leaky abstraction", it just reads like a skeptical argument taken too far. I hand you a box and say, "these are the reals, they behave this way". You respond, "I've looked in the box and almost all the elements have no recipe, this box doesn't exist." It seems like a non-sequitur to me.
Delk 4y ago
I'm not a mathematician, but what you're asking is a valid question in philosophy of mathematics. Generally, mathematical realism sees mathematical objects as existing independently of the human mind while anti-realist schools of thought don't.
- still_grokking 4y ago
  I came across this. As non-mathematician and non-philosopher I have no strong opinion on that question. It's not important to me whether something exists "only in my mind" (because I could imagine it form some principles) or whether it exists "in general". (In the end "reality" only ever exists in someones mind, because that's how our minds work. But that's not relevant here, imho). The question would be more relevant to the divide between mathematical intuitionism and realism. But the question about reals is imho deeper: I have no strong feelings about, say, the "law of excluded middle". Both sides of the debate have good arguments. You can e.g. "logically claim" that excluded middle must hold, or, equally, needs to be refuted. But I didn't find anything similar regarding the "existence" of reals. There seems to be no logic form which one could derive their "existence". The point is: I don't know any method by which one could even "sense" most reals. It is just assumed that there "are" between any two constructible numbers infinite many (non constructible) reals. But nobody ever seen them, nobody ever will see them, not even if you would have an infinitely powerful computer and know anything that is knowable (which would amount to be like a "god"; so not even a god can "see" most reals). The question around the existence of most reals is like asking "What's 'between' two points in space-time which are less than half a Planck unit away?". A physicist would most likely answer with: "Even asking such a question does not make any sense". (That's once again the mentioned tangent to physical reality). But mathematicians seem to happily answer such a question with "There are just more reals. Never mind that you can't see them". Completely unrealistic things like Banach–Tarski get accepted than as a consequence without much fuss… People are still riddled by things like the continuum hypothesis… But what if there isn't any "continuum" at all? In physical reality there is also nothing like that! (Which was an unexpected and deeply concerning discovery, the consequences of which we still don't understand; but we're quite sure by now that this new picture, a discrete description of reality, is closer to what's actually out there than the "naïve" description that assumes some "continuous smooth space").

fdupress 4y ago

The title of the video and talk is "The countable reals." There are plenty of countable sets of real numbers (Q and all its subsets, for one infinity), and the set of all real numbers is not countable, so there is no interpretation of the current submission title that makes sense.

defrost 4y ago
It's a literal assertion that the reals (all reals) ARE countable .. subject to taking issue with aspects of Cantors argument. It opens: > In 1874 Georg Cantor published a theorem stating that every sequence of reals is avoided by some real, thereby showing that the reals are not countable. > Cantor's proof uses classical logic. > There are constructive proofs, although they all rely on the axiom of countable choice. Can the real numbers be shown uncountable without excluded middle and without the axiom of choice? >An answer has not been found so far, although not for lack of trying. > We show that there is a topos in which the real numbers are countable, i.e., there is an epimorphism from the object of natural numbers to the object of Dedekind reals. > Therefore, higher-order intuitionistic logic cannot show the reals to be uncountable.
- fdupress 4y ago
  That is an assertion about one particular construction of the reals, in a particular topos, which implies something on the constructed set in that topos. I'd argue that that set, resulting from carrying out Dedekind cuts in a particular topos, is not in fact the set of real numbers. But I also agree that it means the property of uncountability for the set of real numbers as we understand it in set theoretic terms cannot be proved intuitionistically. And I'm fine with that.
  - fdupress 4y ago
    Just a quick addition: note the care taken to avoid using the word "set" in your excerpts. My objection was with the submission's current title ("The countable set of real numbers"). It still stands.
  - 4y ago

deleted 4y ago

[deleted]

sn41 4y ago

I think Skolem's initial intent in showing the Lowenheim-Skolem theorem (that every structure which has an infinite model has a countably infinite model) was to develop a theory of reals which did not use uncountability.

ogogmad 4y ago

There's more than one way to prove the real numbers uncountable. All of them assume something though! https://link.springer.com/content/pdf/bbm:978-1-4614-8854-5/1.pdf https://link.springer.com/content/pdf/bbm:978-1-4614-8854-5/... There's a recursive subdivision approach that goes back to Cantor. If the subdivisions form a disjoint cover, then the Law Of Excluded Middle (actually, the weaker Limited Principle Of Omniscience) gets used. This proof is equivalent to the popular decimal-digits proof. The problem is that the decimal digits of a real number may not be computable, so there is a dependence on Excluded Middle. If the subdivisions form an open cover, then Dependent Choice gets used to resolve the ambiguity created by open sets overlapping, but LEM gets avoided. This forms an algorithm you can do on a computer, to produce a real number not in a given sequence. The dependence on Dependent Choice can be improved to Countable Choice, which effectively parallelises the algorithm. There's another approach based on the fact that countable sets have measure 0. This then implies that the reals have measure 0. To actually get a rigorous contradiction, you need to use the compactness of the interval [0,1]. In constructive logic, this is a consequence of Open Induction (but can be improved to use the "Fan Theorem"). So you need either LEM (really, LPO), Dependent Choice (really, Countable Choice), or Open Induction (really, Fan Theorem). The Dependent Choice approach even determines an explicit algorithm. But there's no unconditional proof. And if the result in the video is correct, there can never be one, because it's possible that the real numbers are countable.

mjburgess 4y ago
It's "possible" presumably only in the sense in which one can assign a True/False value to any proposition. I guess one could see a logic as deciding if a set of propositions is inconsistent. And one could imagine a "trivial logic" which says "Yes" for any set, consistent?(props | logic) = Yes. Then as we add more structure to the logic, more sets become inconsistent: consistent?(CountableReals | LawExMiddle) = No. What value is there to saying the reals are "possibly" countable when it seems we're basically enforcing no consistency in the set of propositions which would constitute a "proof" of such a thing?
- chriswarbo 4y ago
  Euclidean geometry is a common example of this: if we remove the parallel postulate, we get a weaker theory; unable to prove various "facts". However, this weaker theory is also more general, applying to curved spaces too; where those facts are not true. It turns out that the physical universe is curved, and hence those original "facts" don't hold in the 'real world'. It seems like a similar thing is happening here: we can prove that the set of reals is uncountable, but only if we use classical axioms which don't account for computability. Using a weaker (intuitionistic/constructive) theory prevents us proving that the reals are uncountable; that turns out to be necessary, because some of the alternatives cause the reals to be countable. Since the physical universe is computable (or at least, computably indistinguishable from being computable), these alternatives may be better descriptions of the 'real world' than classical logic.

H8crilA 4y ago

If you want an explanation: the set is countable from "outside", that is the entire model is countable. But inside the model there really isn't a bijection between the sets of naturals and reals. This function is not an element of the model, and had you manually added it you'd experience serious problems. It's not too surprising, after all the set of reals that can be named is obviously countable (there is at most one real number per name), regardless of the complexity of the naming scheme. This theorem is a solid mathematical take on the old trope of "perhaps it's all a simulation".

ogogmad 4y ago
> But inside the model there really isn't a bijection between the sets of naturals and reals No. Inside the model, there is exactly such a surjection. We don't care what happens outside of it. Maybe you already knew this, but to clarify: "Countable" means that there exists a surjection, not necessarily a bijection. For instance, the set {a,b,c} is countable, but there is clearly no bijection Nat -> {a,b,c} as one set is infinite and the other's finite. > It's not too surprising On the contrary: It's a ground-breaking result IMO.
- deleted 4y ago
  [deleted]
- drdec 4y ago
  As always, this depends on your definitions, e.g. see https://encyclopediaofmath.org/wiki/Countable_set https://encyclopediaofmath.org/wiki/Countable_set
  - fdupress 4y ago
    By the definition you link, combined with its subdefinition for uncountable, finite sets are uncountable. That is a pretty big leap from accepted terminology.
ComplexSystems 4y ago
I think it's a little deeper than that. The new idea here is that if we change the background logic from classical to something else, we can get a logic in which Cantor's theorem doesn't hold, since it apparently requires something like excluded middle.

shkkmo 4y ago

This seems to sort of line up with something I've been thinking recently: the difference between nameable and unnameable reals. Some "real" numbers may have no finite definition (i.e. there exists no finite algorithm by which any finite digit can be calculated in finite time), I tend to think of these as cthulu numbers. The total number of possible names for real numbers seems easily countable (just list the possible papers describing the proof that a specific one is nameable, by length and alphabetically), and the real numbers that actually have names are just a subset (though determining which ones those are is an exercise left to the reader.) Thus the uncountable portion of the reals seems to me to be comprised of cthulu numbers. That or the nameable numbers are what we mean by the reals and these cthulu numbers are something else entirely.

ComplexSystems 4y ago
The "Cthulhu numbers" are basically, informally, just "random" numbers. The easiest way to build one is to choose a number at random in the interval [0,1], i.e. by flipping a coin countably many times and choosing each bit in the binary expansion based on the result. With probability one, the number you get will not be the output of any Turing machine, nor described by any particular formula, etc - it will just be a random string of bits whose bits are chosen "for no logical reason." This means it will be one of your Cthulhu numbers. Do we really want to get rid of these and only have non-random structured numbers? Because it's certainly a useful idea to have idealized infinite strings of structureless random bits in plenty of situations. But if you like, you can always try Gödel's constructible universe L.
OscarCunningham 4y ago
One complexity is that it's impossible to define 'definable'. Otherwise you could apply Cantor's construction to define an undefinable number.
jbaber 4y ago
You're noticing the algebraic numbers + all the transcendentals that you happen to need throughout your life (\pi, e, etc.) are countable. Sounds kind of deep, but plenty of proofs apply to uncountable sets. We finite little humans just live, necessarily, in a countable world.

denton-scratch 4y ago

My understanding of "countable" is that it's reasonable to ask which is the "next" in sequence. You can't do that with reals. /me didn't watch the video.

denton-scratch 4y ago
Hey, I don't mind being downvoted at all. But if I'm wrong, then can you please explain how? I thought only sequences could be counted. If I'm downvoted for not watching the video, I think that's mean. I was interested in the subject, but I'd prefer a transcript to a video.
- gjm11 4y ago
  A set is countable iff there is a sequence that counts it. That doesn't require that there be One True Notion of next-ness in the set itself. For instance, if I give you the rational number 337/912 and ask "what's the next rational number?" there isn't a canonical answer. But the rational numbers are countable. So the fact that there isn't a canonical answer to "what's the next real number?" doesn't tell us anything about whether or not the real numbers are countable. (For the avoidance of doubt: in ordinary set theory with ordinary logic, the reals are definitely not countable. The research being reported on here looks at what happens when you weaken your logic, by throwing out the "law of the excluded middle", and weaken your set theory, by not having any form of the "axiom of choice". It turns out that in this case there are multiple things you might reasonably mean by "the real numbers", and for at least one of these you can no longer prove that they're uncountable, and we can tell this because there's a so-called topos in which "the real numbers" are countable. A topos is a sort of generalized "notion of what a set is", and if something is provable intuitionistically and without any version of the axiom of choice then it is true in every topos. I think. Something along those lines, anyway.)
  - denton-scratch 4y ago
    THank you. I had no idea there were different ideas of what "real" meant, and it's my first encounter with the notion of a topos (other than a place: the "topos" was the toilet, the place where the boys went to piss at my boarding school). [Edit] Also, I hadn't grokked that rationals were countable; but now you point it out, I guess they must be. Does countable imply enumerable?