4 ms·

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 converg

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.
- eru 6y ago
  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.
  - Smaug123 6y ago
    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 6y ago
      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 6y ago
    > 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).
    - 6y ago
roenxi 6y ago
> All you need to believe is that an increasing sequence, bounded above, converges 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.
- Smaug123 6y ago
  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$.

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.

eru 6y ago
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.
- Smaug123 6y ago
  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 6y ago
    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 6y ago
  > 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).
  - 6y ago

roenxi 6y ago

> All you need to believe is that an increasing sequence, bounded above, converges 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.

Smaug123 6y ago
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$.