PDF version of this book

Ordinal induction

One can move beyond the Arithmetical Hierarchy by interpreting the output of a computer program in different ways. For example, one can interpret the output as an integer or as the Gödel number of another program. One could assume an even output is interpreted as an integer and an odd output is interpreted as a program's Gödel number. After deciding how an output is to be interpreted, it can be divided by 2 so every integer and every Gödel number is a possible result.

Using this convention one can define an $n$-tree. An output is called $0$-tree if it is to be interpreted as an integer. An output is an $n$-tree if it is interpreted as the Gödel number of a computer program with the following property. When the program is executed it has an infinite number of outputs and an infinite subset of these are $(n-1)$-trees. A $1$-tree must have an infinite number of integer outputs. A $2$-tree must have an infinite number of outputs an infinite subset of these must represent computer programs that generate an infinite number of integer outputs.

With this property one can define sets that are not in the Arithmetical Hierarchy. Consider the question does a computer program have an output that is at least $n$-tree for all integers $n$. That is, for every $n$, is there at least one output that is an $m$-tree where $m\geq n$. I call this an $\omega$-tree. This is no finite logical expression, limited to quantifiers over the integers, that can define this set. It is the self referencing structure of this definition that cannot be captured by the expressions that define the Arithmetical Hierarchy. This property can be defined in the Hyperarithmetical Hierarchy. New `successor' levels in this new hierarchy can be created in the same way the Arithmetical Hierarchy is built up. To go to the next level one asks if a program has an infinite number of outputs of the previous level. One 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.

Solving problems in the Arithmetical and Hyperarithmetical hierarchies requires ordinal induction which is a generalization of 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 ordinals are will ordered by the $\in$ relationship. For any two ordinals $a$ and $b$ either $a \in b$ or $b \in a$ or $a = b$.

The integers have both of these properties and are the finite ordinals. 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 6.1. Ordinal induction is completely general. There is no higher level scheme of induction. It obtains this generality by making ordinal number an open ended concept. The difficulty in increasing the power of a mathematical system to solve problems is the construction of ever larger ordinal numbers. The first tool for defining large ordinals in standard set theory is the axiom of replacement.

Figure 6.1: Induction on the integers and ordinals

PDF version of this book