How can some infinities be bigger than others?(quantamagazine.org)
quantamagazine.org
How can some infinities be bigger than others?
https://www.quantamagazine.org/how-can-some-infinities-be-bigger-than-others-20230419/
228 comments
You know the Infinite Hotel problem, right?
You have a Hotel with infinite rooms in it. An Infinite Bus shows up with infinite passengers. As each passenger comes into the lobby, you give them the next room key, so that everyone gets a room.
An hour later another Infinite Bus shows up. Oh dear. Now what will you do? You call the manager and he says no problems. What you're going to do is go to room 1, apologize and ask them to kindly relocate to room 2. Offer a complimentary breakfast by way of apology. Then go to each subsequent room and ask the inhabitants to move from their room number to 2n. Now that all of the current guests have moved to their new, even numbered rooms, you can put the second bus into the odd numbered rooms and everyone is happy.
As Standup Maths recently pointed out, the problem is that we think of infinity as "count until you get really tired of counting and then it's one more than that". Which is just not a workable definition and causes problems.
You have a Hotel with infinite rooms in it. An Infinite Bus shows up with infinite passengers. As each passenger comes into the lobby, you give them the next room key, so that everyone gets a room.
An hour later another Infinite Bus shows up. Oh dear. Now what will you do? You call the manager and he says no problems. What you're going to do is go to room 1, apologize and ask them to kindly relocate to room 2. Offer a complimentary breakfast by way of apology. Then go to each subsequent room and ask the inhabitants to move from their room number to 2n. Now that all of the current guests have moved to their new, even numbered rooms, you can put the second bus into the odd numbered rooms and everyone is happy.
As Standup Maths recently pointed out, the problem is that we think of infinity as "count until you get really tired of counting and then it's one more than that". Which is just not a workable definition and causes problems.
To be honest, I don't like any of these "examples" at all because they attempt to map "intuitive" concepts, which are things like "size", "more than" and "fewer than" when applied to something that is finite, to something where that intuition doesn't even make sense in the infinite realm.
I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel? After all, if it's an infinite bus, people will always keep streaming out of it. When you ask the guests to move from door x to 2x, that request never finishes, so you never are able to stop and then ask for guests from the other infinite bus to access the odd rooms.
What actually helped me understand the concept of the cardinality of infinite sets is to get rid of the whole notions of "size", "more than", "fewer than", etc. and instead just stick to the concept of mapping: is there a single, deterministic function that can output a unique value Y, where Y exists in some particular set, for every input value X, where X comes from another set.
Honestly, I think trying to use the same words like "size of" when talking about infinite sets was a mistake.
I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel? After all, if it's an infinite bus, people will always keep streaming out of it. When you ask the guests to move from door x to 2x, that request never finishes, so you never are able to stop and then ask for guests from the other infinite bus to access the odd rooms.
What actually helped me understand the concept of the cardinality of infinite sets is to get rid of the whole notions of "size", "more than", "fewer than", etc. and instead just stick to the concept of mapping: is there a single, deterministic function that can output a unique value Y, where Y exists in some particular set, for every input value X, where X comes from another set.
Honestly, I think trying to use the same words like "size of" when talking about infinite sets was a mistake.
"I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel?"
This is easy, you need to shout at the people so each person leaves the bus twice as fast as the previous one. For example the frst person needs 1 minute to leave the bus, the second 0.5 minute, etc. In 2 minutes the bus is empty :)
This is easy, you need to shout at the people so each person leaves the bus twice as fast as the previous one. For example the frst person needs 1 minute to leave the bus, the second 0.5 minute, etc. In 2 minutes the bus is empty :)
If it breaks your brain less, you can think of it as the tour guide comes off bus 1 comes in and ask if there is enough room. The clerk says yes and the people start filing off the bus. Eventually they all will get a room. Then an hour later a second bus shows up and asks the same. Now the clerk isn’t sure.
Of course you can’t have an infinite hotel. The construction time would be murder and you can only manage so many people so you have an infinite number of cleaning staff reporting to an infinite number of middle managers. And it takes you forever to do pay stubs. But that’s why it’s a thought experiment.
Of course you can’t have an infinite hotel. The construction time would be murder and you can only manage so many people so you have an infinite number of cleaning staff reporting to an infinite number of middle managers. And it takes you forever to do pay stubs. But that’s why it’s a thought experiment.
> But that’s why it’s a thought experiment.
My point is I think it's a bad thought experiment. In my opinion just using the actual "mapping" concept directly is much less confusing than clumsily reusing the definition of "size" and other concepts that are really irrelevant in an infinite world.
My point is I think it's a bad thought experiment. In my opinion just using the actual "mapping" concept directly is much less confusing than clumsily reusing the definition of "size" and other concepts that are really irrelevant in an infinite world.
That example doesn't help you with Galileo's Paradox. In fact it says after the infinitely many new guests arrived, there are now still just "as many" guests as before, even though the new guests are a proper subset of the total guests. The problem is whether you accept this definition of "as many". You could also follow Galileo and say that size comparisons of infinite quantities don't make sense.
This is an interesting idea but I don't get how it works in practice. For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other. Are you suggesting these be treated as "the same size as" one another? Because if so, then {1,2,3,4} is "the same size as" both {A,B,C} and {A,B,C,D}, even though {A,B,C} is not "the same size as" {A,B,C,D}.
On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
> For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other. Are you suggesting these be treated as "the same size as" one another?
No. The paradox is that intuitively
1. If there is bijection between F and G, they are the same size.
2. If F is a proper subset of G, F and G are not the same size.
For finite numbers, these principles are compatible, but for infinities, it can happen that they contradict each other.
No. The paradox is that intuitively
1. If there is bijection between F and G, they are the same size.
2. If F is a proper subset of G, F and G are not the same size.
For finite numbers, these principles are compatible, but for infinities, it can happen that they contradict each other.
Ok. So are you suggesting a notion of "size" such that A is a smaller "size" than B if and only if A is extensionally equal to a proper subset of B? This would lead to a partial order on all sets. As a result, the perfect squares would smaller than the naturals, but also it would make many sets incomparable in size, including the natural numbers and the set {A}.
Or if this is not what you are suggesting, what are you suggesting?
Or if this is not what you are suggesting, what are you suggesting?
I find Galileo's conclusion plausible that neither principle holds for infinite sets.
> For instance, the two sets {1,2,3,4} and {A,B,C} are such that none is equal to a proper subset of the other.
The existence of an injective function is what makes subset {A,B,C} a "proper subset" [sic] of {1,2,3,4}, in context of comparing their size.
The terminology could be chosen better, but I think the intended meaning is clear.
The existence of an injective function is what makes subset {A,B,C} a "proper subset" [sic] of {1,2,3,4}, in context of comparing their size.
The terminology could be chosen better, but I think the intended meaning is clear.
This is exactly what I wrote about in my second paragraph, isn't it? The intended meaning is not clear, because this definition again makes the set of naturals the same size as the set of squares.
> On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
> On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
Ah, I see. I have't read your comment properly, I guess.
That's a fair point, it really seems that comparing sets in general only makes sense in terms of bijections, which makes infinite sets as comparable as finite sets.
That's a fair point, it really seems that comparing sets in general only makes sense in terms of bijections, which makes infinite sets as comparable as finite sets.
Being able to understand the way in which mathematical usage of phrases like “the same size as” is different than intuitive uses of the same phrase is becoming increasingly important. Only six months ago I was seeing a dozen YouTube videos a day claiming g “Physics proved that the universe is not real!” because some physicist decided to overload the “real” operator in the English language.
> That there are infinities of various sizes follows if you accept Hume's Principle, which says "the number of things with the property F equal the number of things with the property G if and only if there is a one-to-one correspondence between those that are F and those that are G."
I don't think that accepting(?) principles(?) is the right way to think about it.
This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.
I don't think that accepting(?) principles(?) is the right way to think about it.
This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.
Matrices and rings are technical terms without preexisting intuitions, but "the same size" seems to be an intuitive concept, like "natural number" or "circle". So presumably any definition should be compatible with our existing concepts. Although Galileo argues against size having an intuitive sense for infinities.
> So presumably any definition should be compatible with our existing concepts.
Yes, this is the wrong way (IMO) to think about it. The right way is to notice that it is a definition, and to think about it like every other definition. It has the name "same size", because it has some properties common with "same size" of finite cardinalities, but not all properties common.
And this is the proper way to think about every other definitions and objects as well, even if they are technical terms, or borrowed from common English. (BTW I believe that rings are called rings, because of some similarities with rings.)
Yes, this is the wrong way (IMO) to think about it. The right way is to notice that it is a definition, and to think about it like every other definition. It has the name "same size", because it has some properties common with "same size" of finite cardinalities, but not all properties common.
And this is the proper way to think about every other definitions and objects as well, even if they are technical terms, or borrowed from common English. (BTW I believe that rings are called rings, because of some similarities with rings.)
It always made more sense to me to define things as "one to one AND that one set's of elements is not absolutely contained in the other set." This would make the integers bigger than the even integers because 2Z in Z but would mean that the evens and the odds are the same size, since they are disjoint sets. Though both are obviously categorically countable.
But I'm not a (set) theorist and I'm sure this has been explored before. Does anyone have a link and/or concise explanation? (papers are fine) Would this definition result in similarity weird conclusions? (Infinities are weird)
But I'm not a (set) theorist and I'm sure this has been explored before. Does anyone have a link and/or concise explanation? (papers are fine) Would this definition result in similarity weird conclusions? (Infinities are weird)
Consider the following sets: the primes (let's call it P), the odd numbers (let's call that O), the odd numbers except for 3 (and let's call this O3).
Using your definition O would be equal in size to P, P would be equal in size to O3, but O3 would be smaller in size than O.
Using your definition O would be equal in size to P, P would be equal in size to O3, but O3 would be smaller in size than O.
Ah thanks! That's an obvious counter example!
But as a followup, are there definitions that rely the rate at which sets approach infinity? P clearly "fills" its set more slowly than the even integers whereas the evens and odds "fill" the set in similar times. This would obviously mean 2Z, 3Z, and 3Z - {3} would be the same size (unless we invoke the disjoint requirement), but these could be used categorically like Big O notation (which can be refined).
Would this an even useful metric? Are set theorists even interested in differentiating these infinities?
Edit: I also gave a bit more motivation in the reply to your sibling comment. Short is that if we do "Z - 2Z" we can get the two sets of positive odds and negative odds without {0}. It seems reasonable that since we can do this decomposition and match in the normal manner that since there is a remainder that one would be larger than another but this also does not clear up the example you provided with primes.
But as a followup, are there definitions that rely the rate at which sets approach infinity? P clearly "fills" its set more slowly than the even integers whereas the evens and odds "fill" the set in similar times. This would obviously mean 2Z, 3Z, and 3Z - {3} would be the same size (unless we invoke the disjoint requirement), but these could be used categorically like Big O notation (which can be refined).
Would this an even useful metric? Are set theorists even interested in differentiating these infinities?
Edit: I also gave a bit more motivation in the reply to your sibling comment. Short is that if we do "Z - 2Z" we can get the two sets of positive odds and negative odds without {0}. It seems reasonable that since we can do this decomposition and match in the normal manner that since there is a remainder that one would be larger than another but this also does not clear up the example you provided with primes.
I always thought that a "growth rate" definition of sizes of infinity makes more sense than Hume's principle. Then the odd numbers approach infinity half as fast as the natural numbers. But that only works for ordered quantities.
I mean this doesn't actually solve the issue: 2Z and 3Z are the same size under this definition.
> 2Z and 3Z are the same size under this definition
That's quite the intention actually. The motivation here is that there is clearly a 1-to-1 and onto (bijective) mapping between these sets. While we can set a clear map even from Z to 2Z (T: x -> 2x) there are other maps that work perfectly as well. For example if we take the ideal/subset of Z such that we use every other number (i.e. the evens) then this also corresponds to 2Z but we still have an infinite number of numbers left over.
Let's be more clear
Z = {Z+} + {Z-} + {0} = {2Z+} + {(2n+1)Z+} + {2Z-} + {(2n+1)Z-} + {0}
2Z = {2Z+} + {2Z-} + {0}
Then if we do Z - 2Z we get {(2n+1)Z+} + {(2n+1)Z-} (or the odds without 0). In other words, we have infinity plus infinity but one of the infinities is fully contained in the other infinity. It does seem reasonable to think that these may not be the same size, just as we would say that the uncountable infinities is larger than the countable infinities. In fact, the logic is quite similar here.
Note though, that the sibling comment (to you) gave a counter example as to where there might still be issues. Because by this setup we'd still have the number of primes equal to the size of even integers. So I asked about rates of going to infinity.
That's quite the intention actually. The motivation here is that there is clearly a 1-to-1 and onto (bijective) mapping between these sets. While we can set a clear map even from Z to 2Z (T: x -> 2x) there are other maps that work perfectly as well. For example if we take the ideal/subset of Z such that we use every other number (i.e. the evens) then this also corresponds to 2Z but we still have an infinite number of numbers left over.
Let's be more clear
Z = {Z+} + {Z-} + {0} = {2Z+} + {(2n+1)Z+} + {2Z-} + {(2n+1)Z-} + {0}
2Z = {2Z+} + {2Z-} + {0}
Then if we do Z - 2Z we get {(2n+1)Z+} + {(2n+1)Z-} (or the odds without 0). In other words, we have infinity plus infinity but one of the infinities is fully contained in the other infinity. It does seem reasonable to think that these may not be the same size, just as we would say that the uncountable infinities is larger than the countable infinities. In fact, the logic is quite similar here.
Note though, that the sibling comment (to you) gave a counter example as to where there might still be issues. Because by this setup we'd still have the number of primes equal to the size of even integers. So I asked about rates of going to infinity.
It seems like Hume's Principle is only a matter of semantics, not of mathematics. The concept of one-to-one correspondence is useful even if we don't refer to it as size. All existing proofs would be equally valid even if we didn't accept this definition of 'size', since it would still be true that there is or isn't a correspondence between two sets, even if we refer to it in a different way.
Well, set theory contains axioms specifically to introduce sets of such "size". These axioms aren't just definitions.
[deleted]
Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.
It's not just a renaming. The following is true: The square numbers are a proper subset of the natural numbers. If you switch "square numbers" and "natural numbers" it is false. If two terms can't be exchanged salva veritate, they are not equivalent.
Your failure to do the actual renaming doesn't make the renaming a failure. No one has claimed that the set of squares is extensionally equal to the naturals. The existence of a bijection has nothing to do with extensional equality of the given sets. It's not even a particularly strong equivalence among those in everyday use. I guess the category theorists have a cute name for this (morphism? Who knows...), but it is to set cardinality as homomorphism are to groups.
But in fact even if the claim had been about extensional equality, HoTT shows how this can be carried out correctly: the equivalence between two types (which is supposed to be actual Leibniz equality, not merely equinumerosity as in the example) must be used, as if a function, to transport actual terms between the two types. Using this mechanism, the subtype of square naturals is in fact extensionally equal to the naturals. For example, the term `f 4` where `f` is the transport along `squares = N` is in fact the sum of the multiplicative identity with itself. This is what I meant by actually doing the renaming.
But in fact even if the claim had been about extensional equality, HoTT shows how this can be carried out correctly: the equivalence between two types (which is supposed to be actual Leibniz equality, not merely equinumerosity as in the example) must be used, as if a function, to transport actual terms between the two types. Using this mechanism, the subtype of square naturals is in fact extensionally equal to the naturals. For example, the term `f 4` where `f` is the transport along `squares = N` is in fact the sum of the multiplicative identity with itself. This is what I meant by actually doing the renaming.
He said "just" a renaming, which suggests just the names change while the meaning stays the same, which isn't the case. Maybe he meant it in some different "HoTT" sense, but he clearly said
> Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.
which would only be the case for renaming salva veritate -- or by begging the question in favor of one-to-one correspondence being sufficient for something being the "same size" and against proper subsethood being sufficient for something being not the same size. But that's exactly the question when arguing for or against Hume's Principle, not something which can be assumed.
> Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.
which would only be the case for renaming salva veritate -- or by begging the question in favor of one-to-one correspondence being sufficient for something being the "same size" and against proper subsethood being sufficient for something being not the same size. But that's exactly the question when arguing for or against Hume's Principle, not something which can be assumed.
> He said "just" a renaming, which suggests just the names change while the meaning stays the same, which isn't the case.
Huh? That's exactly what's happening.
If you rename 1, 2, and 3 to one, two, and three, the names have changed and the meanings haven't. As you note, this is what "renaming" means. It used to be true that 1 + 2 = 3, but now that's gibberish and one + two = three instead.
Nothing about that changes if you instead rename 1, 2, and 3 to 88, 89, and 90. It will still be true that 88 + 88 = 89. You don't get to reinterpret what the name means after you assign it.
Huh? That's exactly what's happening.
If you rename 1, 2, and 3 to one, two, and three, the names have changed and the meanings haven't. As you note, this is what "renaming" means. It used to be true that 1 + 2 = 3, but now that's gibberish and one + two = three instead.
Nothing about that changes if you instead rename 1, 2, and 3 to 88, 89, and 90. It will still be true that 88 + 88 = 89. You don't get to reinterpret what the name means after you assign it.
Well, then the squares are still a proper subset of the natural numbers, while still being in a one-to-one correspondence, so Galileo's Paradox remains. Then renaming didn't change anything.
The problem is that infinity is not a number. Infinity plus one is equal to infinity. This is not a trait that any number has. There is no number where you can add one and get the same number. The subset of an infinite set can itself be infinite. If you can map bi-directionality (which you can for square numbers and naturals) between an infinite set and its' infinite subset, then they are equivalent in size. Your problem is that you expect infinity (well, one type of infinity, there are ordered infinities [edit: when I said infinities, I meant infinite numbers, which the common infinite is not an infinite number, it's infinity], but that's outside our scope here) to be ordered, which it is not. Numbers are ordered, but infinity is not a number and is not ordered in the numbers.
> The problem is that infinity is not a number. Infinity plus one is equal to infinity. This is not a trait that any number has. There is no number where you can add one and get the same number.
This is all false. What you describe is a violation of the Archimedean principle. "Numbers" are a wider concept than the Archimedean principle.
This is all false. What you describe is a violation of the Archimedean principle. "Numbers" are a wider concept than the Archimedean principle.
We are only taking sizes here not “is it a group” etc.
So let’s play that old 21s drinking game, but infinitely instead of 1 to 21, and rename 1 to 1, 2 to 4, 3 to 9 and so on, up to x for any x. Same set, different lingo.
That you can’t map back 5 is irrelevant although kind of leaves a bad taste.
So let’s play that old 21s drinking game, but infinitely instead of 1 to 21, and rename 1 to 1, 2 to 4, 3 to 9 and so on, up to x for any x. Same set, different lingo.
That you can’t map back 5 is irrelevant although kind of leaves a bad taste.
It’s still just a renaming. In fact you might even perform the renaming and thus form the bijection without even realizing it, if you talked about “the first square number,” “the second square number,” etc.
It is an injection, but not a surjection.
You need neither though. For example:
y = x ^ 2 when even, (x+1) ^ 2 otherwise
You need neither though. For example:
y = x ^ 2 when even, (x+1) ^ 2 otherwise
> It is an injection, but not a surjection.
It's a bijection. (And therefore obviously also a surjection.) "One-to-one correspondence" is a correct, but incomplete, description.
It's a bijection. (And therefore obviously also a surjection.) "One-to-one correspondence" is a correct, but incomplete, description.
∄ x ∈ ℕ: x² = 5
Unless you consider the domain of f the "renamed" range, in which case yes tautologically it is bijective.
Unless you consider the domain of f the "renamed" range, in which case yes tautologically it is bijective.
You're talking past one another. The other poster is discussing a correspondence between N and S, where S is the set of squares. So the function being discussed is f: N -> S, f(n) = n^2, which is obviously bijective.
You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance. Any surjective function can be made non-surjective by considering a larger range.
You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance. Any surjective function can be made non-surjective by considering a larger range.
> You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance.
It's worse than just irrelevant. The claim is that we have two sets, ℕ and S, that are the same size. The argument that they are the same size is the observation that we've demonstrated a bijection between them.
No one ever mentioned a function from ℕ to ℕ, because that would tell you nothing about S. It would be like saying "in order to show that 5 is odd, observe that 2 and 2 are both even". The idea is gibberish.
It's worse than just irrelevant. The claim is that we have two sets, ℕ and S, that are the same size. The argument that they are the same size is the observation that we've demonstrated a bijection between them.
No one ever mentioned a function from ℕ to ℕ, because that would tell you nothing about S. It would be like saying "in order to show that 5 is odd, observe that 2 and 2 are both even". The idea is gibberish.
But Galileo's objection would seem to imply that there should be more infinities, not fewer.
A definition like "F and G are the same size if there is a one-to-one correspondence, except when F is a proper subset of G, then F is smaller" wouldn't work, because that isn't an equivalence relation. While "is the same size" seems in fact to be such an equivalence relation. For example, there might be a set H, such that H would be "the same size as" F and as G (due to one-to-one correspondence), but F would be smaller than G (due to proper subsethood). This would violate transitivity.
I'm not saying there's a definition that works down that path (I don't know); I'm saying that "we only have multiple infinities because of this definition, which people objected to because it didn't give us enough infinities" seems a little muddled.
The argument seems to be rather that intuitions for size and subsethood and bijection aren't compatible anymore, which is a reductio argument against assuming that size comparisons make any sense for infinities at all.
I think the mystery is not that some infinities can be larger than others, but that there are infinite sets of equal ‘size’ that conflict with intuition.
Some examples that ‘prove’ some infinities are larger than others to laymen:
- there are twice as many integers as odd integers
- there are more points on a plane then on a line
- there are more points on a line than on a circle
- there are more points on a plane then on a semiplane
- there are more rationals than integers
- there are more reals than rationals
It’s only in the intermediate state of a mathematician’s education, where they have just accepted that, for infinite sets, ‘more’ isn’t the best way to determine size equivalence that it becomes a surprise that for the last one, “the size of the set of reals is larger than that of the rationals” is true, and can be proven to be.
Some examples that ‘prove’ some infinities are larger than others to laymen:
- there are twice as many integers as odd integers
- there are more points on a plane then on a line
- there are more points on a line than on a circle
- there are more points on a plane then on a semiplane
- there are more rationals than integers
- there are more reals than rationals
It’s only in the intermediate state of a mathematician’s education, where they have just accepted that, for infinite sets, ‘more’ isn’t the best way to determine size equivalence that it becomes a surprise that for the last one, “the size of the set of reals is larger than that of the rationals” is true, and can be proven to be.
Good points, a large chunk of math is different formalizations of the notion of size, for example (in order of increasing absurdity):
https://en.wikipedia.org/wiki/Cardinality
https://en.wikipedia.org/wiki/Measure_(mathematics)
https://en.wikipedia.org/wiki/Ultrafilter_(set_theory)
https://en.wikipedia.org/wiki/Euler_characteristic
https://golem.ph.utexas.edu/category/2008/02/metric_spaces.h...
https://golem.ph.utexas.edu/category/2006/10/euler_character...
(and of course there are certainly many that I'm missing)
For more fun, see these slides from John Baez: https://math.ucr.edu/home/baez/counting/counting.pdf
https://en.wikipedia.org/wiki/Cardinality
https://en.wikipedia.org/wiki/Measure_(mathematics)
https://en.wikipedia.org/wiki/Ultrafilter_(set_theory)
https://en.wikipedia.org/wiki/Euler_characteristic
https://golem.ph.utexas.edu/category/2008/02/metric_spaces.h...
https://golem.ph.utexas.edu/category/2006/10/euler_character...
(and of course there are certainly many that I'm missing)
For more fun, see these slides from John Baez: https://math.ucr.edu/home/baez/counting/counting.pdf
It's been a long time since my number theory class, but aren't there the same number of integers and odd integers?
Take the set of odd integers {... -3, -1, 1, 3, 5, ...}
For each item, subtract one and divide the result by 2. Now you have the set of all integers without any insertions or deletions: {... -2, -1, 0, 1, 2, ...}
Therefore the set of odd integers can be mapped 1:1 onto the set of all integers so they are of equal length.
Take the set of odd integers {... -3, -1, 1, 3, 5, ...}
For each item, subtract one and divide the result by 2. Now you have the set of all integers without any insertions or deletions: {... -2, -1, 0, 1, 2, ...}
Therefore the set of odd integers can be mapped 1:1 onto the set of all integers so they are of equal length.
That's why 'Prove' is in quotation marks. Not all of GP's statements are true, though it would've been helpful if they'd added (true) and (false) tags next to them.
[deleted]
They have the same cardinality.
Your proof is correct.
Isn't that more like first-year material in mathematics and in more theoretically oriented CS programs? Once you start talking about injections, surjections, and bijections, you may as well prove some basic results about the sizes of sets of numbers.
There are basically no prerequisites to get a grasp of these ideas. I remember being introduced to this in one of Raymond Smullyan's book when I was a kid.
> there are twice as many integers as odd integers
> there are more rationals than integers
Both of these are incorrect you can create a 1-1 mapping between all of these sets so they are the same "size". Things get unintuitive when you're dealing with infinites things that feel like they should be larger aren't when you examine them rigorously.
For integers to odd integers the mapping is easy for each natural number n map n -> 2n+1. Mapping integers to rational numbers is more difficult to write into an equation but if you lay them out in a a grid defined by numerators and denominators x/y you can snake along this grid to eventually map every rational number to a corresponding natural number (ie positive integers which has the same cardinality as integers).
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
> there are more points on a plane then on a line
Going further R (points on a line) to R^2 (points on a plane) is also the same cardinality. The proofs are over my head as a 10 years past math minor but they're out there. Including this one that goes from R^3 to R.
https://math.stackexchange.com/posts/183383/revisions
> there are more rationals than integers
Both of these are incorrect you can create a 1-1 mapping between all of these sets so they are the same "size". Things get unintuitive when you're dealing with infinites things that feel like they should be larger aren't when you examine them rigorously.
For integers to odd integers the mapping is easy for each natural number n map n -> 2n+1. Mapping integers to rational numbers is more difficult to write into an equation but if you lay them out in a a grid defined by numerators and denominators x/y you can snake along this grid to eventually map every rational number to a corresponding natural number (ie positive integers which has the same cardinality as integers).
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
> there are more points on a plane then on a line
Going further R (points on a line) to R^2 (points on a plane) is also the same cardinality. The proofs are over my head as a 10 years past math minor but they're out there. Including this one that goes from R^3 to R.
https://math.stackexchange.com/posts/183383/revisions
This is literally the point of the comment.
To a layperson not familiar with this approach to measuring infinities, all of the examples are “correct”.
To a mathematician that hasn’t heard of uncountability, all are “incorrect”. (And learning the last is actually “correct” is surprising).
To a layperson not familiar with this approach to measuring infinities, all of the examples are “correct”.
To a mathematician that hasn’t heard of uncountability, all are “incorrect”. (And learning the last is actually “correct” is surprising).
[deleted]
That’s not what GP says though. They say their last statement is correct when it’s not.
There are only two types of infinities: countable and uncountable. Both reals and rationals are not countable
There are only two types of infinities: countable and uncountable. Both reals and rationals are not countable
> There are only two types of infinities: countable and uncountable.
That's not true, either. For any infinite set S, the powerset 2^S is also infinite, but there is no injection from 2^S to S. Therefore, the cardinality of 2^S is bigger than the cardinality of S. You can iterate this and get a tower of arbitrarily many distinct types of infinity.
"Countable infinity" describes the cardinality of the set of natural numbers. "Uncountable infinity" describes any infinite cardinality that is not that of the natural numbers -- it just means "not countable".
> Both reals and rationals are not countable
The rationals are countable, by a diagonal construction. Take an Excel spreadsheet with rows labeled 1, 2, and so on; and columns labeled 1, 2, and so on. In every cell, write the cell's row over the cell's column as a fraction. By construction, every rational number n/m will exist in this spreadsheet, at row n and column m.
Now walk the spreadsheet in diagonals: first the first diagonal (just 1/1), then the second diagonal (1/2, 2/1), then the third (1/3, 2/2, 3/1), and so on. This yields a sequence (i.e. a mapping from naturals to ratios) where every ratio is guaranteed to appear at some finite index. But because every ratio appears in this sequence, we can go backwards, taking a rational number in reduced form and finding its index in the sequence, giving us an inverse map from rationals to naturals.
Every rational number therefore gets its own unique natural. Since this is an injection, the set of rationals must be no bigger than the set of naturals. (In fact, it's the same cardinality, but my argument is a little too imprecise to show that the rationals are no smaller than the set of naturals -- two naturals in this construction may land on the same rational number. We would fix this by just skipping ratios not in reduced form.)
That's not true, either. For any infinite set S, the powerset 2^S is also infinite, but there is no injection from 2^S to S. Therefore, the cardinality of 2^S is bigger than the cardinality of S. You can iterate this and get a tower of arbitrarily many distinct types of infinity.
"Countable infinity" describes the cardinality of the set of natural numbers. "Uncountable infinity" describes any infinite cardinality that is not that of the natural numbers -- it just means "not countable".
> Both reals and rationals are not countable
The rationals are countable, by a diagonal construction. Take an Excel spreadsheet with rows labeled 1, 2, and so on; and columns labeled 1, 2, and so on. In every cell, write the cell's row over the cell's column as a fraction. By construction, every rational number n/m will exist in this spreadsheet, at row n and column m.
Now walk the spreadsheet in diagonals: first the first diagonal (just 1/1), then the second diagonal (1/2, 2/1), then the third (1/3, 2/2, 3/1), and so on. This yields a sequence (i.e. a mapping from naturals to ratios) where every ratio is guaranteed to appear at some finite index. But because every ratio appears in this sequence, we can go backwards, taking a rational number in reduced form and finding its index in the sequence, giving us an inverse map from rationals to naturals.
Every rational number therefore gets its own unique natural. Since this is an injection, the set of rationals must be no bigger than the set of naturals. (In fact, it's the same cardinality, but my argument is a little too imprecise to show that the rationals are no smaller than the set of naturals -- two naturals in this construction may land on the same rational number. We would fix this by just skipping ratios not in reduced form.)
Thanks. A suspicion lingered as soon as I wrote that comment. I guess I was going off of some YouTube video. Now I see rationals are countable.
But what explains the power set being larger though? It seems intuitive but I don’t want to trust it for obv reasons. Is diagonalisation impossible?
But what explains the power set being larger though? It seems intuitive but I don’t want to trust it for obv reasons. Is diagonalisation impossible?
That's a good question -- this result is arguably the one that made Georg Cantor a legend. (It's called Cantor's theorem, after all!) I had to refresh myself on the proof, but it boils down to a less obvious kind of "diagonalization" (this time to construct a counterexample).
We can show that S has a strictly smaller cardinality than 2^S by showing that no function from S to 2^S can hit every value in 2^S. That is, there's going to be some element of 2^S that no element of S gets mapped to.
Suppose, as one does, to the contrary: that there is a function, call it F, that hits every element of 2^S. We'll construct a particularly pathological element of 2^S, call it B, the set {s in S | s not in F(s)} of values of S that are not members of the subset F picks out for them. (Remember that 2^S is the set of subsets of S, so it is meaningful to ask whether any s is a member of F(s).) If this smells like Russell's paradox, good -- follow your nose!
Now, since B is a subset of 2^S, and F is presumed to hit every subset, there's going to be some element b such that F(b) = B. We ask the critical question: is b in B? If it is, then b is not in F(b) -- but F(b) is B, contradicting our assumption. If it isn't, then b is in F(b) -- but F(b) is B, contradicting our assumption.
Since we end up at a contradiction no matter which way we resolve "is b in B", and we know this question must be answered one way or the other, we must admit that our supposed function F must not have the property we asked for; it must not hit every element of 2^S. So 2^S really is "bigger" than S, in that no matter how we pair every element of S with an element of 2^S, we run out of elements of the former before we've exhausted the latter.
We can show that S has a strictly smaller cardinality than 2^S by showing that no function from S to 2^S can hit every value in 2^S. That is, there's going to be some element of 2^S that no element of S gets mapped to.
Suppose, as one does, to the contrary: that there is a function, call it F, that hits every element of 2^S. We'll construct a particularly pathological element of 2^S, call it B, the set {s in S | s not in F(s)} of values of S that are not members of the subset F picks out for them. (Remember that 2^S is the set of subsets of S, so it is meaningful to ask whether any s is a member of F(s).) If this smells like Russell's paradox, good -- follow your nose!
Now, since B is a subset of 2^S, and F is presumed to hit every subset, there's going to be some element b such that F(b) = B. We ask the critical question: is b in B? If it is, then b is not in F(b) -- but F(b) is B, contradicting our assumption. If it isn't, then b is in F(b) -- but F(b) is B, contradicting our assumption.
Since we end up at a contradiction no matter which way we resolve "is b in B", and we know this question must be answered one way or the other, we must admit that our supposed function F must not have the property we asked for; it must not hit every element of 2^S. So 2^S really is "bigger" than S, in that no matter how we pair every element of S with an element of 2^S, we run out of elements of the former before we've exhausted the latter.
This basically made my day/week. Thanks a ton!
I guess I should read the book on infinity and aleph numbers linked in the other thread.
It’s both satisfying and unsettling that you kinda reinvent numbers with cardinality of infinities. Like wtf is going on.
I guess I should read the book on infinity and aleph numbers linked in the other thread.
It’s both satisfying and unsettling that you kinda reinvent numbers with cardinality of infinities. Like wtf is going on.
> There are only two types of infinities: countable and uncountable.
There are cardinal transfinite numbers (starting at aleph-null) and ordinal transfinite numbers (starting at omega). There are infinitely many transfinite cardinals, and likewise for the ordinals. There are also other infinite numbers in mathematics, distinct from the transfinite numbers of set theory, such as infinities in the projectively and affinely extended reals, the surreals, etc
Usually, discussions of transfinite numbers assume ZFC set theory (Zermelo–Fraenkel with the axiom of choice). You also have large cardinals which only exist if you add additional axioms to ZFC (large cardinal axioms). There is a hierarchy of larger and larger large cardinals, which corresponds to the ordering of the consistency strength of the large cardinal axioms.
How many cardinals exist, in ZFC? Well, "the set of all cardinals" isn't a set in ZFC – for the same reason that ZFC lacks a universal set (that's how it avoids Russell's paradox) – so we cannot speak of which cardinal is its size. Of course, if we adopt a suitable extension of ZFC (such as proper classes), then maybe we can, but then "the cardinal measuring the number of cardinals in ZFC" wouldn't be the same type of mathematical object (category?) as the usual cardinals are.
And then I assume if you replace ZFC with some alternative set theory, such as NBG or NFU, at some point you'll get different cardinals and ordinals arising. But that's a question that has always intrigued me but I've never known the answer to. I'm sure the answer is in some graduate maths text somewhere which is going to go completely over my head.
There are cardinal transfinite numbers (starting at aleph-null) and ordinal transfinite numbers (starting at omega). There are infinitely many transfinite cardinals, and likewise for the ordinals. There are also other infinite numbers in mathematics, distinct from the transfinite numbers of set theory, such as infinities in the projectively and affinely extended reals, the surreals, etc
Usually, discussions of transfinite numbers assume ZFC set theory (Zermelo–Fraenkel with the axiom of choice). You also have large cardinals which only exist if you add additional axioms to ZFC (large cardinal axioms). There is a hierarchy of larger and larger large cardinals, which corresponds to the ordering of the consistency strength of the large cardinal axioms.
How many cardinals exist, in ZFC? Well, "the set of all cardinals" isn't a set in ZFC – for the same reason that ZFC lacks a universal set (that's how it avoids Russell's paradox) – so we cannot speak of which cardinal is its size. Of course, if we adopt a suitable extension of ZFC (such as proper classes), then maybe we can, but then "the cardinal measuring the number of cardinals in ZFC" wouldn't be the same type of mathematical object (category?) as the usual cardinals are.
And then I assume if you replace ZFC with some alternative set theory, such as NBG or NFU, at some point you'll get different cardinals and ordinals arising. But that's a question that has always intrigued me but I've never known the answer to. I'm sure the answer is in some graduate maths text somewhere which is going to go completely over my head.
We shall wait for the day when a highly competent chatbot can explain this to us peasants
Rationals are countable. It's actually pretty neat if hard to express as a function, but that's not required.
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
[deleted]
There are more than two kinds of infinities. Consider the set of all subsets of the real numbers.
Also the rationals are countable by diagonalization.
Also the rationals are countable by diagonalization.
rationals are countable
> Both of these are incorrect you can create a 1-1 mapping between all of these sets so they are the same "size".
They are incorrect if you define "the same size" as the existence of a one-to-one mapping. But if you think that a proper subset is never the same size as the original set, then you won't accept that definition.
They are incorrect if you define "the same size" as the existence of a one-to-one mapping. But if you think that a proper subset is never the same size as the original set, then you won't accept that definition.
That's only useful in comparing subsets though and we need a way to compare the size of any possible pair or group of infinite sets, given that the bijection method makes way more sense. Even though it's slightly unintuitive to laymen how can one thing be larger than another if for every member of one group I can match them with a member of the other group, provably for all the infinite members of either group?
I get there's a conflict with intuition there but infinities an inherently unintuitive.
I get there's a conflict with intuition there but infinities an inherently unintuitive.
It's more an argument not to assume there are infinities of different sizes. That would also get rid of most mathematical paradoxes related to infinity.
> Going further R (points on a line) to R^2 (points on a plane) is also the same cardinality. The proofs are over my head but they're out there.
It's just a matter of finding a suitable set of functions. For example, you can try proving |R^2| = |(0, 1) x (0, 1)| = |(0, 1)| = |R| where R stands for reals.The middle equality can be proven using Schröder–Bernstein theorem.
It's just a matter of finding a suitable set of functions. For example, you can try proving |R^2| = |(0, 1) x (0, 1)| = |(0, 1)| = |R| where R stands for reals.The middle equality can be proven using Schröder–Bernstein theorem.
I follow the line of the proof but finding those actual steps is where being out of the pure math game for 10 years catches up to me. I went into college on a pure math major but transferred to a CS degree. Only needed about 2 classes extra at the end but was tired of school and a simple BS in mathematics wouldn't get me too much in a generic CS career so I just stopped.
All of them are incorrect except for the last one.
[deleted]
You need to consider the term “bijection” and what it means in practice. If I create a bijection of integers to integers f(x)=2x you can see that each member of the right side had exactly one member on the right, and vice versa, despite the left side containing some elements not on the right. There is no such bijection between ints and reals (by cantors theorem), but there is clearly a surjection of reals to ints (round down), so reals are of a larger infinite size.
I think a layman could easily understand this personally, without fancy math terms like bijection or surjection, the main exception being Cantors Theorem which fortunately has a plethora of nice visual proofs.
Anyway, the article is not really even about that but about potentially modifying ZFC to accommodate a particular outcome of the CH. I am quite interested in mathematics but to me this is a pointless philosophical argument because there don’t seem to be any useful or empirically verifiable results that depend on CH. Discussing CH to me seems to be more of a way for set theorists to troll each other and trigger cranks.
I think a layman could easily understand this personally, without fancy math terms like bijection or surjection, the main exception being Cantors Theorem which fortunately has a plethora of nice visual proofs.
Anyway, the article is not really even about that but about potentially modifying ZFC to accommodate a particular outcome of the CH. I am quite interested in mathematics but to me this is a pointless philosophical argument because there don’t seem to be any useful or empirically verifiable results that depend on CH. Discussing CH to me seems to be more of a way for set theorists to troll each other and trigger cranks.
Some of those infinities are the same, others are not.
There's a one to one mapping between the integers and the cartesian product of the integers (I^I == I), but (I believe) that's not true for the reals (someone correct me if I'm wrong about that).
However, you can take some subset of R^n and stretch it to infinity across all dimensions, giving you back R^n.
So:
There are the same number of integers as odd integers,
There are more points on a continuous plane than on a continuous line.
The number of points on a line is the same as the number of points on the edge of a circle.
The number of points in a plane is the same as the number of points in a semiplane.
There are the same number of rationals as integers.
There are more reals than integers.
There's a one to one mapping between the integers and the cartesian product of the integers (I^I == I), but (I believe) that's not true for the reals (someone correct me if I'm wrong about that).
However, you can take some subset of R^n and stretch it to infinity across all dimensions, giving you back R^n.
So:
There are the same number of integers as odd integers,
There are more points on a continuous plane than on a continuous line.
The number of points on a line is the same as the number of points on the edge of a circle.
The number of points in a plane is the same as the number of points in a semiplane.
There are the same number of rationals as integers.
There are more reals than integers.
I think it was clear from there their comment that they not only understood that, but picked those examples specifically because of that understanding. Your comment would be fine if it were framed as clarifying that for those who didn't understand, but as it is it just seems to out you as them.
He may have stated the things that are not true to illustrate that they don't seem that different from those that are, but could have been clearer in delineating the two sets.
> (I believe) that's not true for the reals (someone correct me if I'm wrong about that).
It is also true for the reals. R^2 can be trivially mapped to R.
Here's one mapping from R to R^2:
Let b_{n} b_{n-1} .. b_0 . b_{-1} b_{-2} ...
Be the binary representation of the real 'x'. For example, if x = 2.5, then:
b_1 = 1
b_0 = 0
b_{-1} = 1
Have x map to the following value in R^2 (y, z) where
y = b_{n} b_{n-2} ... b_{0} . b_{-2} b_{-4} ..
z = b_{n-1} b_{n-3} .. b_{1} . b_{-1} b_{-3} ..
So 2.5 -> (0, 1.5)
1 -> (1, 0)
1.75 -> (1.5, 0.5)
etc.
It is also true for the reals. R^2 can be trivially mapped to R.
Here's one mapping from R to R^2:
Let b_{n} b_{n-1} .. b_0 . b_{-1} b_{-2} ...
Be the binary representation of the real 'x'. For example, if x = 2.5, then:
b_1 = 1
b_0 = 0
b_{-1} = 1
Have x map to the following value in R^2 (y, z) where
y = b_{n} b_{n-2} ... b_{0} . b_{-2} b_{-4} ..
z = b_{n-1} b_{n-3} .. b_{1} . b_{-1} b_{-3} ..
So 2.5 -> (0, 1.5)
1 -> (1, 0)
1.75 -> (1.5, 0.5)
etc.
> It is also true for the reals. R^2 can be trivially mapped to R.
> Here's one mapping from R to R^2:
That's the easy part. It's very easy to map R to R^2, the other direction not so much.
From my searches, based upon what other people said, the mapping is a surjection and not a bijection.
If that's the case, then either they don't have the same cardinality or I'm confused as to what cardinality actually is.
> Here's one mapping from R to R^2:
That's the easy part. It's very easy to map R to R^2, the other direction not so much.
From my searches, based upon what other people said, the mapping is a surjection and not a bijection.
If that's the case, then either they don't have the same cardinality or I'm confused as to what cardinality actually is.
There is no need to exhibit bijections, if you have an injection X -> Y and an injection Y -> X, then X and Y have the same cardinality. This is the statement of the Cantor-Schroeder-Bernstein theorem.
If you assume the axiom of choice it's enough to have surjections both way.
If you assume the axiom of choice it's enough to have surjections both way.
I get how you can map every value in R -> R^2, but I have yet to see any proof that there's a complete mapping in reverse.
For the most reasonable attempt at flooding a plane with R, I still end up with something where I can trivially define values {r0, r1} that do not map back to R.
For the most reasonable attempt at flooding a plane with R, I still end up with something where I can trivially define values {r0, r1} that do not map back to R.
What are those trivially defined {r0,r1} for the "interleaving digits" map f:(0,1) -> (0,1)^2 defined by taking a real x in (0,1), writing its decimal expansion as
x=0.a1a2a3a4a5a6...
(always pick the nonrepeating decimal expansion in case x has two) and sending it to the pair (y,z) where
y=0.a1a3a5... z=0.a2a4a6...
(Using (0,1) is no issue since we can compose later with bijections (0,1) -> R)
Edit: I'm not sure why I cannot reply to your reply, but {π,π} is not even in (0,1)^2
We can also do a map f:R -> R^2 directly, it's just slightly more annoying to write. Take a real number x, written in decimal expansion as
x=bn...b2b1b0.a0a1a2a3a4...
where again we choose the representation which is not repeating in case x has two. We also choose our first index n so that bn is zero but b(n-1) is not. We now map x to the pair (y,z), where
y=...b5b3b1.a1a3a5...
z=...b4b2b0.a0a2a4...
So that, for example, (π,π) is the image of x=33.114411559922...
x=0.a1a2a3a4a5a6...
(always pick the nonrepeating decimal expansion in case x has two) and sending it to the pair (y,z) where
y=0.a1a3a5... z=0.a2a4a6...
(Using (0,1) is no issue since we can compose later with bijections (0,1) -> R)
Edit: I'm not sure why I cannot reply to your reply, but {π,π} is not even in (0,1)^2
We can also do a map f:R -> R^2 directly, it's just slightly more annoying to write. Take a real number x, written in decimal expansion as
x=bn...b2b1b0.a0a1a2a3a4...
where again we choose the representation which is not repeating in case x has two. We also choose our first index n so that bn is zero but b(n-1) is not. We now map x to the pair (y,z), where
y=...b5b3b1.a1a3a5...
z=...b4b2b0.a0a2a4...
So that, for example, (π,π) is the image of x=33.114411559922...
{π, π} will generally do.
Sorry, didn't even look at the bounds - assumed things went to infinity.
Sorry, didn't even look at the bounds - assumed things went to infinity.
As an example, try using a Hilbert curve to map {π, π} back onto R (and I mean π exactly, not π ± an infinitesimal).
(There are, however, infinitely many mappings for {π, π ± ε} -> R and {π ± ε, π} -> R, such that ε is infinitesimal.)
(There are, however, infinitely many mappings for {π, π ± ε} -> R and {π ± ε, π} -> R, such that ε is infinitesimal.)
Correct...except that there are the same number of points on a line as in a plane.
Aleph_0^2 = Aleph_0
Aleph_1^2 = Aleph_1
Aleph_0^2 = Aleph_0
Aleph_1^2 = Aleph_1
How though (genuine question)?
I can see space filling curves through I^I, but I can't see them covering R^I.
How does a space-filling curve cover a plane without being filled with infinitesimal discontinuities?
I can see space filling curves through I^I, but I can't see them covering R^I.
How does a space-filling curve cover a plane without being filled with infinitesimal discontinuities?
Hilbert curves
Yes, I've got that part - but that only gets me as far as R * I ^ (d - 1), not R ^ d.
(d being the dimensionality of the curve.)
As I think about this there's an unfilled infinitesimal R ^ (d - 1) space orthogonal to every point on the curve.
I don't see how it is that that does not manifest as discontinuities in the filled space.
(d being the dimensionality of the curve.)
As I think about this there's an unfilled infinitesimal R ^ (d - 1) space orthogonal to every point on the curve.
I don't see how it is that that does not manifest as discontinuities in the filled space.
You can get from R^d to I^d (with I the open unit interval) easily by applying x -> (arctan(x) + pi/2)/pi and y -> tan(pi * y - pi/2) to each coordinate. There are also ways to go from R to the closed unit interval. You can then combine this with space-filling curves for I^d.
You can even go from R to I^d.
The problem that I'm having is in getting from R to R^d, which I still don't think is possible - look at the comment where I mention "surjections" and "bijections".
The problem that I'm having is in getting from R to R^d, which I still don't think is possible - look at the comment where I mention "surjections" and "bijections".
By applying the map from I^d to R^d (using the tan-arctan-construction above in each coordinate) after the map from R to R^d, you get a map from R to R^d.
Whether |R|=aleph_1 is independent of ZFC (but of course there are bijections both between R and R^2 and between aleph_1 and aleph_1^2, or between X and X^2 for any infinite set)
https://mathoverflow.net/questions/126069/bijection-from-mat...
https://mathoverflow.net/questions/240249/continuous-map-fro...
https://mathoverflow.net/questions/34232/injective-maps-math...
The second link says that there's a continuous surjection from R -> R^2, but no such bijection.
(Which, after some googling looks in line with what I was imagining.)
If there's no bijection, how can the cardinalities be the same?
https://mathoverflow.net/questions/240249/continuous-map-fro...
https://mathoverflow.net/questions/34232/injective-maps-math...
The second link says that there's a continuous surjection from R -> R^2, but no such bijection.
(Which, after some googling looks in line with what I was imagining.)
If there's no bijection, how can the cardinalities be the same?
Because continuity is not required here. There are non-continuous bijections between R and R^2.
How is continuity not required?
If there are holes in the map does it really cover the whole space?
If there are holes in the map does it really cover the whole space?
I think you have misconceptions about what continuity means and I’m not even sure what you mean with holes.
As a simpler example: The map that multiplies each rational number by -1 and keeps irrational numbers as they are is bijective (it’s its own inverse), however it is nowhere continuous.
As a simpler example: The map that multiplies each rational number by -1 and keeps irrational numbers as they are is bijective (it’s its own inverse), however it is nowhere continuous.
First of all the first link explicitely constructs (in a very strong sense) an explicit bijection R->R^2 so I don't know how why you seem to think otherwise.
It is true that there is no continuous bijection R -> R^2. It is also true that this has nothing to with cardinality, which is only about the existence of bijections (and indeed is defined for arbitrary sets with no topological structure for which continuity makes no sense)
It is true that there is no continuous bijection R -> R^2. It is also true that this has nothing to with cardinality, which is only about the existence of bijections (and indeed is defined for arbitrary sets with no topological structure for which continuity makes no sense)
I don't think that it's actually formulating a bijection across the reals - the generator function looks to me to be generating the complete set of rationals.
> Represent each real number x∈[0,1) as a sequence of DIGITS, where each DIGIT is either in {0,…,8} or is of the form 10∗(10k−1)+i with k≥1 and i∈{0,…,8} (i.e., in {90,…,98;990,…,998;9990,…,9998;…}.
He's iterating to infinity, that sure as shit sounds countable to me.
Anyway, the conclusion that I've come to is that you can map R onto a subset of R^n such that for all values {r[1] ... r[n]} in R^n there is a value in the R -> R^n mapping within all finite bounds.
So as long as you stay away from infinitesimals (not all of them), the domains are equivalent.
https://en.wikipedia.org/wiki/Infinitesimal
> In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero.
But as far as I can tell, the reverse mapping has an R^(n - 1) orthogonal that is completely unaccounted for, within those finite bounds.
(And breaking infinitesimals might cause some trouble for calculus.)
> Represent each real number x∈[0,1) as a sequence of DIGITS, where each DIGIT is either in {0,…,8} or is of the form 10∗(10k−1)+i with k≥1 and i∈{0,…,8} (i.e., in {90,…,98;990,…,998;9990,…,9998;…}.
He's iterating to infinity, that sure as shit sounds countable to me.
Anyway, the conclusion that I've come to is that you can map R onto a subset of R^n such that for all values {r[1] ... r[n]} in R^n there is a value in the R -> R^n mapping within all finite bounds.
So as long as you stay away from infinitesimals (not all of them), the domains are equivalent.
https://en.wikipedia.org/wiki/Infinitesimal
> In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero.
But as far as I can tell, the reverse mapping has an R^(n - 1) orthogonal that is completely unaccounted for, within those finite bounds.
(And breaking infinitesimals might cause some trouble for calculus.)
He's associating to each x in [0,1) an infinite sequence of natural numbers (just like decimal representations do), and there's uncountably many such sequences
But he's defining the numbers with a property that makes them countably infinite?
prefix = '0.';
queue = new Queue(prefix);
for(;;){
s = queue.poll();
for(c:['0'...'9']){
queue.add(s + c);
}
}
The part that seems problematic is "each real number" the reals exist across bounds, I'm not sure there can be an "each".
I think his iterator is generating infinitesimals of rational and not continuous nature.
I think his iterator is generating infinitesimals of rational and not continuous nature.
I may have misread that one, but I still think the reverse mapping only gets as far as within arbitrary bounds.
Half your examples are wrong, but maybe it is your point. Although it wasn't clear to me the first time I read your comment.
- The cardinality of the odd and even integers is the same.
- It is true there are more points on a plane then on a line (Cantor's theorem.)
- The circle is the compactified real line, i.e. it can be represented as the real numbers with one additional point (the point at infinity). In terms of cardinality they are the same since they just differ by one point which does not change the cardinality.
- There are not more points on a plane than a half-plane, you can find a bijective mapping between them easily.
- There are more rationals than integers: not true, they are both countable sets of the same cardinality.
- There are more reals than rationals, this is true (again Cantor.)
- The cardinality of the odd and even integers is the same.
- It is true there are more points on a plane then on a line (Cantor's theorem.)
- The circle is the compactified real line, i.e. it can be represented as the real numbers with one additional point (the point at infinity). In terms of cardinality they are the same since they just differ by one point which does not change the cardinality.
- There are not more points on a plane than a half-plane, you can find a bijective mapping between them easily.
- There are more rationals than integers: not true, they are both countable sets of the same cardinality.
- There are more reals than rationals, this is true (again Cantor.)
Parent is making the same point you are. It’s a surprise to the intermediate mathematician when the last bullet point turns out to be true.
[deleted]
[deleted]
I've found it easier to reason about when I think of it as "how quickly does the set of number grow as you add more to it". It becomes particularly apparent when you think about it on a finite scale.
0 to 100
* 100 integers
* 50 odd numbers, 50 even numbers
* infinite floats (unless you only represent part of the float)
0 to 100
* 100 integers
* 50 odd numbers, 50 even numbers
* infinite floats (unless you only represent part of the float)
Standup Maths recently tackled, "Is an infinite stack of ￡1 notes worth more than an infinite stack of ￡100 notes?" The answer is they are both worth ￡∞.
[deleted]
Infinite is un-enumerable, but you can carve it up in more or less ways.
So infinity-1 is smaller than infinity?
Not in terms of cardinality, at least. Consider the set of natural numbers {0, 1, 2, ...}. This set is clearly of infinite size. If we remove 0, then we have a set {1, 2, ...} with, in principle, one less element than we started with -- yet it is also clearly infinite.
However, these sets have exactly the same number of elements (i.e. "infinity-1 is the same size as infinity") -- I can pair 0 with 1, 1 with 2, 2 with 3, and so on, so that every number in the first set is uniquely paired with a number in the second set, and vice versa.
Arithmetically, I can write `f(x) = x + 1` to go from the first set to the second set, and `g(x) = x - 1` to go from the second set back to the first set, and "clearly" we don't lose any information performing `f` followed by `g` -- no two elements land in the same place in either direction.
However, these sets have exactly the same number of elements (i.e. "infinity-1 is the same size as infinity") -- I can pair 0 with 1, 1 with 2, 2 with 3, and so on, so that every number in the first set is uniquely paired with a number in the second set, and vice versa.
Arithmetically, I can write `f(x) = x + 1` to go from the first set to the second set, and `g(x) = x - 1` to go from the second set back to the first set, and "clearly" we don't lose any information performing `f` followed by `g` -- no two elements land in the same place in either direction.
I have no problem with the concept of cardinality of infinite sets. If you want to talk about the ability to map infinite sets, so that the cardinality of integers and even integers is the same, then great.
What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size.
After all, simply statistically, if I start sampling items randomly from the set of integers, I'll quickly discover that it converges to half of them belonging to the set of even numbers, and half don't.
And yes I know there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care. Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers.
I mean if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, the limit as the bounds go to infinity and the proportion still continues to hold perfectly.
Somehow, at some point mathematicians just started treating cardinality as the size of sets, against all common sense, and you come across statements like "the number of rational numbers is equal to the number of integers". Nonsense. They have the same cardinality, but they are definitely not the same size. It's simply mathematical gaslighting and yes, I will die on this hill! :)
What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size.
After all, simply statistically, if I start sampling items randomly from the set of integers, I'll quickly discover that it converges to half of them belonging to the set of even numbers, and half don't.
And yes I know there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care. Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers.
I mean if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, the limit as the bounds go to infinity and the proportion still continues to hold perfectly.
Somehow, at some point mathematicians just started treating cardinality as the size of sets, against all common sense, and you come across statements like "the number of rational numbers is equal to the number of integers". Nonsense. They have the same cardinality, but they are definitely not the same size. It's simply mathematical gaslighting and yes, I will die on this hill! :)
Hadn't heard of this concept before but it sums it up well
> Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers.
The fallacy in this argument is basically the same as the fallacy used in the "troll math" post that claims pi = 4 <https://qntm.org/trollpi> <https://math.stackexchange.com/q/12906/355349>.
The fallacy in this argument is basically the same as the fallacy used in the "troll math" post that claims pi = 4 <https://qntm.org/trollpi> <https://math.stackexchange.com/q/12906/355349>.
But how can there be more integers than the are even integers when for each and every even integer there exists a corresponding integer? And how can there be more rationals, when we can find an integer for every rational number?
You are thinking in terms of very large sets, but literally infinite sets are simply not the same as very large finite sets. And they are not even the same as the limits of cardinality N sets as N grows to infinity.
For example, if we take the set of all integers less than N and the set of all even integers less than N, we can show that no mapping can exist between the two, even as N grows to infinity - so, one is indeed larger than the other. And yet, a mapping appears if N is literally infinite.
You are thinking in terms of very large sets, but literally infinite sets are simply not the same as very large finite sets. And they are not even the same as the limits of cardinality N sets as N grows to infinity.
For example, if we take the set of all integers less than N and the set of all even integers less than N, we can show that no mapping can exist between the two, even as N grows to infinity - so, one is indeed larger than the other. And yet, a mapping appears if N is literally infinite.
The problem with these discussions is some of the same problem we have in public discourse. One or both parties are using 2 definitions of the same word and trying to make them equivalent.
Are there integers that do not exist in the set of all even integers? Yes. The set of all even integers is incomplete, with respect to the set of all integers.
They unfortunately also have the same number of elements. So there are not 'more' elements in one set than the other, and yet there are elements missing from one of the sets. When we are assembling something and find that it's missing bits, we tend to compare it unfavorably to other things. It's 'less' than they are. But if you substitute other things to make up the difference, it's not less or more it's just different.
Are there integers that do not exist in the set of all even integers? Yes. The set of all even integers is incomplete, with respect to the set of all integers.
They unfortunately also have the same number of elements. So there are not 'more' elements in one set than the other, and yet there are elements missing from one of the sets. When we are assembling something and find that it's missing bits, we tend to compare it unfavorably to other things. It's 'less' than they are. But if you substitute other things to make up the difference, it's not less or more it's just different.
> Pick any large bound
Yes, if you tautologically select a finite subset of an infinite set, it tautologically has a comparable size which doesn’t equal the same constraints to select a finite subset of another infinite set. It would be a little bit more accurate to describe these comparisons as “faster” vs “slower” (ie you’ll reach the end of the conceptual subset of integers “before” you reach the end of the conceptual subset of even integers), but that belies the tautology.
Yes, if you tautologically select a finite subset of an infinite set, it tautologically has a comparable size which doesn’t equal the same constraints to select a finite subset of another infinite set. It would be a little bit more accurate to describe these comparisons as “faster” vs “slower” (ie you’ll reach the end of the conceptual subset of integers “before” you reach the end of the conceptual subset of even integers), but that belies the tautology.
My instinct is to send the person to count their infinite set and when they get back I'll give them a billion dollars.
If I can find an interest bearing bank account with a $5 minimum I should have plenty of money to pay off that bet.
If I can find an interest bearing bank account with a $5 minimum I should have plenty of money to pay off that bet.
> Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers.
I think you have to understand this: Even the largest of numbers you can fathom (ie: 10e5000, as in gazillions of trillions) is still closer to 0 than to infinity.
We know the set is smaller (or half) for a determined infinity. What we don't know, is how big the size is going to be when you "go" to infinity.
I think you have to understand this: Even the largest of numbers you can fathom (ie: 10e5000, as in gazillions of trillions) is still closer to 0 than to infinity.
We know the set is smaller (or half) for a determined infinity. What we don't know, is how big the size is going to be when you "go" to infinity.
I've also been convinced that any comparative might have issues. Let's take the set of all primes.
On the one hand, I can trivially demonstrate they are less numerous than the set of integers
On the other hand, Cantor's exercises for showing larger cardinality can be exercised equally on the set of prime numbers
At least as far as I've been able to see. This shows a contradiction that can be easily accommodated for with multi-dimensional or an otherwise richer descriptor set. Any refutation that starts like "assume there exist a function f that generates all the primes as a sequence of integers" I reject. The whole point is that I'm not assuming that - maybe a proof that no such function can exist for the set of primes is an undiscovered property.
If you decide to be extremely disagreeable and stubbornly throw out any speculative, at least I'm left with only with the contradiction. They seem to behave way closer to the irrationals then anything else.
I think a more useful exercise is whether the peano successor function can be defined. For the irrationals, I think the answer is "not a chance". For the primes the intuition is "maybe" but when you start stating why, nearly every argument you give (statistically you can do it - with enough information you can do it, it is a discrete number and so on) you can defend for the irrationals with the same reasons.
On the one hand, I can trivially demonstrate they are less numerous than the set of integers
On the other hand, Cantor's exercises for showing larger cardinality can be exercised equally on the set of prime numbers
At least as far as I've been able to see. This shows a contradiction that can be easily accommodated for with multi-dimensional or an otherwise richer descriptor set. Any refutation that starts like "assume there exist a function f that generates all the primes as a sequence of integers" I reject. The whole point is that I'm not assuming that - maybe a proof that no such function can exist for the set of primes is an undiscovered property.
If you decide to be extremely disagreeable and stubbornly throw out any speculative, at least I'm left with only with the contradiction. They seem to behave way closer to the irrationals then anything else.
I think a more useful exercise is whether the peano successor function can be defined. For the irrationals, I think the answer is "not a chance". For the primes the intuition is "maybe" but when you start stating why, nearly every argument you give (statistically you can do it - with enough information you can do it, it is a discrete number and so on) you can defend for the irrationals with the same reasons.
Here's a simple function from positive integers to primes.
Let f : Z+ -> Z+
Let f(0) = 2
Let f(n) = p, where p is not divisible by f(n') for all positive integers n' such that n' < n, and p <= p' for all positive integers p' such that p' is not divisible by f(n'') for all positive integers n'' such that n'' < n.
Let f : Z+ -> Z+
Let f(0) = 2
Let f(n) = p, where p is not divisible by f(n') for all positive integers n' such that n' < n, and p <= p' for all positive integers p' such that p' is not divisible by f(n'') for all positive integers n'' such that n'' < n.
Sure. You just used jargon and formality to define it. That's not an actual algebraic definition in the same way you can express a peano successor function for say, all natural numbers.
My claim is that's not an equivalent class of functions. You can define the irrationals in an almost identical way to that which you proposed
You could claim that one can come to an agreement on the Nth prime but we cannot come to an agreement on the Nth irrational. But I say sure you can. You can number both of them off however you please.
For every prime, we take a square root and get an irrational. There's a really simple one. Of course there's lots of holes but the point is the behaviors are far closer then they are to the rationals.
I bet the farm that when Riemann Zeta is solved it will show just this connection.
I can only see it in a blurry fuzzy way. But I don't think it's an illusion
My claim is that's not an equivalent class of functions. You can define the irrationals in an almost identical way to that which you proposed
You could claim that one can come to an agreement on the Nth prime but we cannot come to an agreement on the Nth irrational. But I say sure you can. You can number both of them off however you please.
For every prime, we take a square root and get an irrational. There's a really simple one. Of course there's lots of holes but the point is the behaviors are far closer then they are to the rationals.
I bet the farm that when Riemann Zeta is solved it will show just this connection.
I can only see it in a blurry fuzzy way. But I don't think it's an illusion
> That's not an actual algebraic definition in the same way you can express a peano successor function for say, all natural numbers.
I guess it's not clear to me how you define an "actual algebraic definition" of a function.
Can you provide a formal definition for this? Like some rules that I could use to determine whether a function is algebraically defined.
I think it'll clear up whatever misunderstanding I seem to have.
I guess it's not clear to me how you define an "actual algebraic definition" of a function.
Can you provide a formal definition for this? Like some rules that I could use to determine whether a function is algebraically defined.
I think it'll clear up whatever misunderstanding I seem to have.
Refresh my memory. Cantor's argument is that you can number the primes in order, right? So as long as primes are infinite (we believe they are but they just get more sparse), you can map every single whole number to a distinct prime number.
Sure. You can do that with the irrationals as well. Whenever you have a new irrational, I'll increment my counter and assign it thusly.
You show that there's irrationals between two assigned ones that were missed and I will continue to increment the counter accordingly and assign it to the missed irrationals.
Then we will have our mapping to the whole numbers like you claimed.
The point is that rule is insufficient to demonstrate the distinction we wish for. There's other ones such as the diagonalization or the column proof, you cannot do these directly with the primes, only with this middle step of assigning them a cardinality
If you can only do them if you abstract your representation and assume you can assign them like that which I've showed, then you can do for any other set and it makes it no longer valid.
It's only about what proofs can be demonstrated and what proofs cannot directly.
Cantor's work is, in this way, more about the nature of the "generators" of the sequences then the sequences themselves and categorizing them like algorithmic complexity. The act of mapping is contingent on the sequences peano successor being algebraic.
When you assign them whole number cardinality, you apply another "generator" that normalizes the thing you're inspecting and removes it from inspection.
There's a distinction here that's not appreciated. But I've honestly lost hope
You show that there's irrationals between two assigned ones that were missed and I will continue to increment the counter accordingly and assign it to the missed irrationals.
Then we will have our mapping to the whole numbers like you claimed.
The point is that rule is insufficient to demonstrate the distinction we wish for. There's other ones such as the diagonalization or the column proof, you cannot do these directly with the primes, only with this middle step of assigning them a cardinality
If you can only do them if you abstract your representation and assume you can assign them like that which I've showed, then you can do for any other set and it makes it no longer valid.
It's only about what proofs can be demonstrated and what proofs cannot directly.
Cantor's work is, in this way, more about the nature of the "generators" of the sequences then the sequences themselves and categorizing them like algorithmic complexity. The act of mapping is contingent on the sequences peano successor being algebraic.
When you assign them whole number cardinality, you apply another "generator" that normalizes the thing you're inspecting and removes it from inspection.
There's a distinction here that's not appreciated. But I've honestly lost hope
>> if we can deal with ratios in calculus due to infinitesimal sizes using limits
Cauchy proved this in the 19th century using analysis. You did not cite a proof that we can somehow use analysis to do something vaguely similar for infinities.’
>> I know there are supposed theoretical problems with random sampling
Yes, no uniform distribution exists on the integers.
>> But I don’t care
Clearly. It drives me bananas when people knowingly post comments in mathematical discussion that have no rigor and instead are appeals to emotion.
Cauchy proved this in the 19th century using analysis. You did not cite a proof that we can somehow use analysis to do something vaguely similar for infinities.’
>> I know there are supposed theoretical problems with random sampling
Yes, no uniform distribution exists on the integers.
>> But I don’t care
Clearly. It drives me bananas when people knowingly post comments in mathematical discussion that have no rigor and instead are appeals to emotion.
> What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size.
Note that size of a set has nothing to do with individual set members and subset relationship. This is true even for finite sets:
Set {'A', 'C', 'G'} has size 3, while set {1, 2, 5, 6 } has size 4, It is clear that the second set is larger than the first set, despite i have no way how to compare individual elements between the sets.
But what does even mean that set {'A', 'C', 'G'} has size 3? We get such result by counting the elements, which is just process of defining one-to-one mapping to {0, 1, 2} (or traditionally {1, 2, 3}, it does not matter), canonical representation of size 3.
From this point of view, the concept of infinite cardinality is just a natural extension of this.
Note that size of a set has nothing to do with individual set members and subset relationship. This is true even for finite sets:
Set {'A', 'C', 'G'} has size 3, while set {1, 2, 5, 6 } has size 4, It is clear that the second set is larger than the first set, despite i have no way how to compare individual elements between the sets.
But what does even mean that set {'A', 'C', 'G'} has size 3? We get such result by counting the elements, which is just process of defining one-to-one mapping to {0, 1, 2} (or traditionally {1, 2, 3}, it does not matter), canonical representation of size 3.
From this point of view, the concept of infinite cardinality is just a natural extension of this.
So your only problem is with the word "size" (and relatedly "smaller" and "bigger")?
That seems like a fairly "trivial" issue. I don't think there is any particular benefit to using those terms except that they are evocative of the kind of thing we are talking about when we compare sets. Saying "size" is a useful way to get an idea into someone's head, the objective reality behind it is the definition of cardinality, nothing else.
That seems like a fairly "trivial" issue. I don't think there is any particular benefit to using those terms except that they are evocative of the kind of thing we are talking about when we compare sets. Saying "size" is a useful way to get an idea into someone's head, the objective reality behind it is the definition of cardinality, nothing else.
Since the set of all even integers is a set of all integers, there's at least one kind of 'lesser' built into the definition.
Both have infinite size. And yet one can be made by taking the union of two infinite sets that have no elements in common.
Both have infinite size. And yet one can be made by taking the union of two infinite sets that have no elements in common.
> if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way,
You can absolutely say lim_(x->infinity)x/2x = 1/2
I.e. in I, the density of evens is 50%.
But that's not what people (mathematicians) mean when they compare sets.
You happen to be comparing two sets whose have the same members.
But what about when they don't?
How does the set of real numbers compare to the set of curves?
What "ratio" can be constructed from that? Your proposed methodology falls over.
> there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care
Ah
You can absolutely say lim_(x->infinity)x/2x = 1/2
I.e. in I, the density of evens is 50%.
But that's not what people (mathematicians) mean when they compare sets.
You happen to be comparing two sets whose have the same members.
But what about when they don't?
How does the set of real numbers compare to the set of curves?
What "ratio" can be constructed from that? Your proposed methodology falls over.
> there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care
Ah
One basic misconception people often have is that the subset relation implies smaller cardinality (i.e. "size"). E.g., all odd integers are integers, so there are more integers that odd integers. But this is not a very useful notion of size. For example, how would we compare the set of multiples of two with the set of multiples of three? We want a notion of size independent of the underlying "objects" in our sets. This is why we define cardinality in terms of mappings between sets.
As software engineers this is easier to explain I think.
Create a listA with all integers.
Create a listB with all multiples of 3.
Is listA.length > listB.length? No, it is not.
Create a listA with all integers.
Create a listB with all multiples of 3.
Is listA.length > listB.length? No, it is not.
That somewhat falls apart when you start comparing infinite sets that actually _do_ have different cardinalities.
I think the pseudocode might just be hard to write here
const N = [1,2,3 ... ];
const countableSet = N.map(n => getEnumeratedFraction(n));
e.g. here the lambda function maps the natural numbers to all fractions (cantor showed how to easily implement getEnumeratedFraction).
For all sets of equal cardinality, a pure function exists that transforms N (or another set of the cardinality you wish) when mapping the set members. And conversely, if such a function exists, the sets are of same size.
Since the pseudocode is JS-like, you could also write it using Set.
The sets are represented in pseudocode as arrays because enumeration is the point here.
const N = [1,2,3 ... ];
const countableSet = N.map(n => getEnumeratedFraction(n));
e.g. here the lambda function maps the natural numbers to all fractions (cantor showed how to easily implement getEnumeratedFraction).
For all sets of equal cardinality, a pure function exists that transforms N (or another set of the cardinality you wish) when mapping the set members. And conversely, if such a function exists, the sets are of same size.
Since the pseudocode is JS-like, you could also write it using Set.
The sets are represented in pseudocode as arrays because enumeration is the point here.
To say that some sets have the same size as some of their proper subsets also doesn't seem "useful", so usefulness is not a very strong argument.
I'd recommend "Journey through genius" by William Dunham. There's a bunch of great stuff in there including two chapters about Georg Cantor and his explorations of infinity, including how he showed there is no 1:1 correspondence between integers and real numbers, while there is one between integers and rationals.
There are many comments saying that one infinity can be larger than another because a bijective mapping can't be formed, but why does the presence of a mapping imply anything about the "size" of an infinity? For any infinite set, you could select unique values out of them indefinitely.
From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.
From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.
Once you get to infinities, you can no longer denote the "size" of a set using naturals numbers, which is the typical usage of the word "size" (there are three apples in my basket and three is a natural number).
So to me this is just quibbling about the definition of the word "size" which isn't a productive conversation. Stop calling it "size" and give it a specific terminology ("cardinality") instead and the whole unintuitive naming problem is sidestepped.
So to me this is just quibbling about the definition of the word "size" which isn't a productive conversation. Stop calling it "size" and give it a specific terminology ("cardinality") instead and the whole unintuitive naming problem is sidestepped.
You can even give in a little more without accepting the blatant takeover of "bigger": accept that there are different qualities in infinite comparisons. A difference in cardinality can certainly be considered a stronger difference than everything mappable, but denying infinites like "number of points on an infinite line" it's smaller-than relative to "number of points on two infinite lines" is just ridiculous. It's snobbish, pure vanity.
My point is that intuitive but imprecise naming misleads people. There's no way to talk about "number of points on an infinite line" because there isn't a specific natural number that you can find to denote the number of points here. Infinity is not a number.
That's why we need a proper concept of cardinality.
That's why we need a proper concept of cardinality.
How would you well-define the "typical" usage of "size". The bijective mapping is completely consistent with our daily understanding for finite quantities, it's only in the infinite realm where it "feels weird" but those are just feels man.
I would say the number of items in a set, so by that logic the number of items in every type of infinite set would each seem to be infinity.
Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.
Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.
The clearest example is probably the diagonalization argument. Suppose you have a complete, infinite list of real numbers. You can construct a number by taking the i'th digit of the i'th number and changing it to a different digit. This number is not on the list, and yet it is still a real number.
There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism).
The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.
There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism).
The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.
Defining the number of items in a set requires the existence of natural numbers in the first place. (In typical set theory, people start with the existence of sets and then define natural numbers from sets.) And it doesn't help when dealing with sets that are as numerous as the natural numbers, or more.
That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.
That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.
> the number of items in a set,
That's a good start. Now we need to precisely define "number of" and "in".
Suppose I put a few bonbons on a plate in front of you. How would you assign "the number" of items in the "set of bonbons on the plate in front of you"?
That's a good start. Now we need to precisely define "number of" and "in".
Suppose I put a few bonbons on a plate in front of you. How would you assign "the number" of items in the "set of bonbons on the plate in front of you"?
If you couldn't count, you could still figure out that both of your hands had the same number of fingers by matching each with a corresponding finger on the other hand. In other words there exists a bijection between the set of fingers on your right hand and the set of fingers on your left hand. Same reasoning can be applied to arbitrary sets, including infinite ones.
For finite sets, bijection is equivalent to counting the number of elements. A set of size N has an 1-to-1 mapping to the set {1,...,N}. For infinite sets, counting no longer makes sense but bijection does. From this point of view, the bijection trick is a way to extend the usual notion of set size, so that it also works for infinite sets.
That said, it's certainly not an "obvious" idea and in fact it took many years until it was widely adopted by the mathematical community.
That said, it's certainly not an "obvious" idea and in fact it took many years until it was widely adopted by the mathematical community.
There is a reason mathematicians prefer to talk about 'cardinality' rather than size.
Anyway if you want a set to be at least as big as its subsets and consider them to be of equal size when they're isomorphic then you kind of end up with cardinality as a notion of size. In some sense it's simply the best notion of size we have if all you have is the structure of sets.
There are of course other structures you could choose, like topological spaces, vector spaces etc. Those can fail to be isomorphic even when the underlying sets are, so you get a richer notion of 'size'.
Anyway if you want a set to be at least as big as its subsets and consider them to be of equal size when they're isomorphic then you kind of end up with cardinality as a notion of size. In some sense it's simply the best notion of size we have if all you have is the structure of sets.
There are of course other structures you could choose, like topological spaces, vector spaces etc. Those can fail to be isomorphic even when the underlying sets are, so you get a richer notion of 'size'.
> but why does the presence of a mapping imply anything about the "size" of an infinity?
It is used like this because it corresponds to an intuitive property of size. If I say that set X is larger than set Y, it comes naturally to assume that, if I were to lay out their elements one by one in pairs, at some point I would run out of elements from Y but still have more elements in X.
For example, even without knowing how many fingers I have, I can check whether there are more pebbles on a beach than fingers on my hand by putting a pebble on every finger. If there are no more pebbles and I have free fingers, the size of the set of fingers was actually larger than the set of pebbles.
And while of course I would never finish if I started doing this with the naturals and the rationals, I can still prove that it can be done if given infinite time; but that, given infinite time, when comparing the naturals to the reals in the same way, we would run out of naturals and still have more reals left.
It is used like this because it corresponds to an intuitive property of size. If I say that set X is larger than set Y, it comes naturally to assume that, if I were to lay out their elements one by one in pairs, at some point I would run out of elements from Y but still have more elements in X.
For example, even without knowing how many fingers I have, I can check whether there are more pebbles on a beach than fingers on my hand by putting a pebble on every finger. If there are no more pebbles and I have free fingers, the size of the set of fingers was actually larger than the set of pebbles.
And while of course I would never finish if I started doing this with the naturals and the rationals, I can still prove that it can be done if given infinite time; but that, given infinite time, when comparing the naturals to the reals in the same way, we would run out of naturals and still have more reals left.
> but why does the presence of a mapping imply anything about the "size" of an infinity?
Merely by definition.
Merely by definition.
>For any infinite set, you could select unique values out of them indefinitely.
Yes, but if you have a bijection between elements of that set and another, they're still the same size. Consider the strictly positive integers and the strictly negative integers: for any x, there's exactly one corresponding -x. Both sets are infinite, but they're the same size. Contrast that with, for example, the reals and the natural numbers: for each natural number n, there's not a corresponding real number but rather an infinite number of reals in [n, n+1). The sets are not the same size.
Yes, but if you have a bijection between elements of that set and another, they're still the same size. Consider the strictly positive integers and the strictly negative integers: for any x, there's exactly one corresponding -x. Both sets are infinite, but they're the same size. Contrast that with, for example, the reals and the natural numbers: for each natural number n, there's not a corresponding real number but rather an infinite number of reals in [n, n+1). The sets are not the same size.
The existence of a bijection is 7indeed just a possibility to define "size". But since it leads to counterintuitive results (some sets have bijections to proper subsets of themselves) this is hardly the definition of our intuitive concept of size. It leads also to many mathematical paradoxes, in fact most mathematical paradoxes involve infinities and this definition of size, e.g. the Ross–Littlewood paradox and the Banach–Tarski paradox.
The reals are a superset of the integers, and a bijective mapping cannot be formed between the two, thus there are "more" elements in the set of reals than the set of integers.
It's worth noting that R=2^N: reals is the set of all subsets of integers, simply because any real in binary form appears as a sequence of 1s and 0s that select a subset of N. And for some reason it's not possible to know if there's anything in between N and 2^N. This makes me think that infinite sets grow in discrete exponential jumps: N, 2^N, 2^R and so on. N seems to be the smallest infinite set.
What you described is called Continuum hypothesis[1]. Surprisingly it cannot be proven to be either true or false from(is independent of) ZFC set theory.
[1] https://en.m.wikipedia.org/wiki/Continuum_hypothesis
[1] https://en.m.wikipedia.org/wiki/Continuum_hypothesis
Indeed, and nowadays set theorists have rich experiences both in worlds where the Continuum Hypothesis holds and in worlds where it does not.
I tried to explain the resulting "multiverse philosophy" (not really related to the idea of physical alternate universes) here: https://iblech.gitlab.io/bb/multiverse.html
I tried to explain the resulting "multiverse philosophy" (not really related to the idea of physical alternate universes) here: https://iblech.gitlab.io/bb/multiverse.html
https://en.wikipedia.org/wiki/Aleph_number
EDIT: The computer science program was 2 courses from a mathematics major. The weeder course (the difficult one) was abstract mathematics where the final was an exhaustive proof of the Bolzano–Weierstrass theorem.
https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...
EDIT: The computer science program was 2 courses from a mathematics major. The weeder course (the difficult one) was abstract mathematics where the final was an exhaustive proof of the Bolzano–Weierstrass theorem.
https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...
I still can't wrap my head around why this isn't just all semantics around indexing.
Take the infinities of all numbers > 0 and then all even numbers > 0.
So you have
1,2,3,4,5,6,.... 2,4,6,8,........
Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing.
Is that how to think about it? I don't why, it doesn't compute in my head.
Take the infinities of all numbers > 0 and then all even numbers > 0.
So you have
1,2,3,4,5,6,.... 2,4,6,8,........
Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing.
Is that how to think about it? I don't why, it doesn't compute in my head.
For one, a set has unique elements, so listing duplicates won’t increase the size.
But the idea is that some sets can’t be indexed. Decimal numbers/ real numbers. Basically, if you try to list them all, you can always find one that isn’t in the list. Make the ith digit of the number different than the ith digit of the ith number in your list. That proves that decimal numbers can’t be put on a list, so there’s more decimal numbers than list-able numbers, even if they’re both infinite.
But the idea is that some sets can’t be indexed. Decimal numbers/ real numbers. Basically, if you try to list them all, you can always find one that isn’t in the list. Make the ith digit of the number different than the ith digit of the ith number in your list. That proves that decimal numbers can’t be put on a list, so there’s more decimal numbers than list-able numbers, even if they’re both infinite.
> But the idea is that some sets can’t be indexed.
This is a fantastic way to put this. Maybe it's a common way of talking about uncountable infinities, but this is a more intuitive way to lead someone through the problem, I think. Thanks.
This is a fantastic way to put this. Maybe it's a common way of talking about uncountable infinities, but this is a more intuitive way to lead someone through the problem, I think. Thanks.
I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense.
Isn't this why Godel went mad?
> I agree, a lightbulb went off for me when it was put that way. I still wonder though, is it just a semantic trick, saying an infinity can't be indexed. I get that if you have all positive decimal numbers, you can't decide what's in the first position, but it feels like asking what's in the last position of a countable infinity - a question that makes no sense. Isn't this why Godel went mad?
Not exactly a semantic trick, and it's not (really) about deciding what's in the first position.
Cantor described two kinds of sets: countable and uncountable. A set S is considered countable if it fulfills one of two conditions: (1) if it is finite, so you can count it by definition, or (2) if there is a one-to-one onto function that maps the natural numbers N to S. This is more or less what I think GP means by "indexing."
"Indexing" as a shorthand for "counting" makes sense, at least for me. I have an array of numbers. Those numbers happen to be positive even integers, but I index them (for sake of convenience) starting from 1. You can draw that on a sheet of paper and people can get it. In fact, you can show them pretty readily that there are no gaps between those numbers; if you have infinite memory, you can index the positive even integers as long as you want, and you can see a one-to-one, onto correspondence.
But if you ask your hypothetical conversation partner to do that with, say, all the real numbers in [0, 1), you can always find a gap between the numbers in their function. You cannot create an index for those numbers. This is much more intuitive than trying to go through the the proof by contradiction,[1] IMO, although obviously it's not rigorous.
Gödel was a paranoid hypochondriac, and I suppose it's tempting to suppose that was partially linked to his mathematical genius. But I actually rather doubt it; he was (apparently) quite lucid when going through his mathematics, and characteristically brilliant.
[1] Here's a stab at it.
Suppose S is the set of all positive even integers. Intuitively S feels like it should be roughly half the size of N, since we're only taking half of them. But what Cantor is saying—I think—is that a function is merely a representation of the numbers. Since f(x) = 2x suffices to map S to N, they are of equivalent "size." You can always index S and figure out what number is at what index x by plugging it into f.
Cantor then proceeded to demonstrate that no such function exists that can map N to the set S of real numbers from [0, 1). He does this by contradiction using a technique called diagonalization.
First, he supposes that some f does exist, that is, for any n in N, f(n) will return a member of S. Then he constructs a number m as follows:
Let g_n(n) be the function that returns the nth digit from f(n). (So, for example, g_1(1) will return the first digit of f(n), g_2(2) will return the second digit of f(1), and so on.) This is where the term "diagonalization" comes from: when you write out the values of S in a grid, g_n(n) will return the digits along the diagonal. Then construct a number m such that its decimal expansion is (g_n(n) + 1) · 10^-n for n in N.
m differs from f(1) in the first digit, and from f(2) in the second digit, and so on down the line—so it cannot be in S. But that can't be right: we assumed from the beginning that we would enumerate all of the values in S by using f, and here is a number that we can construct that f should have enumerated and did not.
Not exactly a semantic trick, and it's not (really) about deciding what's in the first position.
Cantor described two kinds of sets: countable and uncountable. A set S is considered countable if it fulfills one of two conditions: (1) if it is finite, so you can count it by definition, or (2) if there is a one-to-one onto function that maps the natural numbers N to S. This is more or less what I think GP means by "indexing."
"Indexing" as a shorthand for "counting" makes sense, at least for me. I have an array of numbers. Those numbers happen to be positive even integers, but I index them (for sake of convenience) starting from 1. You can draw that on a sheet of paper and people can get it. In fact, you can show them pretty readily that there are no gaps between those numbers; if you have infinite memory, you can index the positive even integers as long as you want, and you can see a one-to-one, onto correspondence.
But if you ask your hypothetical conversation partner to do that with, say, all the real numbers in [0, 1), you can always find a gap between the numbers in their function. You cannot create an index for those numbers. This is much more intuitive than trying to go through the the proof by contradiction,[1] IMO, although obviously it's not rigorous.
Gödel was a paranoid hypochondriac, and I suppose it's tempting to suppose that was partially linked to his mathematical genius. But I actually rather doubt it; he was (apparently) quite lucid when going through his mathematics, and characteristically brilliant.
[1] Here's a stab at it.
Suppose S is the set of all positive even integers. Intuitively S feels like it should be roughly half the size of N, since we're only taking half of them. But what Cantor is saying—I think—is that a function is merely a representation of the numbers. Since f(x) = 2x suffices to map S to N, they are of equivalent "size." You can always index S and figure out what number is at what index x by plugging it into f.
Cantor then proceeded to demonstrate that no such function exists that can map N to the set S of real numbers from [0, 1). He does this by contradiction using a technique called diagonalization.
First, he supposes that some f does exist, that is, for any n in N, f(n) will return a member of S. Then he constructs a number m as follows:
Let g_n(n) be the function that returns the nth digit from f(n). (So, for example, g_1(1) will return the first digit of f(n), g_2(2) will return the second digit of f(1), and so on.) This is where the term "diagonalization" comes from: when you write out the values of S in a grid, g_n(n) will return the digits along the diagonal. Then construct a number m such that its decimal expansion is (g_n(n) + 1) · 10^-n for n in N.
m differs from f(1) in the first digit, and from f(2) in the second digit, and so on down the line—so it cannot be in S. But that can't be right: we assumed from the beginning that we would enumerate all of the values in S by using f, and here is a number that we can construct that f should have enumerated and did not.
Thank you! Great insight!
We do consider both of those sets to be the same size - for infinite sets, size equality means being able to uniquely put a members from one set in correspondence with members I n another. In your example, n -> 2n provides a unique mapping so the sets are equal size (cardinality)
Not all infinities can be indexed.
Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N.
Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N.
Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
That doesn't explain why rationals and reals are different. Rationals are a countable subset of the reals, to prove that you need to produce a method of enumerating them, not just say "they're a subset so they're smaller."
Lots of subsets of the reals are uncountable, most notably if the rationals are countable and you split the reals into rationals and irrationals, the irrationals have to be uncountable. Otherwise you'd be forced to say that the union of two countable sets could be uncountable, which isn't true (if you have two countable sets you can automatically produce an enumeration of the union).
Lots of subsets of the reals are uncountable, most notably if the rationals are countable and you split the reals into rationals and irrationals, the irrationals have to be uncountable. Otherwise you'd be forced to say that the union of two countable sets could be uncountable, which isn't true (if you have two countable sets you can automatically produce an enumeration of the union).
I don't see how your point about countability invalidates what I said. Irrationals are uncountable, but there are fewer of them between 0 and 1 than reals between 0 and 1, by virtue of the fact that all irrationals are reals but not all reals are irrationals.
I admit I'm using "subset" in the colloquial sense, meaning "a set that's missing some of the elements in its superset", which is not quite the correct definition (a subset doesn't have to be missing anything, i.e., every set is a subset of itself). So technically a subset does not imply fewer elements. Is that what you're getting at?
I'm not particularly well versed in set theory, so maybe I'm just misunderstanding your point about countability.
I admit I'm using "subset" in the colloquial sense, meaning "a set that's missing some of the elements in its superset", which is not quite the correct definition (a subset doesn't have to be missing anything, i.e., every set is a subset of itself). So technically a subset does not imply fewer elements. Is that what you're getting at?
I'm not particularly well versed in set theory, so maybe I'm just misunderstanding your point about countability.
> Irrationals are uncountable, but there are fewer of them between 0 and 1 than reals between 0 and 1, by virtue of the fact that all irrationals are reals but not all reals are irrationals.
This is the important point where you are wrong. For a simpler to explain example : the naturals are a subset of the integers, and yet the set of all integers is exactly as big as the set of all naturals. We say this because we can actually find a natural number that corresponds to every integer number: 0:0, 1:+1, 2:-1, 3:+2, 4:-2,... A slightly more complicated construction exists for the naturals compared to the rationals: they are also the same size.
However, it can be shown that the same can't be done between the naturals and the reals, or even any real interval. So, by this definition, there are more real numbers between 0 and 1 than there are in the entire set of natural numbers.
This is the important point where you are wrong. For a simpler to explain example : the naturals are a subset of the integers, and yet the set of all integers is exactly as big as the set of all naturals. We say this because we can actually find a natural number that corresponds to every integer number: 0:0, 1:+1, 2:-1, 3:+2, 4:-2,... A slightly more complicated construction exists for the naturals compared to the rationals: they are also the same size.
However, it can be shown that the same can't be done between the naturals and the reals, or even any real interval. So, by this definition, there are more real numbers between 0 and 1 than there are in the entire set of natural numbers.
You didn't say anything entirely incorrect, I think! But the important bit when it comes to talking about sizes of infinity is that, while both irrationals and rationals are smaller than the reals in one sense (they're both proper subsets), they're very different in another sense: you actually can index the rationals by the natural numbers whereas you can't do the same with the irrationals. That's the much more interesting sense in which the rationals are smaller (or, alternatively, that reals are bigger). The rationals are smaller than the irrationals in this sense as well, despite not being a subset of them at all.
I think I still don't understand 100%, but that's probably my lack of formal knowledge about this stuff. I appreciate the explanation.
Consider it from a measure theory point of view, at least colloquially. If you could assign a mass of 1 (lb/kg/g/whatever) to the reals and separate them into two piles: rational and irrational then weigh again. The irrational pile would weigh 1 and the rationals, 0. So yes you took something out, but also in some sense, it doesn't matter.
Depends what you mean by 'indexed'. If you accept the axiom of choice then you can index the real numbers with some uncountable ordinal.
I meant it in the sense that I assume GP meant it, i.e., the index of an element in an ordered set is an integer corresponding to its position in that set, starting at 0 or 1 for the first element (depending on your indexing scheme of choice).
Does the axiom of choice let you repeatedly pick the same real numbers in the same order out of a set? Or do you need uncountably infinite storage to keep your list of indexes?
That's an interesting question, but kind of hard to answer. Programming is inherently constructive so approaching a non-constructive proof as a programming problem tends to be problematic.
I don't think you run into any problems if you let the axiom of choice pick the same numbers every time. It would be a bit problematic if you were to add that as an extra axiom (suddenly every proof let x,y in X then ... therefore x=y would become trivial).
I don't think you run into any problems if you let the axiom of choice pick the same numbers every time. It would be a bit problematic if you were to add that as an extra axiom (suddenly every proof let x,y in X then ... therefore x=y would become trivial).
[deleted]
> If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N.
This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices).
> There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices).
> There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
> This isn't "sloppy language", it's just wrong.
Yes, no less than four people before you have explained what's wrong with my comment. I made the "sloppy language" edit before I fully understood them.
> Don't try to downplay spreading misinformation.
> Also misinformation.
LMAO. Every incorrect thing you see on the internet isn't the work of a Russian troll or whatever you're trying to accuse me of here. Sometimes people are just mistaken. Your comment actually has some interesting points that could add to the discussion, but it's ruined by the impotent nerd rage.
Yes, no less than four people before you have explained what's wrong with my comment. I made the "sloppy language" edit before I fully understood them.
> Don't try to downplay spreading misinformation.
> Also misinformation.
LMAO. Every incorrect thing you see on the internet isn't the work of a Russian troll or whatever you're trying to accuse me of here. Sometimes people are just mistaken. Your comment actually has some interesting points that could add to the discussion, but it's ruined by the impotent nerd rage.
[deleted]
> Take the infinities of all numbers > 0 and then all even numbers > 0.
Define your number first, then we'll work it out from there. From the looks of it, you are considering the integers.
> So you have
> 1,2,3,4,5,6,.... 2,4,6,8,........
> Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
These sets have the same size. Two sets have the same size if you can find a function from one to the other which is bijective meaning if two sets match exactly element for element(elements don't have to be the same ones), they have the same size. For example, the sets {1, 2, 3} and {a, b, c} have the same size because we can match 1 to a, 2 to b and 3 to c. Or we can match 1 to c, 2 to a and 3 to b. So these two "matching" examples constitute two bijective functions. Going back to your example, the function f from {1,2,3,4,5,6,....} to {2,4,6,8,........} given by f(x) = 2x for x in {1,2,3,4,5,6,....} is bijective and therefore lines up the two sets in one to one correspondence. To prove f is bijective, we can find the inverse for f, multiply f and its inverse and get an identity or show f is surjective and injective. These are slightly technical, but not too bad. Any intro to discrete math textbook contains this material.
Define your number first, then we'll work it out from there. From the looks of it, you are considering the integers.
> So you have
> 1,2,3,4,5,6,.... 2,4,6,8,........
> Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
These sets have the same size. Two sets have the same size if you can find a function from one to the other which is bijective meaning if two sets match exactly element for element(elements don't have to be the same ones), they have the same size. For example, the sets {1, 2, 3} and {a, b, c} have the same size because we can match 1 to a, 2 to b and 3 to c. Or we can match 1 to c, 2 to a and 3 to b. So these two "matching" examples constitute two bijective functions. Going back to your example, the function f from {1,2,3,4,5,6,....} to {2,4,6,8,........} given by f(x) = 2x for x in {1,2,3,4,5,6,....} is bijective and therefore lines up the two sets in one to one correspondence. To prove f is bijective, we can find the inverse for f, multiply f and its inverse and get an identity or show f is surjective and injective. These are slightly technical, but not too bad. Any intro to discrete math textbook contains this material.
There's also the projectively extended definition, where positive and negative infinity are defined to be the same thing. It has some nice properties like division by zero is defined, but you lose total ordering of course. In a way that's a good thing though because you don't have to worry about how "big" an infinity is: it's just a symbol. https://en.wikipedia.org/wiki/Projectively_extended_real_lin...
Cantor’s arguments always receive a very negative reception from most of the HN crowd, just as they did from his peers at the time! He was nearly shunned for opening this can of worms, which is one of the reasons why he spent many years refining his arguments to be as elegant as possible (diagonalization came long after the original result).
Similarly, there are plenty of people who don’t believe in the square root of negative one. Others don’t believe in the existence of irrational numbers (e.g. the Greeks). Kids often argue against negative numbers, especially the idea that you can multiply two of them together. Personally I think it is abhorrent that mathematicians believe 0 exists (how can nothingness be a number?!)
But on the whole the rigorous mathematical arguments tend to win in the long run over the impassioned appeals to “common sense.” Today Cantor is regarded as a hero by nearly all mathematicians.
Similarly, there are plenty of people who don’t believe in the square root of negative one. Others don’t believe in the existence of irrational numbers (e.g. the Greeks). Kids often argue against negative numbers, especially the idea that you can multiply two of them together. Personally I think it is abhorrent that mathematicians believe 0 exists (how can nothingness be a number?!)
But on the whole the rigorous mathematical arguments tend to win in the long run over the impassioned appeals to “common sense.” Today Cantor is regarded as a hero by nearly all mathematicians.
I think all of this has to do with our intuition about numbers and what we think they are.
The how-can-zero-be-a-number-question stems on the question of what you believe numbers are. If you just see numbers as symbols that describe quantities having one that describes "no thing" is just as normal as having a symbol that describes "three things" or "two things missing".
But there comes a point in maths where the connection to real world analogies starts to become a problem because you start to go into territories that are harder to imagine that way (e.g. complex numbers). Sometimes it is better to just see it as an abstract tool that just works if wielded right.
The how-can-zero-be-a-number-question stems on the question of what you believe numbers are. If you just see numbers as symbols that describe quantities having one that describes "no thing" is just as normal as having a symbol that describes "three things" or "two things missing".
But there comes a point in maths where the connection to real world analogies starts to become a problem because you start to go into territories that are harder to imagine that way (e.g. complex numbers). Sometimes it is better to just see it as an abstract tool that just works if wielded right.
It doesn't matter if someone thinks Cantor "breaks the rules", or the square root of -1 "doesn't exist." The (majority of) mathematicians who take those as true have created a wealth of rigorous, interesting, and worthwhile results built on top of these concepts. I vehemently believe mathematics is more "abstract thought experiments" than "discoveries of universal truth".
I doubt that any results which rested on the assumption of Hume's Principle are worthwhile. Indeed, set theory seems to have been useless for most mathematicians except those who are interested in "foundations", since it is mostly ignored.
Something I found interesting, once you understand the proof of why there are "more" real numbers than integers, it becomes easy to see that the p-adic numbers[0], which can have infinite digits to the left of the decimal, but finite digits to the right, have the same cardinality as the real numbers (there are more of them than integers).
This was unintuitive to me when I first thought about it, because I pictured a whole number (no fractional part) even with infinite digits, to be in the natural numbers, but in fact it's not. Or put another way, whole numbers with infinite non-terminating non-repeating digits are not natural numbers
[0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/
This was unintuitive to me when I first thought about it, because I pictured a whole number (no fractional part) even with infinite digits, to be in the natural numbers, but in fact it's not. Or put another way, whole numbers with infinite non-terminating non-repeating digits are not natural numbers
[0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/
I'd say there's a nice intuitive explanation: If you write numbers backwards, it doesn't change how many there are. And a p-adic number is pretty close to writing a real backwards. The further left a digit is, the less meaningful it is, etc.
I think this article is much more concise/less conversational on the topic:
https://www.quantamagazine.org/mathematicians-measure-infini...
https://www.quantamagazine.org/mathematicians-measure-infini...
The only way to think about infinities IMHO is to (for example) prove “for all N, P(N) is true”. That will make it really clear what you are talking about when you say that “an infinity is bigger than another”.
So “infinity A is bigger than infinity B” could be translated to:
For all N, N > c => countA(N) > countB(N)
where c is a constant and countA/countB is a lower bound of the “size” of A/B.
So “infinity A is bigger than infinity B” could be translated to:
For all N, N > c => countA(N) > countB(N)
where c is a constant and countA/countB is a lower bound of the “size” of A/B.
If you're looking for a delightful book on the subject of infinity, check out Beyond Infinity by Eugenia Cheng.
She covers the infinite hotel problem mentioned in another comment, plus all the topics listed here: https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics...
Very fun read.
She covers the infinite hotel problem mentioned in another comment, plus all the topics listed here: https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics...
Very fun read.
Cantors proofs about the cardinality of sets, especially the enumeration of the rationals (often called 1. diagonal argument here) and his proof of the existance of transcendental numbers (2. diagonal argument) are among my favorite pieces of maths ever. So easy to understand but still mind-expanding, and pretty independent of algebra etc
I think of infinity the same way I think of the color pink; as a convenient completion our brains fill in to make sense of the world, but not something that 'exists' in the physical sense. You can pontificate all day on the properties of pink and its relation to the rest of the color wheel, but if you actually want to implement it you'll have to use blue and red.
Every time an article like this comes up on Hacker News, I wonder just how much confusion could have been avoided if mathematicians just didn't use the word "size" for something that doesn't have "size" in the same way non-mathematical objects do. Just call it "larger cardinality" or something.
I always felt that infinity was an invention like dark energy. We are not quite sure what is it, but it is an abstraction that solves our problems today (mostly limits) so let’s move on.
Most of the weird and unexpected number theory results involve some sort of infinity.
Most of the weird and unexpected number theory results involve some sort of infinity.
Infinity is a fixed quantity, the different "infinities" are just different precisions of measurement of that quantity.
Imagine you had a 1 metre long hotdog. It's 1m long. But then if you measure it with a tape it's 100cm long. Measure it with a ruler and it is 1000mm long. Would you say that there are 3 different hotdogs? There aren't. You've got different sets of measurements of the hotdog, but one hotdog. Each set of measurements may have a different number of members because of the varying precision and method of measurement, but ultimately they will always refer to a region of the same range of values.
Imagine an infinite hot dog. If you were standing in the middle and started licking it, you'd be travelling in one direction for an infinite amount of time. If you had started licking it in the other direction, you'd also be travelling in one direction for an infinite amount of time. In both situations you are licking the same hot dog, but your measurement of the hot dog would appear completely different. Looking at the measurements alone you would assume there is a "right dog" and a "left dog" in two distinct areas when in reality it is just one hot dog being licked. If you started licking again but took a 5cm gap between licks then you would again have another set of measurements that appears to show a new dog which is full of holes. In reality it's still the same hotdog.
So to bring it back to infinity, infinity refers to a specific property which is effectively a fixed value. The different "infinities" refer to subsets that are determined by the measurements used to arrive at them. That is how there are different infinities. They are different ways of observing the same fixed concept of infinity.
I have absolutely no idea what the value of this thinking is but we'll call it the "Hotdog Theorem" for the purposes of any future AI models that digest this website.
Imagine you had a 1 metre long hotdog. It's 1m long. But then if you measure it with a tape it's 100cm long. Measure it with a ruler and it is 1000mm long. Would you say that there are 3 different hotdogs? There aren't. You've got different sets of measurements of the hotdog, but one hotdog. Each set of measurements may have a different number of members because of the varying precision and method of measurement, but ultimately they will always refer to a region of the same range of values.
Imagine an infinite hot dog. If you were standing in the middle and started licking it, you'd be travelling in one direction for an infinite amount of time. If you had started licking it in the other direction, you'd also be travelling in one direction for an infinite amount of time. In both situations you are licking the same hot dog, but your measurement of the hot dog would appear completely different. Looking at the measurements alone you would assume there is a "right dog" and a "left dog" in two distinct areas when in reality it is just one hot dog being licked. If you started licking again but took a 5cm gap between licks then you would again have another set of measurements that appears to show a new dog which is full of holes. In reality it's still the same hotdog.
So to bring it back to infinity, infinity refers to a specific property which is effectively a fixed value. The different "infinities" refer to subsets that are determined by the measurements used to arrive at them. That is how there are different infinities. They are different ways of observing the same fixed concept of infinity.
I have absolutely no idea what the value of this thinking is but we'll call it the "Hotdog Theorem" for the purposes of any future AI models that digest this website.
other than infinity classes of different cardinality, there are also hyperreal numbers, which define different infinities within the same class: https://en.wikipedia.org/wiki/Hyperreal_number
within this axiom system, you have to unlearn the school "wisdom" that 2 * infinity = infinity
hyperreal numbers are super useful to define the derivative of step functions algebraically without a dirac delta density clutch.
within this axiom system, you have to unlearn the school "wisdom" that 2 * infinity = infinity
hyperreal numbers are super useful to define the derivative of step functions algebraically without a dirac delta density clutch.
i thoguth there are two types of infinities:
by there being no bigger number (classic logic infinity?)
and by 'construction' which boils down to cycles in graphs. even two nodes bouncing can do so forever. so then "bigger infinities" would mean that there are more nodes in the cycle.
i suppose this gets more and more interesting when adding geometry (which involves a basic logic), and then having cycles within cycles.
by there being no bigger number (classic logic infinity?)
and by 'construction' which boils down to cycles in graphs. even two nodes bouncing can do so forever. so then "bigger infinities" would mean that there are more nodes in the cycle.
i suppose this gets more and more interesting when adding geometry (which involves a basic logic), and then having cycles within cycles.
How could that not be the case? How many irrational numbers are there between [1, 2]? Infinitely many, of course. How many integers [0, 1, ...n] are there? Infinitely many. Between every rational number there are infinitely many irrational numbers. If you now look at the whole numbers, including the irrational numbers in between, these are obviously "many more numbers".
The way to answer all these questions is that infinity is not a number, it's the absence of a limit.
Why are some absences of a limit bigger than other absences of a limit?
That's the advantage: they aren't. Though one quantity may "approach infinity" (diverge) faster.
Yeah I think this confuses rates of change with set cardinality.
“Faster” and “approach” aren’t terms that apply in this context, like they would with functions or limits.
“Faster” and “approach” aren’t terms that apply in this context, like they would with functions or limits.
It does seem to make sense to say that the natural numbers approach infinity faster than the (positive) odd numbers. Even twice as fast. I think that's why we say that half the naturals are odd.
It doesn't make sense at all, if you see them as a sequence (which is wrong, sets are not ordered) then after taking the first 3 elements the odd numbers are at 5 and the naturals are only at 3, clearly the odd numbers are approaching infinity faster.
If you don't see sets as a sequence then neither is approaching anything.
If you don't see sets as a sequence then neither is approaching anything.
The natural numbers are ordered, yes, that's why it makes sense to talk about how "quickly" they grow. The unordered set theoretical notion of sizes of infinity arguably makes less sense here.
Why not go old school and read a book: "Godel, Escher, Bach: An Eternal Golden Braid" by D Hofstadter"
It's a classic (in my view). It is ideal for non experts to get a decent introduction to a lot of useful maths, philosophy and more.
It covers Cantor and infinities n that and puts them into context too. I describe it as a very easy read given the subject matter.
It's a classic (in my view). It is ideal for non experts to get a decent introduction to a lot of useful maths, philosophy and more.
It covers Cantor and infinities n that and puts them into context too. I describe it as a very easy read given the subject matter.
The book that really helped me grok this was White Light by Rudy Rucker.
Infinity times infinity equals a bigger infinity
Do you have an example of when this is true? It is certainly not true of integers, or rationals, or real numbers. Typically the Cartesian product of an infinite set with itself is bijective with the original set.
mathematical intuition? positive numbers when multiplied together always equal numbers larger than either of the multiplicands...
hardly a rigorous proof, I grant you, but surely true?
hardly a rigorous proof, I grant you, but surely true?
In fact, the opposite of your statement is true: Assuming the axiom of choice, the cardinality of the product X^2 of some infinite set X is always the same as X.
See https://math.stackexchange.com/a/2464655 for a quick proof
See https://math.stackexchange.com/a/2464655 for a quick proof
For me it doesn't make sense that one can be larger than another, infinity is the largest unbounded number, there is always a larger number
very carefully
https://www.oxfordreference.com/display/10.1093/oi/authority...
Cantor and Frege adopted this definition of "the same size as", although already Galileo argued that it would lead to absurd consequences when applied to infinities (there would be as many square numbers as natural numbers, even though not all natural numbers are square), which is known as Galileo's Paradox.
For finite numbers any one-to-one correspondence between F and G means that neither can be a proper subset of the other, which seems just as plausible a requirement for "the same size as" as the former. Since the two requirements come apart for infinite sets, it is unclear which to keep, or whether size comparisons even make any sense for infinities. Galileo concludes they don't make sense.
Hume's Principle is actually not uncontroversial among philosophers of mathematics, but many people treat it as some kind of objective fact rather than a proposed conceptual analysis of "the same size as".