81 points by MindGods on Aug 2, 2020 | hide | past | favorite | 112 comments

 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."
 kmill on Aug 2, 2020 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.)
 jwilk on Aug 3, 2020 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.
 eru on Aug 4, 2020 Yes. Though that problem is repairable.
 eru on Aug 4, 2020 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.
 eru on Aug 4, 2020 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.
 eru on Aug 4, 2020 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).
 eru on Aug 6, 2020 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 [0]. 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.
 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?
 lmkg on Aug 2, 2020 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.
 eru on Aug 4, 2020 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[1] 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.
 eru on Aug 4, 2020 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.
 mike00632 on Aug 3, 2020 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.
 ogogmad on Aug 2, 2020 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.
 cjfd on Aug 3, 2020 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.
 millimeterman on Aug 3, 2020 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.
 ogogmad on Aug 2, 2020 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.
 millimeterman on Aug 2, 2020 A simple diagonalization argument is perfectly constructive.
 Davidzheng on Aug 2, 2020 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).
 Davidzheng on Aug 2, 2020 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?
 " “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.
 adamnemecek on Aug 2, 2020 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.
 > The first person to notice this difficulty was Jules Richard in 1905, and the manner in which he formulated the problem is now called Richard’s paradox. Here is how it goes.> Since all possible texts in French (Richard was French) can be listed or enumerated, a first text, a second one, etc., 2 you can diagonalize over all the reals that can be defined or named in French and produce a real number that cannot be defined and is therefore unnameable. However, we’ve just indicated how to define it or name it! In other words, Richard’s paradoxical real differs from every real that is definable in French, but nevertheless can itself be defined in French by specifying in detail how to apply Cantor’s diagonal method to the list of all possible mathematical definitions for individual real numbers in French!I followed this up to "and produce a real number that cannot be defined". Would this be from some computation on some/all of the diagonalized reals? I can't see how to guarantee that this generated number wasn't already in the set.
 > I can't see how to guarantee that this generated number wasn't already in the set.The trick here is the diagonal argument [1].The set (S) contains all real numbers that can be described by a valid French sentence (enumerating French sentences in some fixed order). For example we could come up with an enumeration such that the first few elements are:S_0 = .7139847654S_1 = .111111111111S_2 = .93939S_3 = .313331333133 repeating...We can construct a diagonal number r such that the ith digit of r differs from the ith digit of S_i for all S_i in S:r = 0.8204... (8 = 1 + S_0[0], 2 = 1 + S_1[1], 0 = S_2[2] + 1, etc)For any element S_i in S; r and S_i differ in at least one digit (because we constructed it that way); which is why r is guaranteed to not be in S.(But this argument can be translated to French, hence the paradox!)
 Ah got it. This seems different than the idea of there being 'more' real numbers and is rather a quirk of an unclear specification of set membership. This seems to be covered in 'Richardian Numbers'[0]
 I am similarly confused, Is Richard's paradox really a paradox, since the 'diagonalized' mapping of texts to reals is not the same as the implied 'meaning-based' one?'meaning-based' mapping is not bijective - both texts 'pi' and 'the number pi' map to the same real.On the other hand the 'diagonalization' mapping doesn't care about the new real: texts which describe how to obtain it are already assigned to an arbitrary real.
 Isn't this just comparing two infinite wavefronts? Isn't there an infinite number of texts in French?
 There are a countably infinite number of French sentences, but there are uncountably many reals.So there exist reals that cannot be described in French.
 > We discuss mathematical and physical arguments against continuity and in favor of discretenessI can appreciate the physical arguments which makes me think of this as a question in physics. What might the mathematical ones be? Math is about defining a system and playing it out, what would make continuous numbers off-limits?
 The article goes into significant detail, but the problem is that the computable real numbers are a tiny slice of all real numbers, and in general even in principle mathematicians can only deal with a countable subset of the reals. So (metamathematically) if almost every single real can't actually be used in mathematics, it's hard to say the concept has much mathematical validity. [Which makes its mathematical usefulness a philosophical pickle.]> Math is about defining a system and playing it outA lot of mathematicians would consider this a very limited view of the subject.
 > in general even in principle mathematicians can only deal with a countable subset of the reals. So (metamathematically) if almost every single real can't actually be used in mathematics, it's hard to say the concept has much mathematical validity.Let me give it try:> let R be the set of real numbers. Let x be an element of R.There it is, I've dealt with and used every single real number.The notion that reals are only real when they are individually described (Borel's credo in the article) is an odd one. Sure, almost every real number is a "Mathematical fantasy" as the author calls it, but that doesn't mean Mathematicians can't use them or deal with them.Mathematics excels in dealing with imaginary things. To extent Borel's credo to question the Mathematical validity of these Mathematical fantasies seems to defy the entire idea of Mathematics.
 > A lot of mathematicians would consider this a very limited view of the subject.Maybe? A lot of mathematicians actually do describe it just like that.In fact that's one of the most common ways the difference between mechanical arithmetic and research mathematics is described on forums like r/math. And a lot of posts on Math Overflow have precisely the flavor of defining things and then playing around with what consequences emerge.
 karmakaze on Aug 3, 2020 I see. We actually failed to 'define a system' for what it means to be a real number. What the set of real numbers contains can't be defined in any strict formal way.Even for the range [0, 1] saying all numbers including rationals and irrationals is an incomplete cop-out. The rationals are defined. Only some irrationals are/can-be. Saying a 'number that is not rational' is not a definition--it is negative space. Prime numbers are the negative space of composite numbers--they are however countable and computable. The negative space within real numbers is different. There are no possible constructions to reach some/all of them.Does the same problem arise with any uncountably infinite set or only not-well defined ones? Is "The Set of all Subsets of Natural Numbers" (which is uncountable) also non-mathematical in the same sense? A program (requiring infinite storage and computation time) can be constructed.
 "What the set of real numbers contains can't be defined in any strict formal way."On the contrary. There are multiple ways to rigorously define the Real Numbers. The most popular way is perhaps Cauchy sequence: https://en.wikipedia.org/wiki/Cauchy_sequenceThere are also Dedekind cuts: https://en.wikipedia.org/wiki/Dedekind_cut
 mike00632 on Aug 3, 2020 Well, a lot of math doesn't use continuous sets of numbers. Lots of algebra is done using countably infinite sets of numbers like the rationals and the algebraic completion of the rationals. It's about using the right tool for the job. And to that end, the computable numbers are more of a curiosity than something of practical use. Compared to the Reals, the computable numbers are difficult to define and have a lot of logical overhead for virtually no gain. Also, logically, you will never see most all numbers even from a countably infinite set, so a very similar qualm can be had with computable numbers being used in place of the reals (for wherever they can be substituted, which isn't all situations we encounter in math).
 contravariant on Aug 2, 2020 >A lot of mathematicians would consider this a very limited view of the subject.I'm not sure it's as limited as you think it is.It's not very specific though I'll give you that.
 asdf_snar on Aug 2, 2020 > A lot of mathematicians would consider this a very limited view of the subject.Could you provide an example of such a mathematician?
 shezi on Aug 3, 2020 "One of the main themes of the book is the beauty that mathematics possesses, which Hardy compares to painting and poetry.[5] For Hardy, the most beautiful mathematics was that which had no practical applications in the outside world (pure mathematics) and, in particular, his own special field of number theory." -- https://en.m.wikipedia.org/wiki/A_Mathematician's_ApologyG. H. Hardy, A mathematician's apology. I think that would be a good example here, since the focus is on finding beauty and fulfilment, instead of simply visiting every niche.
 shezi on Aug 3, 2020 "Nevertheless, the fact is that there is nothing as dreamy and poetic, nothing as radical, subversive, and psychedelic, as mathematics. It is every bit as mind blowing as cosmology or physics (mathematicians conceived of black holes long before astronomers actually found any), and allows more freedom of expression than poetry, art, or music (which depend heavily on properties of the physical universe). Mathematics is the purest of the arts, as well as the most misunderstood."Paul Lockhart, a mathematicians lament. I think this serves as another example.
 zornthewise on Aug 3, 2020 I am one such mathematician.
 the paper lays this out: it’s just really weird that essentially all real numbers cannot be named, described, or known to us. (or computed by any Turing machine, if you want to avoid paradoxes of natural language.) if you randomly sample a real number, with 100% probability it will be one of these strange, unknowable numbers.this is quite weird! i’ve only ever seen nameable, computable numbers in my whole life, yet apparently drawing one of these from a uniform random sample has probability 0?fortunately IIRC the subset of computable real numbers still forms a field and behaves how we want, although you can only test equality up to some epsilon.
 I found Matt Parker's video to be a good way to visualize the fact that we 'know' essentailly 0% of numbers: https://www.youtube.com/watch?v=5TkIe60y2GI
 mike00632 on Aug 3, 2020 The negative numbers and the number zero have similar problems with being fully manifested in our physical experience. Numbers are a logical tool and what the full range of Real Numbers gives us is the logical foundation for "smoothness".Also, of the discrete Natural numbers, you are unlikely to witness in your entire lifetime any number larger than 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10, i.e. virtually all of the numbers are inaccessible to you except for in your imagination.
 it’s not about physical experience, though. you just described zero, negative numbers, and 10^10^10...what’s weird is that almost all numbers are inaccessible, even in our imaginations.
 The real numbers are perfectly accessable in our imaginations. They just have different properties than some other numbers and are used for different things. It would be similarly absurd to say that we can't "access" negative numbers in our heads. Of course we can. We can construct the Real numbers and consider them in their entirety. In fact, we have a conception of the Reals as we use them in other mathematics.
 [I'll assume the downvote was a misclick and that math/physics hasn't also become political.]
 I don't understand. You didn't say anything remotely political
 His physical arguments are atrocious though, even refers to Zeno.
 If it is not possible to compute most reals, then is there a number system, with only computable numbers that extends the rational numbers to include computable reals such as Pi, e, sqrt(2)?
 Yes, computable numbers (0) 0:https://en.m.wikipedia.org/wiki/Computable_number
 Real numbers are a convenient abstraction which help us think about certain things. They don't have to be any more real than that. (Have not read the article though, sorry if this comment is irrelevant).
 But an abstraction is always an extension of reality.
 The concept of "smooth" is fairly rooted in reality, right? This is one of the concepts that a continuous set of numbers like the Real Numbers can accommodate: https://en.wikipedia.org/wiki/SmoothnessIf it turns out that reality is actually jagged at the quantum scale that doesn't mean that our conception of "smooth" is void.
 Exactly so. When reality becomes too complex, we abstract some things away to get a simpler model. (This we "forget" about the finite and get infinity; ignore the jaggedness and get smoothness).
 GoblinSlayer on Aug 3, 2020 Like phlogiston.
 That one was a physical hypothesis, not a mathematical abstraction.
 I read this intriguing thing once to the effect that: if space and time were discrete, say, at the Planck scale, that the infinities that bedevil modern physics would, magically, disappear. No more renormalization - no more many things.
 We would still be able to think about a half a Planck length.
 So the answer is unexpected: real enough.
 Sounds real enough for me.
 This is pretty far into crank territory.One of the issues with this paper is simply a misunderstanding of terms. The word "real" as in "real numbers" is jargon. It's not about whether or not you believe in them or even whether they are representative of reality. You can think of them entirely in logical terms (whether logically constructed with Cauchy sequences or Dedekind cuts) and then the disagreement is about the axioms of set theory.Numbers are just a theoretical framework, that is how they are used and "believed in". If you want to say that real numbers are absurd or not fitting of our world then simply propose an alternative theory that we could elect to use instead of real numbers. Nobody is adamant about the idea of all real numbers being "real" in every sense of the word.Furthermore, a theory of numbers with a restriction on the size of the set is arbitrary. Cantor's diagonalization argument and construction methods still exist. To exclude uncountably infinite sizes of sets would make as much logical sense as restricting the total number of numbers to something finite, e.g. "there can be no numbers greater than a hundred billion, try not to think of a hundred billion and one because that is bullocks!".An interesting example of irksome numbers being remedied with better theories is the concept of infinitesimals in calculus/analysis. The theory of Nonstandard Analysis provides a rigorous definition of infinitesimals in terms of more familiar numbers. https://en.wikipedia.org/wiki/Nonstandard_analysis
 Gregory Chaitin
 Yes, this is the author of the paper. He is neither a number theorist nor a physicist. So any claims he makes about upending physics and number theory should be taken with a grain of salt.

Search: