Mountain Math Software

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.

$\begin{displaymath}z+n, z\times n, z^n, z^{n^n}, z^{n^{n^n}}, z^{n^{n^{n^n}}} \ldots \end{displaymath}$

Figure 6.2 plots the first four of these functions with . 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,

$\begin{displaymath}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\end{displaymath}$

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 there is some integer such that all programs with Gödel number less than that halt will do so in time steps. can be the longest time to halt for programs with Gödel number less than . If we had a function 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.

The axiom of replacement supports complex iteration schemes and does not seem to lead to contradictions. But there are more general iteration schemes, that require concepts that seem to far removed from the universe of computer programs. By allowing quantification over the reals, one can ask questions about all possible paths in a branching tree. This is a very powerful concept that allows extremely complex iteration. The real numbers would seem to take us beyond the mathematics of finite computers. However it is the fate of computers following paths in a branching tree that are central to the mathematics of the reals.

**Figure 6.2:** Functions that grow rapidly
$\includegraphics[scale = .7]{../big}$ Plot of , $y=2\times x$ , and $y=2^{x^x}$ .

PDF version of this book

Next: Searching all possible paths Up: Creative mathematics Previous: Axiom scheme of replacement Contents

Mountain Math Software

Email comments to: webmaster@mtnmath.com

Ordinal numbers