We all know that the cardinality of the set of all integers is countably infinite. To me, it seems unfair that the cardinality of the set of real numbers is uncoutably infinite. It also seems odd that it is unintuitive to most (including me). However, I now understand why it was unintuitive to me. The key point to remember is that mathematicians don't allow integers to have an infinite number of digits. Instead, you can increase the integer by 1, but at any given time it has a fixed number of digits. However, with real numbers, there can, and often does, exist an infinity of digits. For instance, 1/3 is 0.333333.... So, not only do the real numbers extend countably to infinity, they also can have an infinite number of digits. In essence, they are infinite in 2 dimensions, whereas integers are only infinite in 1 dimension. I would imagine that complex numbers will one day be proven to be infinite in 3 dimensions, but who knows.

To be honest, I think it is a bit silly. We're not actually talking about different orders of infinities here, we're only talking about the existence of a function M that will map from one infinite set to another. If we can find that function, then we say the sets have an equivalent cardinality. Otherwise, the cardinality of one set is said to be greater than the cardinality of the other. If we could extract M from mathematics, and instead use an algorithm, then M could simply be, pick a real number, get next biggest integer, rinse, repeat. However, algorithms are not yet mathematical (unless you're Stephen Wolfram).

ICFP Programming Contest 2018

1 day ago

## 2 comments:

The "one dimension" versus "two dimension" explanation simply doesn't work. To illustrate that fact, the rational numbers (all numbers that can be expressed as a ratio) are also a countably infinite set, even though (1)there are two degrees of freedom and (a ratio is stated in terms of two integers), and (2) infinitely many rational numbers have fractional expansions requiring infinitely many dimensions (e.g. 1/3 in decimal).

To see that the rational numbers are countable, arrange pairs of positive integers first in order by their sum, and then in order by their first term. This gives:

(1,1), (1,2), (2,1), (1,3), (2,3), (3,3), ...

This sequence is clearly countable, as it has a well-defined order and every pair of positive integers will occur eventually (in fact, a simple polynomial formula on the two integers gives its position in the list). To deal with the negative rationals, interleave the above with a similar list where the first term is negated:

(1,1), (-1,1), (1,2), (-1,2), (2,2), (-2,2), ...

Clearly the second list (the one with the negative left-hand values) is also countable, and the union of two countable sets is countable.

Interesting, so the only reason the real numbers are uncountable is because they have an infinite number of digits? That seems a little unfair and arbitrary, but I can see that.

Post a Comment