3 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 conver

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

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