Completed second draft of this book

PDF version of this book

Ordinal numbers

One way to construct ordinals is through ordinal arithmetic. This is similar to arithmetic on the integers. $\omega + \omega$ or $2\times \omega$ is the infinite successor to $\omega$ just as $\omega$ is the infinite successor to 0.

Consider the ordinal sequence $\omega$, $\omega\times\omega$, $\omega\times\omega\times\omega$, $\ldots$. This leads to $\omega^\omega$. Then comes the series $\omega^\omega$, $\omega^{\omega^\omega}$, $\omega^{\omega^{\omega^\omega}}$, $\omega^{\omega^{\omega^{\omega^\omega}}}$, $\ldots$. The limit of this sequence is the first ordinal that is not primitive recursive. Loosely speaking at cannot be obtained by simply iterating, iterating iteration etc. It contains all the iteration schemes one can generate in that way. To get this ordinal you need to introduce a higher level of abstraction. You need to view the process of generating iteration schemes as something that itself can be iterated.

There is a correspondence between the hierarchy of ordinal arithmetic and functions on the integers that increase more rapidly. Compare members in the following sequence.

$$z+n, z\times n, z^n, z^{n^n}, z^{n^{n^n}}, z^{n^{n^{n^n}}} \ldots$$

Figure 4.2 plots the first four of these functions with $z=2$. More complex iteration generates functions that increase more rapidly. The complexity comes from abstracting and generalizing forms of iteration. Addition is iteration of successor. Multiplication is iteration of addition. With multiplication as a base, each level of the exponential hierarchy is iteration of the previous level. One can generalize from the entire exponential hierarchy to create a function that is not in the exponential hierarchy and grows faster than any exponential function. One such function is defined as follows,

$$B(0) = 1, B(1) = 1, B(2) = 2^{2^2}, B(3) = 3^{3^{3^3}} B(4) = 4^{4^{4^{4^4}}} \ldots$$

The idea of the axiom of replacement defined in Section 4.3 is to allow as powerful a process of iteration, abstraction and diagonalization as possible without creating contradictions like the barber paradox.

The Halting Problem could be solved with a function that increased rapidly enough. Assume a specific Gödel numbering of computer programs. For any integer $n$ there is some integer $m$ such that all programs with Gödel number less than $n$ that halt will do so in $m$ time steps. $m$ can be the longest time to halt for programs with Gödel number less than $n$. If we had a function $m(n)$ that could tell us how long to wait we could solve the halting problem. Any function equal to or uniformly larger than this function will do. There is such a function that will solve problems at every level in the Arithmetical and Hyperarithmetical hierarchies.

Figure 4.2: Functions that grow rapidly

Plot of $y=2+x$, $y=2\times x$, $y=2^x$ and $y=2^{x^x}$.

Completed second draft of this book

PDF version of this book