Mountain Math Software
home consulting videos book QM FAQ contact

Generalizing recursive ordinal notations

Introduction

A recursive ordinal has a notation that recursively describes its well ordering. This notation must support a recursive process to enumerate notations for this and smaller ordinals and a recursive process to decide the relative size of ordinals represented by any pair of these notations. Larger countable ordinals (≥ the Church-Kleene ordinal) cannot have a recursive notation, but a weaker analog is possible. These notations for larger ordinals can be used to expand the recursive ordinals in a nested form of ordinal collapsing or projection.

A defining recursive function with a non recursive domain

For each recursive ordinal notation, α, in the ordinal calculator there is a recursively constructable recursive function on the integers fα(n) to enumerate notations for smaller ordinals. The union of ordinals represented by notations in the range of fα(n) is the ordinal represented by α. By nondeterministically evaluating fα(n) and all the functions constructable from the notations generated, directly or indirectly, from this function one can enumerate notations for all ordinals < α.

In the remained of this page the word notation is used for both a finite human readable string that identifies an ordinal and a recursive process that can operate on that string to construct the machinery for an ordinal notation system.

To extend the idea of an ordinal notation to nonrecursive ordinals we introduce a replacement for fα(n). This is gα(λ), a recursive function, not on integers, but other ordinal notations. Although the function is recursive and there is a recursive set of notations in the system that are legal parameters for gα(λ), these do not exhaust the legal parameters. The system is explicitly incomplete and designed to be expanded. In a manner of speaking it is a post Gödel system.

The notation for the Church-Kleene ordinal has, as the domain for its gα(λ), all notation for smaller ordinals that are currently in the system or that will be introduced in the future. Most instances of ordinal notations not yet in the system will be incompatible with it. The system must be expandable with some notation for any recursive ordinal. Only a `full expanded' system contains notations for all ordinals < the church Kleene ordinal. Since no finite extension can fully expand the system, it will always be incomplete. The same is true of any any formal mathematical system that can embed the primitive recursive functions. The difference is that here the incompleteness must be explicitly built into the system because the core structures are recursive processes.

The idea of a recursive function on a nonrecursive domain sounds a bit like a Turing Machine (TM) with an oracle, bit it is different. It remains a recursive process operating on finite parameters. It is only the rules about what could become a valid parameter in the future that are not recursive. For example consider a program that is recursive (gives an output in a finite time) for all inputs that are the Godel numbers of Turning Machines that halt. It is straightforward to write a program that halts in a finite time for input parameters that satisfy this condition. Consider a TM that accepts an arbitrary sequence of integer inputs and design a function that is recursive on all instances of these that will eventually halt no matter what sequence of integers they are presented with. Quantification over the reals is needed to define the domain of this recursive function.

Limit types for countable ordinals

There is a hierarchy of domains for the gα(λ) that correspond to levels in the countable admissible hierarchy. Ordinal notations label these levels as "limit types" and thus specify the legal parameters for the gα(λ) constructable for any limit ordinal α. 0 is the limit type associated with successor ordinals. 1 is the limit type designating integer parameters. It is the limit type associated with recursive limit ordinals. ω is the label for parameters that are the notations for the admissible ordinals at all finite levels in the admissible hierarchy.

With the above approach to defining "limit type" one can define the gα(λ) so that that the union of ordinals represented by notations in their domains is the ordinal represented by the notation associated with the function. This is a weak analog of the fα(n) definable for recursive ordinal notations.

The gα(λ) play another important role. There are somewhat like the hierarchy of Veblen functions giving the most rapidly increasing function definable with the available machinery. In this way they expand the ordinal hierarchy. Through the use of collapsing they do so at many levels in the countable admissible hierarchy including recursive ordinal notations. This hierarchy is a bit like the Mandelbrot set in the ways it can be embedded within itself.

Focusing on recursive processes for the gα(λ) at all levels of the countable admissible hierarchy makes it practical to program these models. This helps with their enormous and expanding complexity. It supports experiments to test and refine intuition. Regression tests can help to quickly determine if a new idea seems to work or fails completely. Tools like the ordinal calculator may eventually become an important aid to the development of mathematics.

The ordinal calculator

For a more complete description of this approach and an implementation including source code and the interactive ordinal calculator see www.mtnmath.com/ord


Mountain Math Software
home consulting videos book QM FAQ contact
Email comments to: webmaster@mtnmath.com