Completed second draft of this book

PDF version of this book

Searching all possible paths

The ordinals and iteration schemes described in the previous section are recursive. Their structure can be described by a nondeterministic computer program like those used in defining an $n$-tree. This suggests that we can define an ordinal that contains all recursive ordinals. Since we can enumerate (or list as outputs of a computer program) the Gödel numbers of all computer programs we should be able to define the ordinal that contains all ordinals whose structure is mirrored by the execution of a computer program. This would be the first non recursive ordinal.

To define the first nonrecursive ordinal we must specify how a computer program mirrors the structure of a recursive ordinal. The idea is that the outputs of the program correspond to the members of the set being represented. Every set except the empty set is represented by a program with at least one output. We can use computer programs with integer outputs. 0 represents the empty set. All other integer outputs are interpreted as Gödel numbers of computer programs. These may or may not have a structure that represents a set. If one of them does not then the program with that output cannot represent a set.

Any sequence of integer outputs generated by a program can be generated by an infinite number of different programs. Sets are uniquely determined by their members but representations for sets are not. To deal with this we will arbitrarily require a unique Gödel number for each set we represent.

A computer outputting notations for the members of an infinite set gives an ordering to the members that is not present in the original set. This can be confusing. For a set like $\omega+1$ the order the notations are output must differ from the ordering of the set members defined by $\in$. The notation for $\omega$ must be output before the notations for most of the elements of $\omega$. Otherwise one would never get around to outputting the notation for $\omega$.

Most computer programs will not represent notations for sets. Most that do represent notations for sets will not represent notations for ordinals. To define which programs represent a set we must define which are well founded. Sets constructed from the axioms of ZF are well founded because they are built up in a finite number of steps from the empty set. A set is well founded if it does not contain an infinite descending chain of members. If you take any member of a set then take any member of that set and keep repeating the process you will reach the empty set in a finite number of steps.

The outputs generated by the nondeterministic execution of a program are structured in a tree. The level of a branch is the number of times we had to execute a new program before getting to this branch. The original program is level 0. Outputs of that program are level 1. Outputs of these programs are at level 2 and they generate outputs at level 3, etc. Each output is a node in the tree that is either another program or the number 0 for the empty set. Each program node may have an infinite number of branches. To select a node or output at the first level requires a single integer. Selecting a second level node requires a pair of integers. Selecting any node in the tree requires an infinite sequence of integers.

For a computer program to represent a notation for a set it must be well founded. If a program is well founded and we repeat the process of taking any output at level $n$ and using that output as the Gödel number of a program to take the output at level $n+1$. we must reach the representation for the empty set in a finite number of steps.

If the program is well founded than every path will end in a finite sequence of integers. But for any integer $N$ there can be a path of length $N$. With no fixed limit on the length of a path we are forced to search over paths that have no limit on their length and this requires an infinite sequence of integers.

To search all paths generated by an infinite sequence of integers requires the power set axiom defined in the next section. That axiom asserts the existence of all subsets of the integers. This is not the same as an ordered sequences of integers needed to specify the position of every node in the tree. To get all ordered infinite sequences of integers from all subsets of the integers we let the integer size determine the ordering. If we used these sequences directly we would be stuck with strictly increasing sequences which would not work. We use only the first (smallest) number in the subset as is. Each subsequent number is the difference between the previous number in the sequence and the current one. This allows an arbitrary ordered sequence of integers with 1 as a minimum.

With the power set axiom and the above construction we can write the following expression that is true if program with Gödel number $p$ is well founded.

$$\forall s (s \in P(\omega)) \exists n (n \in \omega) t(p,s,n)$$

$P(\omega)$ is the set of all subsets of $\omega$. $t(p,s,n)$ is a recursive relationship that is true if at the $n$th level in the evaluation of nondeterministic program $p$ down the path indexed by the sequence of integers $s$ the output is the empty set. Thus the full expression says that for every possible path $s$ in evaluating the full tree of outputs from $p$ the empty set will terminate the path at some finite level $n$. If the statement is true than $p$ is well founded. .

Recall from Section 4.2 that an ordinal is defined as being well ordered by $\in$ and transitive. So in addition to being well founded we must insure the representation meets these requirements. These properties require a search over all members of specific sets. Such an infinite search is not recursive. It requires an existential quantifier in an expression like $\exists n P(n)$. Recall Section 4.1 and Table 4.2 show how to replace multiple adjacent existential quantifiers with a single existential quantifier. Using this technique we can incorporate the transitive and well ordered properties as well as the requirement that each set has a unique representation into the $\exists n (n \in \omega) t(p,s,n)$ part of the above expression defining well founded programs.

Completed second draft of this book

PDF version of this book