Continuum and cardinality

Some notion of a distinction between continuous and discrete systems has existed since antiquity. But in the 1870s the distinction became more precise with Georg Cantor's characterization of the total numbers of possible objects of various types in terms of different orders of infinity (see page 1162). The total number of possible integers corresponds to the smallest level of infinity, usually denoted ℵ₀. The total number of possible lists of integers of given finite length—and thus the number of possible rational numbers—turns out also to be ℵ₀. The reason is that it is always possible to encode any finite list of integers as a single integer, as discussed on page 1120. (A way to do this for pairs of non-negative integers is to use σ[{x_, y_}] := 1/2(x + y)(x + y + 1) + x.) But for real numbers the story is different. Any real number x can be represented as a set of integers using for example

Rest[FoldList[Plus, 1, ContinuedFraction[x]]]

but except when x is rational this list is not finite. Since the number of possible subsets of a set with k elements is 2^k, the number of possible real numbers is 2^ℵ₀. And using Cantor's diagonal argument (see note below) one can then show that this must be larger than ℵ₀. (The claim that there are no sets intermediate in size between ℵ₀ and 2^ℵ₀ is the so-called continuum hypothesis, which is known to be independent of the standard axioms of set theory, as discussed on page 1155.) Much as for integers, finite lists of real numbers can be encoded as single real numbers—using for example roughly FromDigits[Flatten[Transpose[RealDigits[list]]]]—so that the number of such lists is 2^ℵ₀. (Space-filling curves yield a more continuous version of such an encoding.) But unlike for integers the same turns out to be true even for infinite lists of real numbers. (The function σ above can for example be used to specify the order in which to sample elements in RealDigits[list]). The total number of possible functions of real numbers is 2^2ℵ₀; the number of continuous such functions (which can always be represented by a list of coefficients for a series) is however only 2^ℵ₀.

In systems like cellular automata, finite arrangements of black cells on a background of white cells can readily be specified by single integers, so the number of them is ℵ₀. But infinite configurations of cells are like digit sequences of real numbers (as discussed on page 869 they correspond more precisely to elements in a Cantor set), so the number of them is 2^ℵ₀. Continuous cellular automata (see page 155) also have 2^ℵ₀ possible states.