Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations

Transfinite numbers

For most mathematical purposes it is quite adequate just to have a single notion of infinity, usually denoted . But as Georg Cantor began to emphasize in the 1870s, it is possible to distinguish different levels of infinity. Most of the details of this have not been widely used in typical mathematics, but they can be helpful in studying foundational issues. Cantor's theory of ordinal numbers is based on the idea that every integer must have a successor. The next integer after all of the ordinary ones—the first infinite integer—is given the name ω. In Cantor's theory ω+1 is still larger (though 1 + ω is not), as are , ω^2 and ω^ω. Any arithmetic expression involving ω specifies an ordinal number—and can be thought of as corresponding to a set containing all integers up to that number. The ordinary axioms of arithmetic do not apply, but there are still fairly straightforward rules for manipulating such expressions. In general there are many different expressions that correspond to a given number, though there is always a unique Cantor normal form—essentially a finite sequence of digits giving coefficients of descending powers of ω. However, not all infinite integers can be represented in this way. The first one that cannot is ε0, given by the limit ω^ω^ω^..., or effectively Nest[ω^#&, ω, ω]. ε0 is the smallest solution to ω^ε == ε. Subsequent solutions (Subscript[ε, 1], ..., εω, ..., Subscript[ε, ε0], ...) define larger ordinals, and one can go on until one reaches the limit Subscript[ε, Subscript[ε, Subscript[ε, ...]]], which is the first solution to εα == α. Giving this ordinal a name, one can then go on again, until eventually one reaches another limit. And it turns out that in general one in effect has to introduce an infinite sequence of names in order to be able to specify all transfinite integers. (Naming a single largest or "absolutely infinite" integer is never consistent, since one can always then talk about its successor.) As Cantor noted, however, even this only allows one to reach the lowest class of transfinite numbers—in effect those corresponding to sets whose size corresponds to the cardinal number Aleph0. Yet as discussed on page 1127, one can also consider larger cardinal numbers, such as Aleph1, considered in connection with the number of real numbers, and so on. And at least for a while the ordinary axioms of set theory can be used to study the sets that arise.

From Stephen Wolfram: A New Kind of Science [citation]