The countable set of real numbers [video]
youtube.com
youtube.com
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.
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?
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.
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.
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.
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.
I chose that title out of a combination of deliberate clickbait, and because I felt that the original title was confusing to people who hadn't heard the abbreviation "the reals" for the set (or "space"?) of real numbers.
In other words, the object on which the existing proofs of uncountability hold and the object constructed in the talk are not necessarily the same object. In fact, the care taken by Bauer in clarifying "the object of Dedekind reals" in stating his main results leads me to believe the topos in which the Dedekind reals are countable is also a topos in which the Dedekind reals are not equivalent to other constructions of the reals.
/me not a mathematician.
/me didn't watch the video.
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".
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.
That is a pretty big leap from accepted terminology.
- We write a function 'diagonal: List[List[Digit]] -> List[Digit]' which returns the first entry of the first list, followed by the second entry of the second list, and so on for the ith entry of the ith list
- The function 'map (+1) ∘ diagonal' will accept a List[List[Digit]] and return a List[Digit] which is guaranteed to not appear in that given input, even if the lists extend forever
This new approach replaces that List[Digit] representation; instead representing a real number as a set of all 'oracles' which output that number's digits. As you say, there will be numbers with multiple oracles (outputting different digits, which nevertheless correspond to the same number, e.g. 0.1999... and 0.2000...).
The new result is that there are no such functions which treat all of a number's oracles the same; i.e. that return the same sequence of digits for '0.1999...' as for '0.2000...', etc.
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).
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?
> 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?
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.
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").
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.
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.
Sounds kind of deep, but plenty of proofs apply to uncountable sets. We finite little humans just live, necessarily, in a countable world.
They're an interesting set of numbers, but they're a complicated thing to do work with because of the "holes" in them. For instance, see the section in that article labelled "Use in place of the reals". To see how bad missing things like supremums can be, consider something like this video: https://www.youtube.com/watch?v=vV7ZuouUSfs That video is about the difficulty/impossibility of defining calculus over the rational numbers, which is a simpler lens to see the problems that can arise when you're unable to define some simple properties that you may be so used to you don't realize it. Imagining how that can go wrong with a different set of "holes" in the number line is not too much of a strain after that.
For all their paradoxes and oddities, and the unlikelihood of them corresponding to anything actually "real" in the real world, the real numbers are popular in math for a reason.
GP appears to be talking about definable reals, not computable. For example [any particular] Chaitin's constant is definable but not computable.
/me didn't watch the video.
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.
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.)
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?
With the restrictions being used here, though, the different definitions aren't all equivalent, and apparently it turns out that one version of "the real numbers" is necessarily countable and another isn't (because it's countable "in a particular topos").
"Countable" and "enumerable" are the same thing. (But there's a separate term, "recursively enumerable", that means something else.)
One way to see that the rational numbers are countable: write them down in a sort of square where m/n goes in position (m,n). You'll have e.g. 2/3 and 4/6 and 6/9 and ..., all in different places, but that's harmless. Then start at (1,1) and walk along the finite diagonals: 1/1, then 1/2, 2/1, then 1/3, 2/2, 3/1, etc. Boom, you've counted the rational numbers :-).
In other words, there can be multiple next functions, but a set is countable iff there is at least one of them.
In plain English, you need to construct an infinite sequence (a,b,c,d,...) which (i) consists of elements of a set S (ii) contains every element of S at least once - sometimes many times over. We also allow the members of this sequence to equal an exceptional value we denote with an asterisk: *. This is to take into account the possibility that S may be an empty set. Without this exceptional value, such a sequence cannot exist if S is empty. If S has at least 1 element, then we don't need the exceptional value.
I don't know if this means you can sensibly talk about a "next" element. The problem is that an element of S might repeat. What you're describing sounds equally like a total ordering. Assuming the Axiom Of Choice, every set has a total ordering, but the indices are not in general natural numbers, but may be ordinal numbers. You cannot in general exhibit such a total ordering, because anything proved using the Axiom Of Choice is merely known to exist, but cannot always be computed or constructed.
If you take your sequence construction, then by removing duplicates from the sequence, this new sequence would allow finding a "next" element.