How real are real numbers? (2004)
arxiv.org
arxiv.org
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.
"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."
See theorem 2: 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.)
For example, if all digits on the diagonal were 8, then z = 0.(9) = 1, which is not between 0 and 1.
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-...
The terminology gets abused a lot, even by professors. It's actually hard to find theorems which really require proof by contradiction.
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.
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.
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.
No. 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.
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.
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 [2]. Intuitionism avoids this paradox by stating that numbers (and sets of numbers) have no existence independent of their construction.
[2] https://en.wikipedia.org/wiki/Interesting_number_paradox
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.
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.
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).
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.
Proof: x = (s2 + s3) / 2.
This is easily extended to show that there is an arbitrary number of such x.
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.)
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 α.
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 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.
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.
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.
> 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.
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.
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).
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.
1. In an ultrametric space like the p-adics (ℚₚ), two open balls are either totally disjoint or one is a subset of the other
2. 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!
That 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.
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 really don't understand your objection
Bob'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 strategy
So 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.
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.
[0] https://en.wikipedia.org/wiki/Least-upper-bound_property
> 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.
So there exist reals that cannot be described in French.
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
'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.
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?
> Math is about defining a system and playing it out
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.
Could you provide an example of such a mathematician?
G. 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.
Paul Lockhart, a mathematicians lament. I think this serves as another example.
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.
I'm not sure it's as limited as you think it is.
It's not very specific though I'll give you that.
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.
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_sequence
There are also Dedekind cuts: https://en.wikipedia.org/wiki/Dedekind_cut
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.
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.
what’s weird is that almost all numbers are inaccessible, even in our imaginations.
If it turns out that reality is actually jagged at the quantum scale that doesn't mean that our conception of "smooth" is void.
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