Many eons ago when I was in college, I worked with a guy who was a math major. He was a bit of a show boat know it all and I honestly think he believed that he was never wrong. This post reminded me of him because he and I had a debate / discussion on this topic and I came away from that feeling like he he was right and I was too dumb to understand why he was right.
He was arguing that if two sets are both infinite, then they are the same size (i.e. infinity, infinite). From a strictly logical perspective, it seemed to me that even if two sets were infinite, it seems like one could still be larger than the other (or maybe the better way of phrasing it was that one grew faster than the other) and I used the example of even integers versus all integers. He called me an idiot and honestly, I’ve always just assumed I was wrong – he was a math major at a mid-ranked state school after all, how could he be wrong?
Hilbert’s Paradox of the Grand Hotel seems to be the thought experiment with which you were engaged with your math associate. There are countable and uncountable infinities. Integers and skip counted integers are both countable and infinite. Real numbers are uncountable and infinite. There are sets that are more uncountable than others. That uncountability is denoted by aleph number. Uncountable means can’t be mapped to the natural numbers (1, 2, 3…). Infinite means a list with all the elements can’t be created.
Two sets with infinitely many things are the same size when you can describe a one to one mapping from one set to the other.
For example, the counting numbers are the same size as the counting numbers except for 7. To go from the former set to the latter set, we can map 1-6 to themselves, and then for every counting number 7 or larger, add one. To reverse, just do the opposite.
Likewise, we can map the counting numbers to only the even counting numbers by doubling the value or each one as our mapping. There is a first even number, and a 73rd even number, and a 123,456,789,012th even number.
By contrast, imagine I claim to have a map from the counting numbers to all the real numbers between 0 and 1 (including 0 but not 1). You can find a number that isn’t in my mapping. Line all the numbers in my mapping up in the order they map from the counting numbers, so there’s a first real number, a second, a third, and so on. To find a number that doesn’t appear in my mapping anywhere, take the first digit to the right of the decimal from the first number, the second digit from the second number, the third digit from the third number, and so on. Once you have assembled this new (infinitely long) number, change every single digit to something different. You could add 1 to each digit, or change them at random, or anything else.
This new number can’t be the first number in my mapping because the first digit won’t match anymore. Nor can it be the second number, because the second digit doesn’t match the second number. It can’t be the third or the fourth, or any of them, because it is always different somewhere. You may also notice that this isn’t just one number you’ve constructed that isn’t anywhere in the mapping - in fact it’s a whole infinite family of numbers that are still missing, no matter what order I put any of the numbers in, and no matter how clever my mapping seems.
The set of real numbers between 0 and 1 truly is bigger than the set of counting numbers, and it isn’t close, despite both being infinitely large.
It is true! Someone much more studied on this than me could provide a better explanation, but instead of “size” it’s called cardinality. From what I understand your example of even integers versus all integers would still be the same size, since they can both be mapped to the natural numbers and are therefore countable, but something like real numbers would have a higher cardinality than integers, as real numbers are uncountable and infinite. I think you can have different cardinalities within uncountable infinities too, but that’s where my knowledge stops.
In the end it depends on your definition of “bigger”. Traditionally, we use “bigger” to just refer to who has the highest number or count, but neither apply here.
Imagine we have a straight line of skittles. Lines with more are defined as “bigger”. Now imagine the line is expanded into another dimension, a square. Is it still “bigger”? Each line has the same count, so it’s traditional “bigness” value is unchanged…
It’s pretty well settled mathematics that infinities are “the same size” if you can draw any kind of 1-to-1 mapping function between the two sets. If it’s 1-to-1, then every member of set A is paired off with a member of B, and there are no elements left over on either side.
In the example with even integers y versus all integers x, you can define the relation x <–> y = 2*x. So the two sets “have the same size”.
But the real numbers are provably larger than any of the integer sets. Meaning every possible mapping function leaves some reals leftover.
Is this actually true?
Many eons ago when I was in college, I worked with a guy who was a math major. He was a bit of a show boat know it all and I honestly think he believed that he was never wrong. This post reminded me of him because he and I had a debate / discussion on this topic and I came away from that feeling like he he was right and I was too dumb to understand why he was right.
He was arguing that if two sets are both infinite, then they are the same size (i.e. infinity, infinite). From a strictly logical perspective, it seemed to me that even if two sets were infinite, it seems like one could still be larger than the other (or maybe the better way of phrasing it was that one grew faster than the other) and I used the example of even integers versus all integers. He called me an idiot and honestly, I’ve always just assumed I was wrong – he was a math major at a mid-ranked state school after all, how could he be wrong?
Thoughts?
Hilbert’s Paradox of the Grand Hotel seems to be the thought experiment with which you were engaged with your math associate. There are countable and uncountable infinities. Integers and skip counted integers are both countable and infinite. Real numbers are uncountable and infinite. There are sets that are more uncountable than others. That uncountability is denoted by aleph number. Uncountable means can’t be mapped to the natural numbers (1, 2, 3…). Infinite means a list with all the elements can’t be created.
Two sets with infinitely many things are the same size when you can describe a one to one mapping from one set to the other.
For example, the counting numbers are the same size as the counting numbers except for 7. To go from the former set to the latter set, we can map 1-6 to themselves, and then for every counting number 7 or larger, add one. To reverse, just do the opposite.
Likewise, we can map the counting numbers to only the even counting numbers by doubling the value or each one as our mapping. There is a first even number, and a 73rd even number, and a 123,456,789,012th even number.
By contrast, imagine I claim to have a map from the counting numbers to all the real numbers between 0 and 1 (including 0 but not 1). You can find a number that isn’t in my mapping. Line all the numbers in my mapping up in the order they map from the counting numbers, so there’s a first real number, a second, a third, and so on. To find a number that doesn’t appear in my mapping anywhere, take the first digit to the right of the decimal from the first number, the second digit from the second number, the third digit from the third number, and so on. Once you have assembled this new (infinitely long) number, change every single digit to something different. You could add 1 to each digit, or change them at random, or anything else.
This new number can’t be the first number in my mapping because the first digit won’t match anymore. Nor can it be the second number, because the second digit doesn’t match the second number. It can’t be the third or the fourth, or any of them, because it is always different somewhere. You may also notice that this isn’t just one number you’ve constructed that isn’t anywhere in the mapping - in fact it’s a whole infinite family of numbers that are still missing, no matter what order I put any of the numbers in, and no matter how clever my mapping seems.
The set of real numbers between 0 and 1 truly is bigger than the set of counting numbers, and it isn’t close, despite both being infinitely large.
Change the numbers to rubber balls with pictures of ducks or trains and different iconography. You can now intuit that both sets are the same size.
It is true! Someone much more studied on this than me could provide a better explanation, but instead of “size” it’s called cardinality. From what I understand your example of even integers versus all integers would still be the same size, since they can both be mapped to the natural numbers and are therefore countable, but something like real numbers would have a higher cardinality than integers, as real numbers are uncountable and infinite. I think you can have different cardinalities within uncountable infinities too, but that’s where my knowledge stops.
In the end it depends on your definition of “bigger”. Traditionally, we use “bigger” to just refer to who has the highest number or count, but neither apply here.
Imagine we have a straight line of skittles. Lines with more are defined as “bigger”. Now imagine the line is expanded into another dimension, a square. Is it still “bigger”? Each line has the same count, so it’s traditional “bigness” value is unchanged…
The sizes of infinities are about set theory, and including more “dimensions” of number. Not really about which has “more” or “grows faster”. Your even v all integers is actually a classic example of two same-size infinities E.g. an infinite stack of one dollar bills and one of ten dollar bills are worth the same
It’s pretty well settled mathematics that infinities are “the same size” if you can draw any kind of 1-to-1 mapping function between the two sets. If it’s 1-to-1, then every member of set A is paired off with a member of B, and there are no elements left over on either side.
In the example with even integers y versus all integers x, you can define the relation x <–> y = 2*x. So the two sets “have the same size”.
But the real numbers are provably larger than any of the integer sets. Meaning every possible mapping function leaves some reals leftover.
I side with you, though the experts call me stupid for it too.
if for all n < infinity, one set is double the size of another then it is still double the size at n = infinity.
You’re not stupid for it. Since it makes sense.
However, due to the way we “calculate” the sizes of infinite sets, you are wrong.
Even integers and all integers are the same infinity.
But reals are “bigger” than integers.