New version of this book

What is infinity in mathematics

---

What does one make of the immense body of mathematics based on infinite structures  ? The universe may be potentially infinite. Thus questions about whether a Turing Machine 

(TM ) will halt can be meaningful without reference to the completed infinite. (TM s are a special class of computer that have unlimited storage and that can execute any mathematical algorithm with the appropriate program.) This is a question of whether an event will ever occur in an indefinite future.

Every initial segment of a potentially infinite universe is potentially empirically accessible to us. Questions about all these segments may be meaningful. To say a TM does not halt is meaningful because if it does halt we (or our distant ancestors) may eventually know about it.

Most of mathematics that deals with the infinite can be interpreted as dealing with the potentially infinite. For example the question of whether a species will have an infinite chain of descendant species  can be defined in a way that requires quantification over the reals  . There is no single event that decides this question but it is still meaningful and interesting in a potentially infinite universe. It is determined by a recursively enumerable set of events that can be listed by a computer. Some questions such as the Continuum Hypothesis 

(see Appendix on page ) cannot be. I do not think such questions have any absolute meaning. They are questions about formal system  s which are within a particular system true, false or undecidable.

To understand in more detail how to develop conventional mathematics along these lines we revive the old idea of the `  ' quantifier. This can replace both the universal and existential quantifiers over the integers: is true if and only if is true for some infinite subset of the integers. This is equivalent to saying that some particular TM has an infinite number of outputs.

This can be generalized to provide an interpretation of the arithmetical sets of integers  (those definable with a finite number of quantifiers ranging over the integers). To do so we use the concept of a nondeterministic TM  . Here nondeterministic does not refer to probabilistic behavior. A nondeterministic TM is completely deterministic in its behavior. However, instead of executing a single program, it executes one or more (up to a recursively enumerable set) programs.

Any arithmetical set of integers can be defined by a succession of a finite number of quantifiers: . This in turn is interpretable as some statement about a nondeterministic TM . For two quantifiers, the equivalent statement is that a TM has an infinite number of outputs, such that an infinite subset of these are the Gödel numbers of TM s that in turn have an infinite number of outputs. This is equivalent to a statement about a single nondeterministic TM , since we can easily program such a machine to simulate all the TM s that outputs. This result can be generalized to any finite number of `' quantifiers.

Generalizing further one can also define the hyperarithmetical sets of integers 

as properties of nondeterministic TM s.

We can go a little further. To define the set of all hyperarithmetical sets of integers or equivalently all recursive ordinals 

requires quantification over the reals. See Appendix on page if these terms are not familiar. Yet this set also has a natural interpretation in terms of nondeterministic TM s. To show this we introduce a variation on the notion of well foundedness  .   Program a nondeterministic TM to do the following given the Gödel number  of some other TM () as input. Simulate and for every value that outputs treat this as a the Gödel number of another TM . Simulate this machine just as is simulated, so each of its outputs is interpreted as the Gödel number of another TM . Repeat this process for all outputs of all machines simulated. A path through this tree of simulations is defined to be a sequence of Gödel numbers of TM s. The first element of the sequence is , the second is an output of , the third is the output from the second element in the sequence, the fourth and output from the third etc. is well founded if every path is finite. The set of all recursive ordinals is recursive in the set of well founded TM s. This is not surprising since the definition of well founded TM is close to the definition of a recursive ordinal.

At least this initial fragment of the hierarchy of real numbers  has a natural interpretation as properties of TM s.

What is the advantage of analyzing mathematics in this way and is this mathematics, even interpreted as properties of TM s, relevant to anything at all? Understanding the mathematics as properties of TM s offers the possibility of adding an experimental element to the study of logic. One can write programs of the type just discussed and observe their behavior. This can make it easier to gain insight into this area of mathematics. Something like this has happened. Until recently nonlinear differential equations  were, for the most part, ignored as being too complex to understand. Once researchers started playing with simulations, a new branch of mathematics, Chaos theory  , was created. Chaos theory is only possible because one can simulate complex systems and observe their behavior.

We know mathematics that requires quantification over infinite sets  is useful because it can make it easier to decide practical questions. However, if there are no infinite sets, does this mathematics have a meaning and use in its own right as opposed to being an aid to decide lower level questions? Nondeterministic TM 's are similar to the most important process on earth: biological evolution  . (At least this is true if biological processes only has access to finite computation.) If we identify a species with a single TM then the question of well foundedness for biological evolution is the question will any species have an infinite chain (the second element of the chain is a descendant of the first, the third a descendant of the second, etc.) of descendant species.

Consider that nondeterministic processes are not subject to the limitations of Gödel 's incompleteness theorem  . As long as the number of paths of evolution that you follow increases without limit, there is nothing to prevent one particular path from ultimately solving the halting problem  for every TM using a chain of mathematical systems each of which proves the consistency of the previous one. This suggests that thinking in terms of nondeterministic processes 

may be helpful in creating mathematics and that the resulting mathematics is the mathematics of creativity.

New version of this book