Next: Extending mathematics Up: Creative mathematics Previous: Axiom of Choice   Contents

# Trees of trees

Searching all paths or quantifying over the reals can, in many cases, be interpreted as a property of computer programs. In such cases one is dealing with logically determined properties of computer programs. Everything a nondeterministic program does happens at some finite time and the collection of all those events determines if a given property like defining an ordinal representation is true. Far more complex problems can be defined that remain logically determined by the outputs generated from a computer.

One way to do this is by iterating the notion of a program being well founded for inputs of a given type. To do this have the program indicate how its output is to be interpreted. For example the program may have a label that says it requires an integer input. Alternatively it could say it requires an input which is the Gödel number of a program that accepts integers as input and is well founded for such inputs.

The question is a computer well founded for integer inputs fully captures the Hyperarithmetical Hierarchy. If one could decide that question for every possible computer program, one could decide any question in the Hyperarithmetical Hierarchy. Looking for computers that are well founded for various types of inputs is a natural way to extend the hierarchy of logically determined mathematical questions.

Beyond the Hyperarithmetical Hierarchy, mathematics becomes likes Swiss cheese. It is full of holes. One can list by a computer all meaningful mathematical questions at a given level of the Hyperarithmetical Hierarchy. But all levels of this hierarchy cannot be enumerate, even though structures that transcend the hierarchy can be defined by quantifying over the reals.

The idea of being well founded is a conceptual leap that allows us to do induction on more powerful structures. So what is the next conceptual leap and how do we find it? The axioms of set theory allow us to quantify over not just reals but functions from reals to reals (with cardinality ) and much larger cardinals. The difficulty with using such abstractions to define higher level iterative structures is their disconnect from properties of computer programs. The total number of events that fully characterize the execution of a nondeterministic computer program is countable. Cardinals larger than the reals seem to have a limited relevance to such structures.

Perhaps it is possible to come up with more powerful structures by approaching the problem in a different way. Instead of looking to larger cardinals one can explicitly generalize the concept of trees of trees. A nondeterministic computer program can label its outputs in a variety of ways. For example they may be integers or the Gödel numbers of well founded computer programs that terminate with outputs that are integers. Once one has defined a hierarchy in this way one can use the hierarchy itself to label levels in a more complex hierarchy. What are the most powerful ways one can generalize and iterate such structures?

An advantage of this approach as that one can write and play with computer programs to develop intuition and understanding. Research in the foundation of mathematics is one of the few if not the only major scientific discipline in which computer simulations do not play a major role in developing the field. I believe that is unfortunate and significantly greater progress is possible by changing it.