10 ms·

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

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 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 ago
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 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 ago
  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! 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 ago
  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 6y ago
    Yes. Though that problem is repairable.
- eru 6y ago
  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.
adamnemecek 6y ago
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.
- millimeterman 6y ago
  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-contradiction-is-not-a-proof-that-derives-a-contradiction/ https://existentialtype.wordpress.com/2017/03/04/a-proof-by-...
  - fractionalhare 6y ago
    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=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 ago
      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.
  - a1369209993 6y ago
achillesheels 6y ago
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?
- ogogmad 6y ago
  The complex numbers are also uncountable.
- fractionalhare 6y ago
  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.
  - achillesheels 6y ago
    I was ignorant of the mathematically rigorous definition of countability, thanks.
- mike00632 6y ago
  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.
  - achillesheels 6y ago
    I like “imagining” them as geometrical because of the logical necessity of motion in the complex plane when processing their mathematical operations.
saiojd 6y ago
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 6y ago
  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.
  - saiojd 6y ago
    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.
    - blake1 6y ago
      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.
      - saiojd 6y ago
        Thanks, that makes sense!
      - eru 6y ago
        Even some subsets have that property, like eg all the finite decimal fractions.
gautamcgoel 6y ago
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.
esrauch 6y ago
Can you explain which part of that line of reasoning doesn't apply to rationals, which are countable?
- yongjik 6y ago
  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.
  - esrauch 6y ago
    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?
    - yongjik 6y ago
      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. [1] https://en.wikipedia.org/wiki/Dedekind_cut https://en.wikipedia.org/wiki/Dedekind_cut
      - eru 6y ago
        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.)
deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
ridiculous_fish 6y ago
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.
roenxi 6y ago
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.
- Smaug123 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.) 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.

avani 6y ago

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 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 ago
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! 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 ago
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 6y ago
  Yes. Though that problem is repairable.
eru 6y ago
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.

adamnemecek 6y ago

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.

millimeterman 6y ago
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-contradiction-is-not-a-proof-that-derives-a-contradiction/ https://existentialtype.wordpress.com/2017/03/04/a-proof-by-...
- fractionalhare 6y ago
  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=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 ago
    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.
- a1369209993 6y ago

achillesheels 6y ago

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?

ogogmad 6y ago
The complex numbers are also uncountable.
fractionalhare 6y ago
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.
- achillesheels 6y ago
  I was ignorant of the mathematically rigorous definition of countability, thanks.
mike00632 6y ago
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.
- achillesheels 6y ago
  I like “imagining” them as geometrical because of the logical necessity of motion in the complex plane when processing their mathematical operations.

saiojd 6y ago

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 6y ago
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.
- saiojd 6y ago
  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.
  - blake1 6y ago
    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.
    - saiojd 6y ago
      Thanks, that makes sense!
    - eru 6y ago
      Even some subsets have that property, like eg all the finite decimal fractions.

gautamcgoel 6y ago

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.

esrauch 6y ago

Can you explain which part of that line of reasoning doesn't apply to rationals, which are countable?

yongjik 6y ago
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.
- esrauch 6y ago
  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?
  - yongjik 6y ago
    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. [1] https://en.wikipedia.org/wiki/Dedekind_cut https://en.wikipedia.org/wiki/Dedekind_cut
    - eru 6y ago
      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.)

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

ridiculous_fish 6y ago

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.

roenxi 6y ago

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.

Smaug123 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.) 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.