1) The reason I describe the "increment forever" method of calculating 1 + ω as "very informal" is that it doesn't give us solid intuition about cases such as 1 + (ω + ω). Is there a difference between incrementing 1 for "one forever" and "two forevers"? I didn't want to cram too much detail into a single article, but if you're interested in a more principled approach, see this comment:
2) You often hear about "cardinal numbers", but they're not a part of the same hierarchy as normal numbers (ordinals). Their arithmetic is different and even more abstract.
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) If we construct a set of all the countable ordinals (0, 1, 2, ..., ω, ω + 1, ..., ω·2, ..., ω², ...), we can imagine an uncountable ordinal that's strictly greater and therefore can't be possibly "counted to" using these countable infinities. As with ω, there is no mathematical necessity for it to exist, but it's a thought experiment that unlocks even more weird math. This uncountable ordinal is called ω₁ and is associated with a new cardinal ℵ₁. We can't prove or disprove that ℵ₁ is the same as the cardinality of ℝ.
5) If you're rattled about the loss of commutativity for infinite numbers, it's often the first thing to go when we start messing around with numbers, even without infinity. For example, quaternion algebra (https://lcamtuf.substack.com/p/complex-numbers-2-a-world-in-3d) is non-commutative.
6) 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. The basic meaning of ω is the same, but there are some functional differences in how arithmetic operations are defined.
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
PS. Thanks to Christopher Sahnwaldt for correcting a subtle mistake in #4. More notes in the comments attached to this one.
Footnotes, part #2: for a more rigorous way to define the addition of infinite ordinals, we start with the two recursive rules inherited from Peano arithmetic:
Rule #1: A + 0 = A
Rule #2: A + S(B) = S(A+B)
However, as noted in the article, the second rule can be used to solve A + C only if the second operand is a successor ordinal that can be rewritten in the form of C = S(B). Ordinals such as ω are not successors. They are also known as limit ordinals and we need to invent a third rule to handle them.
The correct course of action doesn't naturally follow from what we know about finite numbers, so we're improvising, but we probably want three properties: (a) no overt paradoxes; (b) alignment with intuition about the "increment forever" thought experiment in the article; (c) associativity, especially since Peano rule #2 already effectively says this for the non-limit case: A + (B+1) = (A+B) + 1. Associativity is more basic than commutativity and it would suck to lose it.
To analyze the usual solution, recall that every ordinal other than zero embeds all the "lesser" ordinals:
2 = { 0, 1 }
5 = { 0, 1, 2, 3, 4 }
ω = { 0, 1, 2, ... }
ω · 2 = { 0, 1, 2, ...; ω, ω + 1, ω + 2, ... }
This means that the set union operator (∪) just gives us the larger of the two values - the lesser ordinal disappears:
In effect, calculating the union of any collection of ordinals gives us a single ordinal greater or equal to each "merged" value. This is known as the least upper bound, aka supremum.
With this in mind, the third rule for calculating A + B for a limit ordinal B can be expressed this way: for every element b in set B, recursively calculate sum A + b. Then, calculate the union of the resulting ordinals to obtain the supremum. This supremum is the value of A + B.
To show how this works, let's consider four test cases:
1) 2 + ω. Here, b iterates all natural numbers (because ω is just another name for ℕ). The resulting sequence of A + b sums is 2, 3, 4, 5, ... For the union, it doesn't matter if the merged sequence started at zero or two, because 2 already contains 0 and 1. The union is identical to the ordinal ω and aligns with the intuitive solution outlined in the article.
2) ω + ω. Once again, b iterates over all natural numbers. The A + b sequence is ω, ω + 1, ω + 2, ... The resulting union-ordinal evidently extends past ω to include all the successors of ω. This is ω · 2. Likewise, the result aligns with intuition.
3) (2 + ω) + ω. This can be deconstructed to #1 followed by #2: 2 + ω = ω, then ω + ω = ω · 2.
4) 2 + (ω + ω). The first addition produces ω · 2, as per #2. The second addition is analogous to #1, introducing an inconsequential starting offset to the infinite sums. The result is ω · 2, same as in #3, so we have associativity.
Footnotes, part #3 - in the article, I addressed four common critiques of Cantor:
1) "There should be just one kind of infinity." This is a philosophical belief, but it doesn't square with set theory that includes infinite sets.
2) "Infinite mathematical objects shouldn't exist." Once again, essentially a philosophical position; once you allow infinite sets, Cantor's argument follows.
3) "Different decimals can represent the same real". As discussed in the article, this problem is easily sidestepped, plus Cantor's argument also applies to power sets.
4) The ℕ-to-ℕ diagonalization to "prove" that ℵ₀ ≠ ℵ₀. This hinges on the spurious assumption that the constructed infinite sequence is in ℕ.
Here are two other examples I had no room for, but that come up in Google searches:
1) https://medium.com/@freefrancisco/was-cantor-wrong-a30802cf3152 - this is conceptually related to #4. The author posits an ℕ-to-E mapping (E = even numbers), sums all the values on the E side, and claims that the sum is an even number - so it's a missing element of the map. From Peano rules, we can show that the sum of all even numbers produces a set indistinguishable from the infinite ordinal ω, which is not in ℕ and therefore not in E. So, it's not an orphaned member of the map.
2) https://hesperusisbosphorus.wordpress.com/2016/07/31/what-is-wrong-with-cantors-diagonal-argument/ - based on a quick skim, this incorrectly assumes that the constructed diagonal sequence is the *only* real missing from the map. That's not what Cantor was trying to show. His argument was essentially that a complete line-by-line list of reals can't constructed. Assuming otherwise leads to contradictions that are in no way limited to a single missing value; it's just that it's enough to show one missing element to prove the impossibility of the task.
It was a really clear and nice refreshment for Cantor's proof for higher order infinity.
It's taking me back to grad school, when the professor argued that there're more real numbers in [0, 1] than the natural numbers altogether, it just blowed my mind up back then, and the proof of Cantor is so elegant and beautiful. It reminds me that beautiful ideas are usually quite simple!
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.
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.
Footnotes, part #1:
1) The reason I describe the "increment forever" method of calculating 1 + ω as "very informal" is that it doesn't give us solid intuition about cases such as 1 + (ω + ω). Is there a difference between incrementing 1 for "one forever" and "two forevers"? I didn't want to cram too much detail into a single article, but if you're interested in a more principled approach, see this comment:
https://lcamtuf.substack.com/p/how-has-mathematics-gotten-so-abstract/comment/216119337
2) You often hear about "cardinal numbers", but they're not a part of the same hierarchy as normal numbers (ordinals). Their arithmetic is different and even more abstract.
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) If we construct a set of all the countable ordinals (0, 1, 2, ..., ω, ω + 1, ..., ω·2, ..., ω², ...), we can imagine an uncountable ordinal that's strictly greater and therefore can't be possibly "counted to" using these countable infinities. As with ω, there is no mathematical necessity for it to exist, but it's a thought experiment that unlocks even more weird math. This uncountable ordinal is called ω₁ and is associated with a new cardinal ℵ₁. We can't prove or disprove that ℵ₁ is the same as the cardinality of ℝ.
5) If you're rattled about the loss of commutativity for infinite numbers, it's often the first thing to go when we start messing around with numbers, even without infinity. For example, quaternion algebra (https://lcamtuf.substack.com/p/complex-numbers-2-a-world-in-3d) is non-commutative.
6) 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. The basic meaning of ω is the same, but there are some functional differences in how arithmetic operations are defined.
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
PS. Thanks to Christopher Sahnwaldt for correcting a subtle mistake in #4. More notes in the comments attached to this one.
Footnotes, part #2: for a more rigorous way to define the addition of infinite ordinals, we start with the two recursive rules inherited from Peano arithmetic:
Rule #1: A + 0 = A
Rule #2: A + S(B) = S(A+B)
However, as noted in the article, the second rule can be used to solve A + C only if the second operand is a successor ordinal that can be rewritten in the form of C = S(B). Ordinals such as ω are not successors. They are also known as limit ordinals and we need to invent a third rule to handle them.
The correct course of action doesn't naturally follow from what we know about finite numbers, so we're improvising, but we probably want three properties: (a) no overt paradoxes; (b) alignment with intuition about the "increment forever" thought experiment in the article; (c) associativity, especially since Peano rule #2 already effectively says this for the non-limit case: A + (B+1) = (A+B) + 1. Associativity is more basic than commutativity and it would suck to lose it.
To analyze the usual solution, recall that every ordinal other than zero embeds all the "lesser" ordinals:
2 = { 0, 1 }
5 = { 0, 1, 2, 3, 4 }
ω = { 0, 1, 2, ... }
ω · 2 = { 0, 1, 2, ...; ω, ω + 1, ω + 2, ... }
This means that the set union operator (∪) just gives us the larger of the two values - the lesser ordinal disappears:
2 ∪ 5 = { 0, 1 } ∪ { 0, 1, 2, 3, 4 } = { 0, 1, 2, 3, 4 } = 5
In effect, calculating the union of any collection of ordinals gives us a single ordinal greater or equal to each "merged" value. This is known as the least upper bound, aka supremum.
With this in mind, the third rule for calculating A + B for a limit ordinal B can be expressed this way: for every element b in set B, recursively calculate sum A + b. Then, calculate the union of the resulting ordinals to obtain the supremum. This supremum is the value of A + B.
To show how this works, let's consider four test cases:
1) 2 + ω. Here, b iterates all natural numbers (because ω is just another name for ℕ). The resulting sequence of A + b sums is 2, 3, 4, 5, ... For the union, it doesn't matter if the merged sequence started at zero or two, because 2 already contains 0 and 1. The union is identical to the ordinal ω and aligns with the intuitive solution outlined in the article.
2) ω + ω. Once again, b iterates over all natural numbers. The A + b sequence is ω, ω + 1, ω + 2, ... The resulting union-ordinal evidently extends past ω to include all the successors of ω. This is ω · 2. Likewise, the result aligns with intuition.
3) (2 + ω) + ω. This can be deconstructed to #1 followed by #2: 2 + ω = ω, then ω + ω = ω · 2.
4) 2 + (ω + ω). The first addition produces ω · 2, as per #2. The second addition is analogous to #1, introducing an inconsequential starting offset to the infinite sums. The result is ω · 2, same as in #3, so we have associativity.
Footnotes, part #3 - in the article, I addressed four common critiques of Cantor:
1) "There should be just one kind of infinity." This is a philosophical belief, but it doesn't square with set theory that includes infinite sets.
2) "Infinite mathematical objects shouldn't exist." Once again, essentially a philosophical position; once you allow infinite sets, Cantor's argument follows.
3) "Different decimals can represent the same real". As discussed in the article, this problem is easily sidestepped, plus Cantor's argument also applies to power sets.
4) The ℕ-to-ℕ diagonalization to "prove" that ℵ₀ ≠ ℵ₀. This hinges on the spurious assumption that the constructed infinite sequence is in ℕ.
Here are two other examples I had no room for, but that come up in Google searches:
1) https://medium.com/@freefrancisco/was-cantor-wrong-a30802cf3152 - this is conceptually related to #4. The author posits an ℕ-to-E mapping (E = even numbers), sums all the values on the E side, and claims that the sum is an even number - so it's a missing element of the map. From Peano rules, we can show that the sum of all even numbers produces a set indistinguishable from the infinite ordinal ω, which is not in ℕ and therefore not in E. So, it's not an orphaned member of the map.
2) https://hesperusisbosphorus.wordpress.com/2016/07/31/what-is-wrong-with-cantors-diagonal-argument/ - based on a quick skim, this incorrectly assumes that the constructed diagonal sequence is the *only* real missing from the map. That's not what Cantor was trying to show. His argument was essentially that a complete line-by-line list of reals can't constructed. Assuming otherwise leads to contradictions that are in no way limited to a single missing value; it's just that it's enough to show one missing element to prove the impossibility of the task.
It was a really clear and nice refreshment for Cantor's proof for higher order infinity.
It's taking me back to grad school, when the professor argued that there're more real numbers in [0, 1] than the natural numbers altogether, it just blowed my mind up back then, and the proof of Cantor is so elegant and beautiful. It reminds me that beautiful ideas are usually quite simple!
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.
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.