Computers can oftentimes be thought of as dealing with infinity, whether it be pushing the limits of hardware, optimization, or reasonableness. There are many interesting ways to frame the idea, but here we’ll discuss *sets*. In school, you learned about the set of natural (counting) numbers, the set of integers (positive and negative numbers and zero), and the set of rational numbers (fractions or decimals). The sets are all infinite, but the infinity that represents the naturals (ℕ) is the same as the one that represents the integers (ℤ), which is the same as the one that represents the rationals (ℚ). Even though each number system contains the previous one (ℕ ⊆ ℤ ⊆ ℚ), these all have the same size, or cardinality, of infinity.

Consider the set of even numbers **E** and the set of odd numbers **O**. Both have the same cardinality, right? You can use a function 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 at scales large and small, 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. He argues that in order to travel a meter, you first have to travel half a meter, and in order to travel half a meter, you have to travel a quarter of a meter, and etc. But since atoms are discrete entities that don’t come close to being infinitely small, we actually *can* move over those distances over a finite timeframe by ‘jumping over’ Zeno’s infinitesimal singularities.

The counting numbers **ℕ**, integers **ℤ**, and rationals **ℚ** are all bounded by the same infinity, **ℵ**_{0}, because just as you can reach infinity in counting the set of all positive numbers, you can reach it by counting the set of all positive and negative numbers. These sets are the same size because the elements of **ℕ **can be systematically mapped to elements of **ℤ** as 0→0, 1→1, 2→-1, 3→2, 4→-2, etc. There may be twice as many integers, but for every one, there is exactly one counting number, so really the sets are the same size of infinity. Essentially, ∞+∞=∞.

Likewise, **ℕ** maps to **ℚ** through the visualization of a table of all fractions with the numerators incrementing over the columns and the denominators incrementing over the rows.

1/1 ① |
2/1 ③ |
3/1 ④ |
4/1 ⑨ |

1/2 ② |
~~2/2~~ |
3/2 ⑧ |
~~4/2~~ |

1/3 ⑤ |
2/3 ⑦ |
~~3/3~~ |
4/3 |

1/4 ⑥ |
~~2/4~~ |
~~3/3~~ |
~~4/4~~ |

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 n^{2}<=2 and n^{2}>2 marks the upper boundary of the rationals just below s^{2}, so s^{2} is included along with infinitely many other real numbers in **ℝ**, a set of cardinality **ℵ**_{1}.

Cantor’s Diagonal argument

Continuum Hypothesis

bijective (injective and surjective)

David Hilbert’s idea of a hotel with countably infinite rooms may reframe our look at number sequences. 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→2*n*, 2→3*n*, 3→4*n*, etc. and the mapping of each bus **P**_{n} (i.e., **P**_{1}, **P**_{2}, 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?