3 ms·

What is missing from this discussion of infinity is the notion that there are multiple infinities that are different from each other. The integers (like the ho

by dxjones 17y ago

What is missing from this discussion of infinity is the notion that there are multiple infinities that are different from each other. The integers (like the hotel rooms) are countably infinite. There are only a FINITE number of integers (or hotel rooms) between any two integers (rooms), like between rooms 1 and 100. The set of real numbers is a larger set than the integers. Both are infinitely large, but the real numbers are a larger infinity. Between any two real numbers, (even 0 and 1), there is still an INFINITE number of real numbers in between. The notion of a hierarchy of infinities initially seems paradoxical, but once you know how to distinguish countably infinite from uncountably infinite, you have the key concept.

mojuba 17y ago
So what does it explain in this context?
drbaskin 17y ago
The reals and the integers do have different cardinalities, but not for the reason you imply. In fact, the rational numbers have the same cardinality (the same infinity) as the integers, but they have the same property that you use to characterize the reals, i.e., that between any two distinct rationals there is an infinite number of rationals. One way to see that there are as many integers as there are rational numbers is just to find a way to count the rational numbers. There are a number of ways to do this. There is a very nice and explicit way to do enumerate the positive rationals that involves the prime factorization of the integers. Suppose first that p is a prime number. We identify p^k with the integer p^{2k}. For the rational number 1/p^k (p is still prime), we label it by the integer p^{2k-1}. For a rational number p/q in lowest terms, we take the prime factorization of p and the prime factorization of q, apply the above identification to each factor p_i ^k and then take the product. This gives a very explicit bijection between the positive rationals and the positive integers.with My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok.
- slackenerny 17y ago
  My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok. Calkin and Wilf cleverly avoid duplications by arranging reals not on a lattice but on a (Stern-Borcot) tree. http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://www.mathlesstraveled.com/?p=94 http://www.mathlesstraveled.com/?p=94
- mnemonicsloth 17y ago
  My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok. Or just enumerate the naturals in base 11. Denote 9+1 by "/". Interpret "/" as a negative sign when it's the first or last base-10 digit, otherwise as division. Pick an associativity.
  - slackenerny 17y ago
    Oh, that's really nifty. I first got embarassed by not knowing of that direct way here: http://gowers.wordpress.com/2008/07/30/recognising-countable-sets/ http://gowers.wordpress.com/2008/07/30/recognising-countable...

by dxjones 17y ago

mojuba 17y ago

So what does it explain in this context?

drbaskin 17y ago

The reals and the integers do have different cardinalities, but not for the reason you imply. In fact, the rational numbers have the same cardinality (the same infinity) as the integers, but they have the same property that you use to characterize the reals, i.e., that between any two distinct rationals there is an infinite number of rationals. One way to see that there are as many integers as there are rational numbers is just to find a way to count the rational numbers. There are a number of ways to do this. There is a very nice and explicit way to do enumerate the positive rationals that involves the prime factorization of the integers. Suppose first that p is a prime number. We identify p^k with the integer p^{2k}. For the rational number 1/p^k (p is still prime), we label it by the integer p^{2k-1}. For a rational number p/q in lowest terms, we take the prime factorization of p and the prime factorization of q, apply the above identification to each factor p_i ^k and then take the product. This gives a very explicit bijection between the positive rationals and the positive integers.with My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok.

slackenerny 17y ago
My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok. Calkin and Wilf cleverly avoid duplications by arranging reals not on a lattice but on a (Stern-Borcot) tree. http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree http://www.mathlesstraveled.com/?p=94 http://www.mathlesstraveled.com/?p=94
mnemonicsloth 17y ago
My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok. Or just enumerate the naturals in base 11. Denote 9+1 by "/". Interpret "/" as a negative sign when it's the first or last base-10 digit, otherwise as division. Pick an associativity.
- slackenerny 17y ago
  Oh, that's really nifty. I first got embarassed by not knowing of that direct way here: http://gowers.wordpress.com/2008/07/30/recognising-countable-sets/ http://gowers.wordpress.com/2008/07/30/recognising-countable...