Representing Infinities

Computers oftentimes deal with infinity, whether it be pushing the limits of hardware, optimization, or reasonableness. There are many interesting ways to frame the idea. In school you learned about the sets of counting numbers, integers, and rationals. Each number system contains the previous as:  ⊂  ⊂ . But these are all essentially equally countable sets of numbers.

Consider the set of even numbers E and the set of odd numbers O. Both have the same cardinality, or size, right? You can use a formula to map every element in E to exactly one element in O. (e.g., 0→1, 2→3, 4→5, etc.) without having extras or leaving out elements. Likewise, you can map one set of numbers from  to another set of numbers from , as with 1→3, 2→4, 3→5, etc., where the second set does not include the elements {1, 2}. Because the mapping is consistent, both sets have the same cardinality, ‎ℵ0 (pronounced “aleph naught” or “aleph null”). This is countable infinity, the smallest kind of infinity.

Infinities are not something we can innately observe; the universe may go on forever, but there are bounds on what we can see and do. Zeno’s Paradox states that motion is impossible because we have to travel over infinitely small distances to get anywhere, but atoms are discrete entities that don’t come close to being infinitely small, so we can move over those distances over a finite time frame.

David Hilbert’s idea of a hotel with countably infinite rooms may reframe our look at number sequences to better show how they apply to computing. If this hypothetical hotel were fully booked, then the set of rooms R could have a corresponding set of customers C mapped to it as 1→1, 2→2, 3→3, etc. Both C and R have cardinality ‎ℵ0. If two additional people each want rooms, the fact that there are no vacancies doesn’t stop the front desk from making room for them. By asking the customers to move from their room n to room n+2, they remap C to R as 1→3, 2→4, 3→5, etc., making the rooms 1 and 2 available. There is no room numbered ∞ where this mapping stops. It just keeps on going…

What if instead of two people demanding rooms in the fully booked infinite hotel, there was an infinite bus full of a set of people P each demanding a room? Well, we now know that ∞+2=∞, so why not try ∞2=∞? Mapping C to R through 1→2, 2→4, 3→6, etc., makes room in all of the odd-numbered rooms for the elements of P. If there were n buses each with infinite passengers, then the mapping of C is 1→2n, 2→3n, 3→4n, etc. and the mapping of each bus Pn (i.e., P1, P2, etc.) is 1→n, 2→2n+1, 3→3n+2, 4→4n+3, 5→5n+4, etc.

Now what if there were instead an infinite number of infinite buses B each filled with an infinite amount of people demanding rooms in this infinite hotel? What can you do?

The counting numbers , integers , and rationals  are all bounded by the same infinity, ℵ‎0, because just as you can reach infinity in counting all the positive numbers, they can be systematically mapped to all the integers as 0→0, 1→1, 2→-1, 3→2, 4→-2, etc. Likewise,  maps to  through visualizing a table of all fractions with the numerators incrementing over the columns and the denominators incrementing over the rows.

Make a “Dedekind” cut along the rational number line and define even more numbers that are irrational because they fall just between the cut and the next rational. For example, the Dedekind cut between numbers n such that n2<=2 and n2>2 marks the upper boundary of the rationals just below s2, so s2 is included along with infinitely many other real numbers in , a set of cardinality ‎ℵ1.

Cantor’s Diagonal argument