1) Although a lot of online sources make that error, it's important to underscore that infinite cardinals such as ℵ₀ are *not* set sizes in any plain meaning of this term. The whole point is that there are several ways of measuring set size that are equivalent for finite sets, but *completely diverge* once you start talking about infinite sets. Cardinals are just one of the resulting hierarchies; there are other approaches that give you different results. Many internet attempts to "debunk" Georg Cantor's work are based on this misunderstanding.
2) In the same vein, you often hear about "cardinal numbers", but it's best not to think of infinite cardinals as normal (ordinal-like) numbers. Compared to ordinals, they're different mathematical beasts. They are not a label for a specific set; they are a label for an entire class of sets. There's a lot of baggage that comes with that.
3) There are multiple infinite ordinals that will have the same cardinality. For example, ℵ₀ (the cardinality of ℕ) covers ω, ω + 1, ω · 2, and so forth; ω is the "smallest" ordinal in the ℵ₀ class.
4) There are ordinals of higher cardinality, too. If you take the set of all the first-order ordinals that we know how to construct (0, 1, 2, ..., ω, ω + 1, ..., ω·2, ..., ω·3, ...), you will get a structure that embeds infinitely many infinite sequences separated by successor-discontinuities (see article). This construction corresponds to higher cardinality that can no longer be mapped to natural numbers. It nets us a new ordinal, ω₁, and a new cardinal ℵ₁. We can't prove or disprove that ℵ₁ is the same as the cardinality of ℝ.
5) If you read https://lcamtuf.substack.com/p/09999-1, you might be wondering if the arithmetic of infinite hyperintegers is different from infinite ordinals. It is, essentially because of the addition of some extra rules to make it more regular. That said, the basic meaning of ω is the same.
6) Toward the end of the article, we introduce the set of real numbers. The construction of reals is left as an exercise for the reader.
7) In addition to folks who object to the concept of infinity, there is a small number of mathematicians and philosophers who dislike set theory. For example, one prominent philosopher believes it's nonsensical to make a distinction between x and a set of containing x: https://ontology.buffalo.edu/04/AgainstSetTheory.pdf
I’ve always struggled with Cantor’s diagonal argument, and I’ve never found a satisfactory explanation of how to address my concern. We often remind ourselves that we don’t truly know how infinity behaves and therefore should be cautious in our reasoning. Yet the diagonal argument seems to proceed as if we could actually list all the real numbers between 0 and 1, and then construct a number not in that list. To me, the step “suppose we have listed them” feels meaningless, because such a listing cannot be carried out in the first place. (I am aware that the proof does not assume the list to be actually realized: suppose it were possible to arrange them in a complete list.)
Just to be clear: I’m not disputing Cantor’s conclusion. I know that mathematicians have established the same result through multiple rigorous approaches. My issue is specifically with how the diagonal argument is framed.
Yeah, it feels somewhat wonky. As you note, there are other ways to prove it, and in fact, the diagonal argument wasn't Cantor's first proof. Further, there are more rigorous versions of the proof that are expressed in terms of formal logic and that still hold.
I think the discomfort that people have with the proof boils down to the common-sense, philosophical understanding of infinity as a single, special place. But if you take basic set theory with the axiom of infinity (which is basically an arbitrary but widely-accepted assumption: "there exists an infinite set of natural numbers"), you can already show that there are different flavors of infinity. In particular, as we show in the article, ω+1 must be obviously larger than ω, and you don't need Cantor's argument for that.
If you accept infinite ordinals, then see footnote #4 in the comment pinned under the article: we can pretty easily visualize the ordinal ω₁, which, unlike ω+1, contains an infinity of infinite sequences. For me, this makes it easier to swallow that some ordinals might be impossible to map to a set containing only a finite number of infinite sequences.
Thanks for explaining that Zeno's paradox was successfully solved, mathematically I mean, via calculus. It's one of the paradoxes that I never, ever understood the premise for, whether mathematically or not. And I still don't understand why some people, even mathematicians, claimed it is a paradox at all.
Zeno's paradoxes were solved by Aristotle by introducing the distinction between act and potency. Remember that Zeno was a pupil of Parmenides, and the paradoxes are actually the result of Parmenides's monistic premises. The infinite divisions of the length aren't actually there, they are potentially there. The paradox only emerges if we conflate potentiality with actuality.
If one wanted to, they could still reject the mathematical solution because we don't know the structure of time and space on arbitrarily / infinitely small scales, so I guess it could behave differently than what calculus gives us for the continuum of real numbers.
That said, the fact that you can outrun a turtle suggests our mathematical answer is probably pretty close to reality..
I find it even simpler. Assuming, as the paradox sets up, constant speeds, then the distance shrinks not proportionally to the remaining distance, but by a fixed amount over time. Hence the fact that the turtle still moves forward is irrelevant, and only a distraction.
And this is why I say that I never understood the paradox. It would only apply if the reduction in distance is proportional to the remaining distance, in which case it is true (the paradox). Otherwise, the fact that the turtle still moves has no bearing 🤷🏻
I think the point of the paradox isn't that you couldn't get the correct result by *some* method, but that there was a particular method that seemed legit on the face of it, and yet gave a nonsensical answer. And that's the "let's analyze it based on the intervals needed to catch up with the turtle's last known position" approach.
If you have contradictory solutions, you have a paradox until you can show that one of the methods of solving the problem was wrong. And that took a while.
Maybe. As I said, I never understood the paradox, because to me it looks just like "a theoretical method disagrees with reality". But yes, I'm not a mathematician.
You're right in the sense that certain *assumptions* lead to the paradox, but it is in fact deeper than method. It is a matter of *metaphysical* error, specifically the Parmenidean metaphysical monism that Zeno was working from.
Some footnotes:
1) Although a lot of online sources make that error, it's important to underscore that infinite cardinals such as ℵ₀ are *not* set sizes in any plain meaning of this term. The whole point is that there are several ways of measuring set size that are equivalent for finite sets, but *completely diverge* once you start talking about infinite sets. Cardinals are just one of the resulting hierarchies; there are other approaches that give you different results. Many internet attempts to "debunk" Georg Cantor's work are based on this misunderstanding.
2) In the same vein, you often hear about "cardinal numbers", but it's best not to think of infinite cardinals as normal (ordinal-like) numbers. Compared to ordinals, they're different mathematical beasts. They are not a label for a specific set; they are a label for an entire class of sets. There's a lot of baggage that comes with that.
3) There are multiple infinite ordinals that will have the same cardinality. For example, ℵ₀ (the cardinality of ℕ) covers ω, ω + 1, ω · 2, and so forth; ω is the "smallest" ordinal in the ℵ₀ class.
4) There are ordinals of higher cardinality, too. If you take the set of all the first-order ordinals that we know how to construct (0, 1, 2, ..., ω, ω + 1, ..., ω·2, ..., ω·3, ...), you will get a structure that embeds infinitely many infinite sequences separated by successor-discontinuities (see article). This construction corresponds to higher cardinality that can no longer be mapped to natural numbers. It nets us a new ordinal, ω₁, and a new cardinal ℵ₁. We can't prove or disprove that ℵ₁ is the same as the cardinality of ℝ.
5) If you read https://lcamtuf.substack.com/p/09999-1, you might be wondering if the arithmetic of infinite hyperintegers is different from infinite ordinals. It is, essentially because of the addition of some extra rules to make it more regular. That said, the basic meaning of ω is the same.
6) Toward the end of the article, we introduce the set of real numbers. The construction of reals is left as an exercise for the reader.
7) In addition to folks who object to the concept of infinity, there is a small number of mathematicians and philosophers who dislike set theory. For example, one prominent philosopher believes it's nonsensical to make a distinction between x and a set of containing x: https://ontology.buffalo.edu/04/AgainstSetTheory.pdf
I’ve always struggled with Cantor’s diagonal argument, and I’ve never found a satisfactory explanation of how to address my concern. We often remind ourselves that we don’t truly know how infinity behaves and therefore should be cautious in our reasoning. Yet the diagonal argument seems to proceed as if we could actually list all the real numbers between 0 and 1, and then construct a number not in that list. To me, the step “suppose we have listed them” feels meaningless, because such a listing cannot be carried out in the first place. (I am aware that the proof does not assume the list to be actually realized: suppose it were possible to arrange them in a complete list.)
Just to be clear: I’m not disputing Cantor’s conclusion. I know that mathematicians have established the same result through multiple rigorous approaches. My issue is specifically with how the diagonal argument is framed.
Yeah, it feels somewhat wonky. As you note, there are other ways to prove it, and in fact, the diagonal argument wasn't Cantor's first proof. Further, there are more rigorous versions of the proof that are expressed in terms of formal logic and that still hold.
I think the discomfort that people have with the proof boils down to the common-sense, philosophical understanding of infinity as a single, special place. But if you take basic set theory with the axiom of infinity (which is basically an arbitrary but widely-accepted assumption: "there exists an infinite set of natural numbers"), you can already show that there are different flavors of infinity. In particular, as we show in the article, ω+1 must be obviously larger than ω, and you don't need Cantor's argument for that.
If you accept infinite ordinals, then see footnote #4 in the comment pinned under the article: we can pretty easily visualize the ordinal ω₁, which, unlike ω+1, contains an infinity of infinite sequences. For me, this makes it easier to swallow that some ordinals might be impossible to map to a set containing only a finite number of infinite sequences.
HN endorsements, for posterity:
"Why read this? Why be exposed to this slop?"
"A watered down Intro to Mathematics 101"
If I could read these comments, I would be very upset
Can you re-write your example in rust? it's safer.
No, but here's set theory in bash:
$ mkdir 0
$ function succ () { [ $# = 2 ] && cp -r "$1/." "$2/" && cp -r "$1" "$2/"; }
$ succ 0 1
$ succ 1 2
$ succ 2 3
Forgive me senpai
Thanks for explaining that Zeno's paradox was successfully solved, mathematically I mean, via calculus. It's one of the paradoxes that I never, ever understood the premise for, whether mathematically or not. And I still don't understand why some people, even mathematicians, claimed it is a paradox at all.
Zeno's paradoxes were solved by Aristotle by introducing the distinction between act and potency. Remember that Zeno was a pupil of Parmenides, and the paradoxes are actually the result of Parmenides's monistic premises. The infinite divisions of the length aren't actually there, they are potentially there. The paradox only emerges if we conflate potentiality with actuality.
If one wanted to, they could still reject the mathematical solution because we don't know the structure of time and space on arbitrarily / infinitely small scales, so I guess it could behave differently than what calculus gives us for the continuum of real numbers.
That said, the fact that you can outrun a turtle suggests our mathematical answer is probably pretty close to reality..
I find it even simpler. Assuming, as the paradox sets up, constant speeds, then the distance shrinks not proportionally to the remaining distance, but by a fixed amount over time. Hence the fact that the turtle still moves forward is irrelevant, and only a distraction.
And this is why I say that I never understood the paradox. It would only apply if the reduction in distance is proportional to the remaining distance, in which case it is true (the paradox). Otherwise, the fact that the turtle still moves has no bearing 🤷🏻
I think the point of the paradox isn't that you couldn't get the correct result by *some* method, but that there was a particular method that seemed legit on the face of it, and yet gave a nonsensical answer. And that's the "let's analyze it based on the intervals needed to catch up with the turtle's last known position" approach.
If you have contradictory solutions, you have a paradox until you can show that one of the methods of solving the problem was wrong. And that took a while.
Maybe. As I said, I never understood the paradox, because to me it looks just like "a theoretical method disagrees with reality". But yes, I'm not a mathematician.
You're right in the sense that certain *assumptions* lead to the paradox, but it is in fact deeper than method. It is a matter of *metaphysical* error, specifically the Parmenidean metaphysical monism that Zeno was working from.