• 0 Posts
  • 13 Comments
Joined 1 year ago
cake
Cake day: June 20th, 2023

help-circle








  • This is a common one, but the cardinality of infinite sets. Some infinities are larger than others.

    The natural numbers are countably infinite, and any set that has a one-to-one mapping to the natural numbers is also countably infinite. So that means the set of all even natural numbers is the same size as the natural numbers, because we can map 0 > 0, 1 > 2, 2 > 4, 3 > 6, etc.

    But that suggests we can also map a set that seems larger than the natural numbers to the natural numbers, such as the integers: 0 → 0, 1 → 1, 2 → –1, 3 → 2, 4 → –2, etc. In fact, we can even map pairs of integers to natural numbers, and because rational numbers can be represented in terms of pairs of numbers, their cardinality is that of the natural numbers. Even though the cardinality of the rationals is identical to that of the integers, the rationals are still dense, which means that between any two rational numbers we can find another one. The integers do not have this property.

    But if we try to do this with real numbers, even a limited subset such as the real numbers between 0 and 1, it is impossible to perform this mapping. If you attempted to enumerate all of the real numbers between 0 and 1 as infinitely long decimals, you could always construct a number that was not present in the original enumeration by going through each element in order and appending a digit that did not match a decimal digit in the referenced element. This is Cantor’s diagonal argument, which implies that the cardinality of the real numbers is strictly greater than that of the rationals.

    The best part of this is that it is possible to construct a set that has the same cardinality as the real numbers but is not dense, such as the Cantor set.