12 ms·
How real are real numbers? (2004)
- Smaug123 6y agoI 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 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.
- avani 6y agoIn 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 https://www.cs.virginia.edu/luther/blog/posts/124.html: "Any real number can be represented as an integer followed by a decimal point and an infinite sequence of digits. Let’s ignore the integer part for now and only consider real numbers between 0 and 1. Now we need to show that all pairings of infinite sequences of digits to integers of necessity leaves out some infinite sequences of digits. Let’s say our candidate pairing maps positive integer i to real number r_i. Let’s also denote the digit in position i of a real number x as x_i. Thus, if one of our pairings was (17, 0.651249324…) then r_17^4 would be 2. Now, consider the special number z, where z_i is the bottom digit of r_i^i + 1. The number z above is a real number between 0 and 1 and is not paired with any positive integer. Since we can construct such a z for any pairing, we know that every pairing has at least one number not in it. Thus, the lists aren’t the same size, meaning that the list of real numbers must be bigger than the list of integers."
- kmill 6y agoBefore 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! See theorem 2: https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Gray819-832.pdf https://www.maa.org/sites/default/files/pdf/upload_library/2... (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 6y agoThe 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 6y agoYes. Though that problem is repairable.
- eru 6y agoCantor'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.
- adamnemecek 6y agoProofs 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.
- millimeterman 6y agoI'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-contradiction-is-not-a-proof-that-derives-a-contradiction/ https://existentialtype.wordpress.com/2017/03/04/a-proof-by-...
- fractionalhare 6y agoNice 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=1 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.
- Smaug123 6y agoWell, 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.
- a1369209993 6y ago
- achillesheels 6y agoI 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?
- ogogmad 6y agoThe complex numbers are also uncountable.
- fractionalhare 6y agoIt 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.
- achillesheels 6y agoI was ignorant of the mathematically rigorous definition of countability, thanks.
- mike00632 6y agoThink 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.
- achillesheels 6y agoI like “imagining” them as geometrical because of the logical necessity of motion in the complex plane when processing their mathematical operations.
- saiojd 6y agoI 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 6y agoThey 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.
- saiojd 6y agoOk, 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.
- blake1 6y agoEven 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.
- gautamcgoel 6y agoThe 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.
- esrauch 6y agoCan you explain which part of that line of reasoning doesn't apply to rationals, which are countable?
- yongjik 6y agoA 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.
- esrauch 6y agoI 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?
- yongjik 6y agoWell 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. [1] https://en.wikipedia.org/wiki/Dedekind_cut https://en.wikipedia.org/wiki/Dedekind_cut
- eru 6y agoYou 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.)
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- ridiculous_fish 6y agoI 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.
- roenxi 6y agoThis 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.
- Smaug123 6y agoAll 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.
- jfarmer 6y ago> 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.
- deleted 6y ago[deleted]
- karmakaze 6y ago> We discuss mathematical and physical arguments against continuity and in favor of discreteness I 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?
- karmakaze 6y ago[I'll assume the downvote was a misclick and that math/physics hasn't also become political.]
- sebastialonso 6y agoI don't understand. You didn't say anything remotely political
- ojnabieoot 6y agoThe 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 out A lot of mathematicians would consider this a very limited view of the subject.
- asdf_snar 6y ago> A lot of mathematicians would consider this a very limited view of the subject. Could you provide an example of such a mathematician?
- zornthewise 6y agoI am one such mathematician.
- 6y ago
- deleted 6y ago[deleted]
- rurban 6y agoSo the answer is unexpected: real enough.
- dmch-1 6y agoReal 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).
- Koshkin 6y agoBut an abstraction is always an extension of reality.
- mike00632 6y agoThe 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/Smoothness https://en.wikipedia.org/wiki/Smoothness If it turns out that reality is actually jagged at the quantum scale that doesn't mean that our conception of "smooth" is void.
- Koshkin 6y agoExactly 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 6y agoLike phlogiston.
- Koshkin 6y agoThat one was a physical hypothesis, not a mathematical abstraction.
- montecarl 6y agoIf 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)?
- andromaton 6y agoYes, computable numbers (0) 0:https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number
- karmakaze 6y ago> 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.
- colordrops 6y agoIsn't this just comparing two infinite wavefronts? Isn't there an infinite number of texts in French?
- missblit 6y agoThere are a countably infinite number of French sentences, but there are uncountably many reals. So there exist reals that cannot be described in French.
- missblit 6y ago> 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 = .7139847654 S_1 = .111111111111 S_2 = .93939 S_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!) [1] https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
- patfla 6y agoI 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.
- mike00632 6y agoWe would still be able to think about a half a Planck length.
- mike00632 6y agoThis 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 https://en.wikipedia.org/wiki/Nonstandard_analysis
- karmakaze 6y agoThank you. https://en.wikipedia.org/wiki/Construction_of_the_real_numbers https://en.wikipedia.org/wiki/Construction_of_the_real_numbe...
- wrycoder 6y agoGregory Chaitin https://en.m.wikipedia.org/wiki/Gregory_Chaitin https://en.m.wikipedia.org/wiki/Gregory_Chaitin
- mike00632 6y agoYes, 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.
- gthtjtkt 6y agoSounds real enough for me.
- GregoryVPerry 6y agoSo basically, float sucks.