PDF version
of this book

**Next:** Axiom scheme of replacement **Up:** Creative
mathematics **Previous:** Arithmetical Hierarchy
**Contents**

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 -tree. An output is called -tree if it is to be interpreted as an integer. An output is an -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 -trees. A -tree must have an infinite number of integer outputs. A -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 -tree for all
integers . That is, for every , is there
at least one output that is an -tree where
. I call this an -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 relationship. A
set is transitive if every *member of a
member* of a set belongs to the set. A set
is well ordered if, for every two elements
and of ,
either or or
. Such a set is also said to be linearly
ordered. The ordinals are will ordered by the
relationship. For any two ordinals
and either or or .

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

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.

PDF version
of this book

**Next:** Axiom scheme of replacement **Up:** Creative
mathematics **Previous:** Arithmetical Hierarchy
**Contents**

home | consulting | videos | book | QM FAQ | contact |