Completed second draft of this book

PDF version of this book

Ordinal induction

One can move beyond the Arithmetical Hierarchy by allowing a computer program to specify which of its outputs are to be interpreted as computer programs and which are terminal and treated as integers. One way to do this is to assume an even output is terminal and an odd output is a program's Gödel number. After deciding how it is to be interpreted we can divide the output by 2 so the program can still generate every Gödel number or integer.

To use this property we define an $n$-tree. An output is $0$-tree if it is to be interpreted as an integer. It is $n$-tree if it has an infinite number of outputs that are $(n-1)$-tree. A $1$-tree must have an infinite number of integer outputs. A $2$-tree must have an infinite number of nonterminal outputs an infinite subset of these must have an infinite number of integer outputs.

With this property we can ask questions that cannot be formulated in the Arithmetical Hierarchy. For example we can ask if a computer program has an output that is at least $n$-tree for all integers $n$. We call this an $\omega$-tree. With this question we enter the Hyperarithmetical Hierarchy. we can create new levels in this hierarchy just as we created new levels in the Arithmetical Hierarchy. We ask if a program has an infinite number of outputs of the previous type. We can also create new limit levels by asking if a computer program has outputs that span some infinite sequence of lower levels as we just did to move beyond the Arithmetical Hierarchy.

The idea of infinite trees like those definable with the property of $n$-tree is central to extending mathematics. At the core of this mathematics is ordinal induction which generalizes induction on the integers. Ordinals are defined by two properties. They are transitive and they are well ordered by the `$\in$' relationship. A set is transitive if every member of a member of a set belongs to the set. A set $S$ is well ordered if for every two elements $a$ and $b$ of $S$ either $a > b$ or $a < b$ or $a = b$. Such a set is also said to be linearly ordered.

The integers have both of these properties. The ordinals generalize the integers into the transfinite. $\omega$ is the smallest infinite ordinal. The next ordinal contains $\omega$ and all the elements of $\omega$.

Induction on the integers and ordinal induction are compared in Figure 4.1. Ordinal induction is completely general. There is no higher level scheme of induction. It obtains this generality by making oridnal number an open ended concept. The difficulty in moving up the hierarchy of solvability in mathematics is in constructing ever larger ordinal numbers. It is the structure of the ordinals in a system that determines its power. To define large ordinals on which we can apply oridnal induction we need the axiom scheme of replacement.

Figure 4.1: Induction on the integers and ordinals

Completed second draft of this book

PDF version of this book