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 modeled by a nondeterministic computer program like those used in defining an $n$-tree. By defining precisely what it means for the structure of an ordinal to be modeled by a computer, one can define the set of all recursive ordinals. This set is the smallest nonrecursive ordinal.

A computer program can model the structure of a recursive ordinal by outputting Gödel numbers that represent all the members of the ordinal in question. Every set except the empty set is represented by a program with at least one output. 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 represent a set. A program represents a set only if all of its outputs represent sets.

Many computer programs (in fact an infinite number) will be representations of the same set. Sets are uniquely determined by their members but representations for sets are not. To deal with this require that only one Gödel number represents each each set.

A computer outputting representations for the members of an infinite set gives an ordering to the members that is not present in the original set. (The outputs must come in some sequence.) This can be confusing. For a set like $\omega+1$ the order the representations are output must differ from the ordering of the set members defined by $\in$. Recall that ordinals are well ordered by $\in$. The representation for $\omega$ must be output before the representations for most of the elements of $\omega$. Otherwise one would never get around to outputting the representation for $\omega$.

Most computer programs will not represent sets. Most that do represent sets will not represent ordinals. To define which programs represent a set requires defining which are well founded. Sets constructed from the axioms of set theory 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 node is the number of times the output of a program is interpreted as another program before getting to this node. The original program is level 0. Outputs of that program are level 1. Outputs of these programs are 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 etc.

If a program is well founded, then repeating 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$. will 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, one must search over paths that have no limit on their length. 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 implies the set of all subsets of the integers exists. This is not the same as the set of all 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, let the integer size determine the ordering. Using such a sequence directly would result in strictly increasing sequences. That does not work. Instead 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 One 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,O(s),n)$$

$O$ is the map between an unordered sequence of integers and the ordered sequence defined in the above paragraph. $O$ also needs to extend any finite subset of the integers to make it infinite by, for example, repeating the last element in the finite set. $P(\omega)$ is the set of all subsets of $\omega$. $t(p,O(s),n)$ is a recursive relationship between the program with Gödel number p, the ordered sequence of integers $O(s)$ and the integer $n$. It is true if there exists an output of 0 at level $n$ from program $p$ with path given by sequence $O(s)$. Thus for every possible path $O(s)$ in the 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 6.2 that an ordinal is defined as being well ordered by $\in$ and transitive. So in addition to being well founded an ordinal representation must meet 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 6.1 and Table 6.2 show how to replace multiple adjacent existential quantifiers with a single existential quantifier. Using this technique one 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.

PDF version of this book