5 ms·

A similar observation is that there's exactly as many natural numbers [0, 1, 2, 3, ...) as integer numbers (the same, but with negatives: ..., -2, -1, 0, 1, 2,

by t0mek 5y ago

A similar observation is that there's exactly as many natural numbers [0, 1, 2, 3, ...) as integer numbers (the same, but with negatives: ..., -2, -1, 0, 1, 2, ...). Normally we'd need to count things to say there's "as many" X as Y. But with infinities counting is a bit tricky. So, is the infinite count of natural numbers the same kind of infinity as count for integer numbers? To check this, we need to see if for every number in one set we can assign exactly one number in the other set (and the other way around). It's actually pretty simple: 0 -> 0 1 -> -1 2 -> 1 3 -> -2 4 -> 2 5 -> -3 6 -> 3 ... Since this mapping ("bijective function") exists, we know that every number in one set has exactly one representative in the other set - so the set counts are identical. What's interesting, if we look into real numbers (think: double in C, but without problems with approximation), there's much, much more of them. The infinite count of real numbers is much larger than the infinite count of integers. But let's keep it for another comment.

jodrellblank 5y ago
> "The infinite count of real numbers is much larger than the infinite count of integers. But let's keep it for another comment." That is, beautifully, Cantor's diagonal argument, which goes: write some decimal numbers between two integers 0 and 1: 0.111 0.222 0.333 Now work diagonally through the digits: 0.[1] 1 1 0. 2 [2] 2 0. 3 3 [3] and change those selected ones to other digits: 0.[2] 1 1 0. 2 [3] 2 0. 3 3 [4] And pull those diagonals out into their own new number 0.[2][3][4] or 0.234, and add that in to the list: 0.111 0.222 0.234 <- new number 0.333 That number differs from the first entry in the first decimal position, from the second number in the second position, from the third number in the third position, ... and the Nth number in the Nth position, because those are the positions you changed in each one to make sure of it. If it's different from every existing decimal in at least the one place, it cannot be a duplicate entry seen before in the list you wrote down, it must be a new entry. You can always change the first number in the first position because there's only a single digit there and nine more to choose from. You can always change the Nth number in the Nth position because 0.2 is really 0.20000000... so changing 0.2 in the 5th decimal place makes 0.2 into 0.20007 or etc. This makes the decimals longer, sub-dividing into increasingly tiny pieces, without end - infinitely. Therefore with an infinity of integers, you can subdivide infinitely between any two of them. You can take your infinite list of decimals between 0 and 1 and map the integers to them, 1 for the first entry, 2 for the second, 3 for the third, and pair up both infinities 1:1. And then have no integers leftover to map onto the infinity of decimals between 2 and 3, and again none left over for the decimals between 3 and 4, etc. Conclusion: there are infinite integers, and infinite decimals, and there are more decimals than integers. The infinity of decimals is the larger infinity. (Which makes some intuitive sense looking at single digit integers 0-9 on the left of a decimal point, fan-out to single digit 0-9 for each of those on the right of the decimal point. 10× more 2-digit decimals than 1-digit integers (of course). Infinite permutations of digits on the left of the decimal point, an infinite permutation of digits on the right for each starting permutation on the left, means infinity× more decimals than integers). [ I wrote this more for the practise of pulling it out of memory and going over it, because doing that cements it more in my memory. It is one of the few bits of math I can more or less remember. It would surely be more beneficial and correct for you to read it elsewhere. This is the paradox of internet comments written for the author, not the reader. ]
- thethimble 5y ago
  I’ve always been severely dissatisfied with this argument. It feels like a sleight of hand as opposed to something profound. Are there any other roads to “sizes of infinity” that are more palatable than the diagonalization argument?
  - morelisp 5y ago
    Do you also see the First Incompleteness Theorem, or Halting Problem, as sleights of hand? Informally, the answer to your question is no - the Schröder-Bernstein theorem, which lets us order the size of sets, is sufficient to derive the law of the excluded middle. Therefore if you don't like the "trick" i.e. proof by contradiction (even given the contradiction is "actually constructed" in this case), and instead demand constructive mathematics, you will not be able to say much about relative cardinality.
morelisp 5y ago
> The infinite count of real numbers is much larger than the infinite count of integers. "Much larger," or just barely, the smallest possible amount, larger? :)
- hnfong 5y ago
  I suppose both, assuming size of real numbers is indeed larger.

by t0mek 5y ago

jodrellblank 5y ago

> "The infinite count of real numbers is much larger than the infinite count of integers. But let's keep it for another comment." That is, beautifully, Cantor's diagonal argument, which goes: write some decimal numbers between two integers 0 and 1: 0.111 0.222 0.333 Now work diagonally through the digits: 0.[1] 1 1 0. 2 [2] 2 0. 3 3 [3] and change those selected ones to other digits: 0.[2] 1 1 0. 2 [3] 2 0. 3 3 [4] And pull those diagonals out into their own new number 0.[2][3][4] or 0.234, and add that in to the list: 0.111 0.222 0.234 <- new number 0.333 That number differs from the first entry in the first decimal position, from the second number in the second position, from the third number in the third position, ... and the Nth number in the Nth position, because those are the positions you changed in each one to make sure of it. If it's different from every existing decimal in at least the one place, it cannot be a duplicate entry seen before in the list you wrote down, it must be a new entry. You can always change the first number in the first position because there's only a single digit there and nine more to choose from. You can always change the Nth number in the Nth position because 0.2 is really 0.20000000... so changing 0.2 in the 5th decimal place makes 0.2 into 0.20007 or etc. This makes the decimals longer, sub-dividing into increasingly tiny pieces, without end - infinitely. Therefore with an infinity of integers, you can subdivide infinitely between any two of them. You can take your infinite list of decimals between 0 and 1 and map the integers to them, 1 for the first entry, 2 for the second, 3 for the third, and pair up both infinities 1:1. And then have no integers leftover to map onto the infinity of decimals between 2 and 3, and again none left over for the decimals between 3 and 4, etc. Conclusion: there are infinite integers, and infinite decimals, and there are more decimals than integers. The infinity of decimals is the larger infinity. (Which makes some intuitive sense looking at single digit integers 0-9 on the left of a decimal point, fan-out to single digit 0-9 for each of those on the right of the decimal point. 10× more 2-digit decimals than 1-digit integers (of course). Infinite permutations of digits on the left of the decimal point, an infinite permutation of digits on the right for each starting permutation on the left, means infinity× more decimals than integers). [ I wrote this more for the practise of pulling it out of memory and going over it, because doing that cements it more in my memory. It is one of the few bits of math I can more or less remember. It would surely be more beneficial and correct for you to read it elsewhere. This is the paradox of internet comments written for the author, not the reader. ]

thethimble 5y ago
I’ve always been severely dissatisfied with this argument. It feels like a sleight of hand as opposed to something profound. Are there any other roads to “sizes of infinity” that are more palatable than the diagonalization argument?
- morelisp 5y ago
  Do you also see the First Incompleteness Theorem, or Halting Problem, as sleights of hand? Informally, the answer to your question is no - the Schröder-Bernstein theorem, which lets us order the size of sets, is sufficient to derive the law of the excluded middle. Therefore if you don't like the "trick" i.e. proof by contradiction (even given the contradiction is "actually constructed" in this case), and instead demand constructive mathematics, you will not be able to say much about relative cardinality.

morelisp 5y ago

> The infinite count of real numbers is much larger than the infinite count of integers. "Much larger," or just barely, the smallest possible amount, larger? :)

hnfong 5y ago
I suppose both, assuming size of real numbers is indeed larger.