Beyond infinity

In the Disney/Pixar film Toy Story, one of the lead characters likes to use the catchphrase "To infinity and beyond!" But what is beyond infinity? As a child, we seem to believe that there are things beyond infinity, especially when we are comparing, i.e. "my toy car is infinity times faster than your car.", "no, my car is infinity plus one times faster.", etc.

In a branch of mathematics called Set Theory, an effort is made to count beyond infinity. First numbers are associated with sets. The number 5 is associated with a set of 5 items. Then a number is larger than, equal to or smaller than another number if the corresponding sets have more items, the same number of items or have less items. One of the consequences of counting this way is that we can extend it to infinite numbers. How do we count whether two sets of objects are of equal size or not? Two sets are of the same size if we can associate each member of the first set with exactly one member of the second set and every member of the second set is associated to some member of the first set. Such a mapping is called a bijection. A map which assigns to a member of a first set exactly one member of the second set is called an injection. A famous result known as the Cantor-Bernstein theorem states that a bijection between two sets exists if and only if there is an injection from the first set to the second set and an injection from the second set to the first set.

With this definition, Cantor shows that the set of even integers is the same size as the set of all integers: just assign each integer n to the number 2n. Intuitively this is strange since the set of even integers is a strict subset of the set of integers.  What is more remarkable is that the set of rational numbers p/q where p and q are integers is also the same size as the set of integers, even though there are infinitely number of rational numbers between any two integers. This infinity is denoted as Aleph-zero. So in this context the child's argument of saying "infinity plus 1" is really not any bigger than "infinity".

So are all infinite sets of the same size? Cantor showed using a diagonalization argument that the set of real numbers is strictly larger than Aleph-zero. In fact, given any set, infinite or not, the power set, i.e. the set of all subsets, is strictly larger. Thus for any infinite set, we can create one that is strictly larger. For a finite set of size n, the power set has 2ⁿ elements. For instance, the set {1,2,3} has as its power set {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} with 8 elements. Analogously, the size of the power set of Aleph-zero is denoted as 2^Aleph-zero and is the size of the set of real numbers. The Continuum Hypothesis states that the next strictly larger infinity beyond Aleph-zero is equal to 2^Aleph-zero. It was shown in 1963 by Cohen that this hypothesis is not provable using the assumptions (axioms) of standard set theory.

All this talk about infinity might seem abstract, but it did find its way into the foundation of computer science. In fact, the same diagonalization argument that Cantor used to show that the real numbers is "more infinite" than the integers is used by Turing to show that there are problems that are uncomputable, i.e. there does not exists a computer algorithm that can solve this problem. A famous uncomputable problem is the halting problem: given a computer program with a given input, determine whether it will ever end executing or not.