 I know it's completely unrelated to the article, but I would like to take a moment to plug an absolutely beautiful proof of the uncountability of [0,1], which I first saw in http://people.math.gatech.edu/~mbaker/pdf/realgame.pdf .Briefly: Alice and Bob play a game. Alice starts at 0, Bob starts at 1, and they alternate taking turns (starting with Alice), each picking a number between Alice and Bob's current numbers. (So start with A:0, B:1, then A:0.5, B:0.75, A:0.6, … is an example of the start of a valid sequence of plays.) We fix a subset S of [0,1] in advance, and Alice will win if at the end of all time the sequence of numbers she has picked converges to a number in S; Bob wins otherwise. (Alice's sequence does converge: it's increasing and bounded above by 1.)It's obvious that if S = [0,1] then Alice wins no matter what strategy either of them uses: a convergent sequence drawn from [0,1] must converge to something in [0,1].Also, if S = (s1, s2, …) is countable then Bob has a winning strategy: at move n, pick s_n if possible, and otherwise make any legal move. (Think for a couple of minutes to see why this is true: if Bob couldn't pick s_n at time n, then either Alice has already picked a number bigger, in which case she can't ever get back down near s_n again, or Bob has already picked a number b which is smaller, in which case she is blocked off from reaching s_n because she can't get past b.)So if [0,1] is countable then Alice must win no matter what either of them does, but Bob has a winning strategy; contradiction. In a similar vein, Cantor's original diagonalization proof of uncountability is one of the most satisfying results in real analysis. From https://www.cs.virginia.edu/luther/blog/posts/124.html:"Any real number can be rep­re­sented as an inte­ger fol­lowed by a dec­imal point and an infi­nite sequence of dig­its. Let’s ignore the inte­ger part for now and only con­sider real numbers between 0 and 1. Now we need to show that all pair­ings of infi­nite sequences of dig­its to inte­gers of neces­sity leaves out some infi­nite sequences of dig­its.Let’s say our can­di­date pair­ing maps pos­i­tive inte­ger i to real number r_i. Let’s also denote the digit in posi­tion i of a real number x as x_i. Thus, if one of our pair­ings was (17, 0.651249324…) then r_17^4 would be 2. Now, con­sider the spe­cial number z, where z_i is the bot­tom digit of r_i^i + 1.The number z above is a real number between 0 and 1 and is not paired with any pos­i­tive inte­ger. Since we can con­struct such a z for any pair­ing, we know that every pair­ing has at least one number not in it. Thus, the lists aren’t the same size, mean­ing that the list of real numbers must be big­ger than the list of inte­gers." Before the diagonalization argument, Cantor had another proof of the uncountability of the reals. Looking it up again, it's actually pretty much the Alice-Bob game!(To see the correspondence, it's helpful to think of limits as being a kind of game. You claim the limit is a particular value, another party challenges you with an epsilon, and then you respond to the challenge by saying an index in the sequence after which all the entries are within epsilon of the claimed limit.) The proof on this page has a small gap: it fails to take into account that some numbers don't have unique decimal expansion.For example, if all digits on the diagonal were 8, then z = 0.(9) = 1, which is not between 0 and 1. Yes. Though that problem is repairable. Cantor's diagonal argument is interesting, because it's not just a nifty proof, but seen as an entirely new proof strategy. Those don't get invented often. I took a very long time to understand this! I want to share my understanding.Say Alice's sequence converges to some rational X. You enumerated all the rationals, and X has index N. But Bob played X in turn N, because X was a legal move in turn N (in every turn even). And in turn N+1, Bob must play something smaller than X. So Alice's sequence cannot converge to X. The author, Matt Baker, was my Algebra professor back when I was an undergrad. The guy is super smart and also an amazing magician, he used to perform these awesome magic tricks in class. This proof seems a little bit subtle and rather unsatisfying because of it. It isn't even obvious that the game can be said to converge to a value. We don't seem to be able to say we know of a value that it converges to, because both players have an infinite amount of time to change it.The proof you link says the series converges to some \alpha where a_n < \alpha < b_n. So we have an infinite number of values in S that the series cannot converge to. But it is also true that the number of values between a_n and b_n that are \in S is infinite for all n. So we know there are infinitely many numbers that we could converge to where Alice wins, and infinitely many of them won't be converged to by Bob's actions. The satisfying argument that the two infinities are the same size is not that clear although I'm sure in the technicalities there is some definition that settles it. The reader has to be really on top of the definitions of limits and behaviours at infinity to trust this result.The diagonal argument is a lot smoother because it constructs a neat example of a number that you missed if you tried to count the reals. It has a lot more punch with the "if you believe they are countable, explain this number I'm building" approach. All you need to believe is that an increasing sequence, bounded above, converges. (Indeed, take the supremum of the sequence, and show that the sequence converges to that supremum.) Alice's sequence is increasing, and bounded above by 1, so it converges.Certainly both players have infinitely many chances to influence the limit - it's an adversarial game! The point is whether Bob can force a win against Alice, and it turns out that if the set S is countable then Bob can. > All you need to believe is that an increasing sequence, bounded above, converges. Indeed, take the supremum of the sequence, and show that the sequence converges to that supremum.While one might feel more "comfortable" with the the monotone convergence theorem because one encounters it as early as, say, high school calculus, I'm not sure it's _simpler_ than Cantor's proof which doesn't require any of the _analytic_ properties of the real numbers to do its job.How do we know the monotone convergence theorem is true? Like you say, it's because the reals have the least upper bound property (aka they're Dedekind complete).How do we know the reals have the least upper bound property? Well, we can construct them from the rationals via Dedekind cuts to make it obvious they have that property.Peeled back, the machinery being brought to bear in this proof is way more subtle and high-powered than required for directly proving, say, "The set of all infinite sequences on {0,1} is uncountable." It's just machinery we take for granted.What's more, the integers are infinite and Dedekind complete, so _that's_ not enough to conclude a set is uncountable. The fact that the reals are totally ordered and we can always pick a third, distinct number between any two reals plays a role here.I'm not even sure we need the underlying set to be ordered. Is every infinite, non-discrete, Dedekind complete set also uncountable?Overall, I find the original proof more clever than satisfying. The idea of playing a game on [0,1] is cute, but what does it reveal about the essential distinctions between the integers, the rationals, and the reals WRT their set-theoretic properties? When it comes to answering "What's actually going on, here?" I think it obscures more than clarifies. Both proofs are interesting.> The idea of playing a game on [0,1] is cute, but what does it reveal about the essential distinctions between the integers, the rationals, and the reals WRT their set-theoretic properties?You could for example see what happens when you play this game on the p-adic numbers. I agree: the proof suggests that the integers are essentially different because their order is not dense; the rationals are essentially different because Alice's sequence might not converge; the computable reals are different because Bob might not be able to compute membership of S. These aren't set-theoretic properties, I suppose, but they're certainly interesting. Of course, the mere failure of an argument is not proof of the negation, but I'd say the proof is illuminating. By contrast, Cantor's diagonal argument is laser-focused on proving this one fact (and it does so well!): it's a single technique, pared to the bone, telling you exactly what you wanted to know and no more. Yes. Though it's also interesting to see how Cantor's proof can fail.Eg you can try to apply Cantor's proof on the list of all integers (written in decimal form) to attempt to prove that the integers aren't countable. Or on a list of all rationals.The proofs will fail in interesting ways. jfarmer on Aug 5, 2020 [–] > You could for example see what happens when you play this game on the p-adic numbers.The p-adic numbers can't be turned into an ordered field, so it's unclear what the "between" in "choosing a number between A and B" would mean. It's hard to imagine a generalization since concepts like "monotone convergence" and "least upper bound" come from order theory, not topology.The p-adics are complete as a metric space (Cauchy) but not complete as an order (Dedekind). Thanks! I wasn't thinking too hard when I wrote that, but your example shows exactly what I had in mind. The game just 'fails earlier', than I thought.To play a similar-ish game, you could perhaps have Alice and Bob alternate to pick open (or closed etc) balls, with the constrained that subsequent balls have to be contained in each other. Maybe, but I don't really see what that gets you:1. In an ultrametric space like the p-adics (ℚₚ), two open balls are either totally disjoint or one is a subset of the other2. In an ultrametric space like the p-adics (ℚₚ), every ball is both open and closed (clopen)3. The p-adics are spherically complete, which means the intersection of any sequence of nested balls is non-empty (remember balls are clopen, so it doesn't matter if the balls are "open" or "closed")4. Let ℤₚ denote the p-adic integers (not the integers-mod-p). Then ℚₚ has a countable basis consisting of sets that look like: {q + pⁿℤₚ : q ∈ ℚ, n ∈ ℤ}This doesn't prove anything, but, to me, the game has the "smell" of requiring an ordered field to even make sense. Then for the trick to work, the field has to be Dedekind-complete. But the real numbers are the only such field (up to isomorphism).Overall the game feels very similar to one of Cantor's early, more analytic proofs of the fact that the reals are uncountable. Those proofs were all very tightly coupled to the analytics structure of the reals.But in the process of writing that proof he "saw" that it didn't depend on any of the analytic stuff. He wrote up a rough version of the diagonal argument which he sent to Dedekind in a letter, who then refined it into the proof that is typically taught today.There's something really special to me about Cantor's diagonal argument because diagonalization gets at the heart of the set-ness of (un-)countability. It might not be the most comfortable or natural, but it distills the essence of the concept.Remember, Cantor came to the concept of (un-)countability via harmonic analysis. His early proofs were all very analytic, so it wasn't comfortable or natural to him, either — at least at first! roenxi on Aug 4, 2020 [–] > All you need to believe is that an increasing sequence, bounded above, convergesThat isn't quite enough; because the final limit on the sequence is only determined after an infinite number of 'moves' in the game. The details of why it is true might be relevant here because it might interact with the strategies of players A and B.Does that interact with the a_n < α < b_n part of the proof in strange ways? I can say 0.9, 0.99, 0.999 are all < 1 and handwave an induction proof that 0.999... < 1 but that isn't true. Strange things happen at infinity and to verify that this proof isn't hand waving requires detailed consideration of quite complicated issues about how mechanically all these limits and convergences work. I suppose that is my real concern; I don't think it is supported that a_n < α < b_n for all n still forces convergence out of S; because it looks vaguely similar to the 0.999... = 1 issue. I'd look to the monotonic limit part of the proof for support there.I accept that this is just me not having a deep familiarity with these things, so the details will all turn out to support the proof and/or be irrelevant. But Cantor's proof is a lot easier on people who are reliant on working stuff out from first principles. I don't even need to look up definitions of convergence or think about strategic options at infinity.Say S is the rationals. For all a_n < α < b_n there are rationals in the interval. So it isn't immediately obvious that Bob's strategy is a winning strategy at infinity. Nobody can describe a game state where Alice has unambiguously lost. If n is finite Alice will clearly lose but the argument that she loses when n is infinite is going to be technical. The infinity where Bob wins might be a different infinity to the one where the series is forced to converge. Not all infinities are equal. I really don't understand your objection, mainly because I can't identify the referent of "the a_n < a < b_n part of the proof" in "Does that interact with the a_n < α < b_n part of the proof in strange ways?". I can't make "I don't think it is supported that a_n < a < b_n for all n still forces convergence out of S" be a meaningful sentence - it's the case that a_n < a < b_n, but certainly that doesn't force $a$ to lie outside S.If you restrict to the case when S is countable, then the thing that forces $a$ to lie outside S is rather that Bob has enumerated S and made certain that Alice's $a$ is bounded some concrete distance away from every s_n; in fact, for every $s_n$ he could tell you why $a$ is not equal to $s_n$, by telling you "$a$ is at least this much away from $s_n$" for each $n$. We don't even care what $a$ is; we just know that it's far away from every member of $S$. I had a few days to think about it and looked up the Wikipedia article for the monotonic limit theorum family and figured out what my confusion was about. I don't accept that theorem applies; and I don't think this game converges to a real number.Real numbers have a least upper bound . This game doesn't describe something with a least upper bound (assume the least upper bound is U, Bob will then pick a number < U as the upper bound, this contradicts - in the limit there is no upper bound unless the players agree to cooperate). I don't think the game describes a Real number - I think it describes some other mathematical object. roenxi on Aug 5, 2020 [–] Thanks for your time and attention on the matter; I've enjoyed the thread. I think you might have convinced me on that point; certainly my attempts to follow up were incoherent to the point where even I could tell.> I really don't understand your objectionBob's strategy is bunk, we've started by assuming something that is false. Therefore, the assumption that the reals are countable might already invalidate the proof that a bounded but monotonically increasing sequence converges. If that assumption is invalid, then the argument in this proof might already fail even before the contradiction we later identify. So it is obvious to me we're going to have a contradiction. But the contradiction might be elsewhere than in the true facts that the proof gives. So the proof might not be correct.I suppose I accept the proof will find a contradiction, but I'm not sure that the contradiction it found was the first one to arise. I can imagine that this might be a proof that Bob has a winning strategy without further argument:* Reals are countable* Bounded monotonic increasing sequence converges to a Real* These are inconsistent assumptions so I can prove anything* Therefore Bob has a winning strategySo that means all the additional logic the proof adds in has to be re-verified from first principles to ensure that everything is still valid and internally consistent as far as it went after assuming that the reals are countable. I'm not good enough at maths to know that this specific proof of a winning strategy doesn't contain subtle flaws, so I don't trust it (maybe proof by contradiction just isn't for me). I struggle to accept it as simpler - the Cantor proof constructs a direct counterexample and is very satisfying to me. I don't follow why Bob can play any legal move when s_n is not possible. The proposition is that, if S is countable, Bob has a winning strategy. Suppose S = (s1, s2, s3), which is finite and therefore countable. On turn 1 Alice picks s1. Since s1 is already taken, Bob picks any legal move, which means any number in [0, 1]. Suppose he picks s3. Then, Alice picks s2 and wins? They must continue playing. There is no termination condition for the game. They always continue playing an infinite number of steps.Alice picks s2. Then Bob picks some number less than s3, so the sequence does not converge to s3. Then Alice picks some number larger than s2, so the sequence does not converge to s2. Any number that is picked after a finite number of steps, cannot be the value that the sequence converges to. Ok, that makes more sense. The part I still don't get is how we can pick a number x such that s2 < x < s3 without directly assuming that [0, 1] is uncountable. Even the rational numbers have that property (the Archimedean property): for any distinct rationals s2 and s3, there exists a rational x such that s2 < x < s3.Proof: x = (s2 + s3) / 2.This is easily extended to show that there is an arbitrary number of such x. Even some subsets have that property, like eg all the finite decimal fractions. saiojd on Aug 3, 2020 [–] Thanks, that makes sense! Can you explain which part of that line of reasoning doesn't apply to rationals, which are countable? A sequence of rational numbers need not converge to a rational number, so you can't play the game with rationals. As a trivial example, consider the sequence of rational numbers 3, 3.1, 3.14, 3.141, 3.1415, ... converging to pi. You certainly can play the game with rationals, and Bob can win!The idea is that if Alice's sequence looks to be converging to some rational number α, well then α came up in Bob's enumeration of all rationals and was (by hypothesis) legal to play. So Bob played it, and then played something smaller next move! So Alice's sequence cannot converge to α. esrauch on Aug 3, 2020 [–] I kind of get it but it seems like a circular proof isn't it? As in, it seems that you are citing Cantor's Diagonal as a necessary precondition for the argument to hold for reals and not rationals. Specifically the "it will converge in the same infinite number space" was stated in the original argument with a reason that should apply to rationals, so I think it's an erroneous step? Well my math is quite rusty, but if I remember correctly, you can "define" reals using Dedekind cuts made of rational numbers - in this way you can trivially prove that a bounded increasing sequence converges to a real number (i.e., the reals are complete), without assuming anything about uncountability of reals. You can also not define anything up front; then take the proof that Bob can enforce that there's no convergence to any rational number.Next step, look at the process of playing the game, and show that you can define operations like adding any two games or comparing them for equality etc.(In some sense, that would be similar to showing that Dedekind cuts define a sensible structure. With the added complication that the game doesn't have to converge to arbitrary small intervals, because the players could agree to leave a finite interval like [1/4, 3/4] untouched, eg Alice plays 1/4-1/n and Bob plays 3/4+1/n.You'd just be defining interval arithmetic on real numbers.) I wonder if this further demonstrates the reality of the complex domain and the anachronism of the real number line? In that, numbers are “circularly” or ultimately geometrically countable and not sequentially? It does not demonstrate that, no. Complex numbers are no more "real" than real numbers are. They are uncountable, as another commenter said. In general they share many properties with real numbers because the sets C and R^2 are isomorphic and isometric with respect to each other. I was ignorant of the mathematically rigorous definition of countability, thanks. Think of the complex numbers chiefly as all the solutions to polynomials with coefficients that are real. The number "i" is the solution to the polynomial 0 = x^2 + 1. We choose to use a letter instead of a number simply because the numbers are already being used, similar to how hexadecimal uses letters. I like “imagining” them as geometrical because of the logical necessity of motion in the complex plane when processing their mathematical operations. The complex numbers are also uncountable. Proofs by contradiction are not accepted in some flavors of mathematics, like constructive mathematics. In fact, constructive mathematicians believe in a definition of real numbers that is more in line with what this paper talks about. I'm not familiar with this specific proof, but reading the description it sounds perfectly constructive.A true proof by contradiction would be "Assume [0, 1] is not uncountable. That leads to a contradiction, so [0, 1] is not not uncountable. By the law of the excluded middle, [0, 1] is therefore uncountable."This proof seems to be "Assume [0, 1] is countable. That leads to a contradiction, so [0, 1] is not countable." That's not a proof by contradiction - it's just how you prove a negative.This is a nice blog post about the distinction: https://existentialtype.wordpress.com/2017/03/04/a-proof-by-... > [0, 1] is not not uncountable. By the law of the excluded middle, [0, 1] is therefore uncountable.Nitpick: that's not excluded middle, that's double negation elimination. They're both non-constructive and (IIRC) equivalent in most formalizations, but they're not the same thing. Actually, the thing that is excluded in constructive mathematics is ~ ~ P -> P. ~ ~ ~ P -> ~ P is a theorem also in constructive mathematics. > ~ ~ ~ P -> ~ P is a theorem also in constructive mathematics.Could you provide a citation for this? I can vaguely see how that might work, being ~~Q->Q for the special case where Q can be decomposed into Q = ~P, but it's obviously rather difficult to search for. Here is a StackExchange post: https://math.stackexchange.com/questions/2453533/triple-nega... cjfd on Aug 4, 2020 [–] It is very easy to prove. Note first that ~P is an abbreviation for P -> False. So we can rewrite this as (~ ~ P -> False) -> P -> False. This is tautologically true by modes ponens if P -> ~ ~ P. But that is a well known fact. Oops, good catch. Nice comment. A succinct explanation of the difference between negation and contradiction can also be found in this r/math comment: https://reddit.com/r/math/comments/cu9gsk/_/exse1ps/?context...The terminology gets abused a lot, even by professors. It's actually hard to find theorems which really require proof by contradiction. Well, if your logical system defines "not P" as "assuming P, you can derive falsity", then "uncountable" precisely means "if you assume it is countable then you can derive falsity". That's exactly what the proof did. If you particularly care then you can just replace the final word "contradiction" with "QED"; it doesn't change the structure or content of the proof. Proofs that derive a contradiction are perfectly acceptable in constructive mathematics. Indeed, the real numbers are uncountable in constructive mathematics. What is not allowed is elimination of double negatives, which is not present in the above proof. I'm not sure that real numbers are uncountable in constructive mathematics as they are not computable. See Andrej Bauer's proof that they are indeed uncountable: https://mathoverflow.net/questions/30643/are-real-numbers-co... I'm still unconvinced. Is there a specific issue you have with this proof? With respect, I think you may be conflating a constructive proof of the uncountability of the reals with a proof that the set of all computable reals is countable. These are two different claims.A statement about the reals which is provable under constructive mathematics does not reduce to a statement about the computable reals and vice versa. A set can be constructively definable without all of its elements being constructively enumerable. ogogmad on Aug 2, 2020 [–] Given any explicit sequence of real numbers, it's always possible to generate a number not in that sequence. In fact, this can be done algorithmically using essentially Cantor's method. A simple diagonalization argument is perfectly constructive. Yes, and to clarify what I predict might be a point of contention about the necessity of "contradiction" in Cantor's argument, some of the comments in this thread might be helpful: https://reddit.com/r/math/comments/70xeon/why_is_cantors_dia... Ok I think what happens here is that we assume for the real numbers an increasing sequence which is bounded converges. I think that a number system with this property is probably already hard to construct in constructive math. No. The real numbers are constructed as located Dedekind cuts, or modulated Cauchy sequences. There are no issues with this construction in constructive mathematics.You are indeed right that you can't show that an increasing and bounded sequence of real numbers has a limit. But you can prove constructively that if a sequence of real numbers is Cauchy then it has a limit. And it is that last property which is the defining property of the real numbers (Cauchy completeness). So the problem that constructive math has for real numbers is that it's hard to show real numbers exist at all, not that it's uncountable if you have its properties. Also the deeper point is that you have all the properties of the real numbers you can actually derive the law of excluded middle. (Coming from the supremum axiom) > So the problem that constructive math has for real numbers is that it's hard to show real numbers exist at allNo. They exist in any topos with a Natural Number Object. In other words, they exist in all varieties of constructive mathematics that admit a set of natural numbers. Brouwer (father of intuitionism) rejected actual infinity. He would not admit the axiom of infinity and therefore reject the set of all natural numbers. Tough to do things that way though. If there isn't an actual infinity of Natural numbers, which is the largest? Brouwer distinguished between actual infinity and potential infinity, with the former inadmissible in intuitionism. He would say “the largest natural number” is a meaningless statement. You could only have the “largest so far”.Intuitionism invites you to construct as large of a natural number as you want. It simply does not admit “the complete set of all natural numbers”.The point of intuitionism is the idea that all mathematics is constructed by human creativity and logic. Brouwer rejected the idea that mathematics was “already out there, waiting to be discovered”. This is a subtle point. It says that mathematical objects do not exist in some mind-independent realm of truth. It has the nice property of avoiding some of the problems of classical mathematics that Hilbert got caught up in. Ok, so what is the largest Natural number so far? “So far” with respect to some particular problem you’re solving or process you’re following. If you’re talking about all problems, you’d have to do some research. Perhaps OEIS  could help you. Or you could interview some number theorists to find out who is working in large numbers and ask them.Asking the question in general, though, is equivalent to asking “what is the largest number anyone has thought of?” I would have to interrogate your motives to know why you would want to ask such a question.Intuitionists would scoff at the idea of a “number larger than anyone could describe.” That’s heading into the territory of the interesting number paradox . Intuitionism avoids this paradox by stating that numbers (and sets of numbers) have no existence independent of their construction. " “what is the largest number anyone has thought of?” I would have to interrogate your motives to know why you would want to ask such a question..."I ask because it's absurd. A particular large number is a logical thing regardless of whether a person thought of it before or whether it describes a distinct natural phenomenon. This follows from the set theory axioms, as well as Real numbers and infinitely many other number systems. To restrict our capacity to think of numbers to only numbers that people can enumerate or numbers that describe natural phenomena seems arbitrary and onerous. We construct the Real number simply by considering the limits of convergent sequences to be numbers. I don't see anything transgressive about this idea. Sure, some numbers are not computable, and other numbers can't be represented with marbles; they still have utility and there is no reason to make the concept of "numbers" exclusive. Smaug123 on Aug 3, 2020 [–] Certainly in Agda I've personally proved that the "Cauchy sequences of rationals" formulation is a partially ordered ring.However, I believe (but have not tried it and have not proved) that if you stick with Agda's incredibly strict and purely computational logic, the proof does indeed fall over. The problem is that Bob can't identify in general whether one real is less than another (indeed, this would imply solving the halting problem), so he can't know whether he's allowed to pick s_n at time n or not: he can't know whether s_n is less than his current number and hence a valid choice. This is really interesting. I'm not surprised by axiom of choice being based on real numbers. I've been thinking about that lately but I don't have a good intuition why. Do you have a link? I'd be very surprised if it were true in general. But there certainly has to be some non-computational component to the reals being a complete totally ordered Archimedean field, because the question of deciding the equality of two reals is uncomputable, so there is no procedure to decide the total order. Search: