Next: A recursive functional Up: Recursive structures for Previous: C ++ constructs

# Sets versus recursive functionals

We can fully model the structure of any recursive ordinal with a functional on the integers. That is a functional that accepts integers as input and has as output a notation that represents either an integer or a functional on the integers. We need the ordering of elements in the domain of a functional to match the ordering of elements in the range. That is if a<b we want . To make this possible we must allow two kinds of elements in the range of the functional. The first represents a subset and the second a union of elements each of which individually represents a subset. For example the ordinal   is represented by a functional f on the integers such that , , etc. However does not represent a set but an infinite union of sets (all the integers) that are are each members of the ordinal represented just as is a member.

It does not matter how one builds up the ordinal hierarchy in set theory because each ordinal is the union of all smaller ordinals plus the set containing this union. The set for a particular ordinal will be the same no matter how it is constructed. The structure we must build is more complex and has additional constraints. We want to make all operations on these structures effective and thus we must insure that we can have a recursive process to determine if any two ordinal notations are identical and if not which is larger.

It might seem that this restricts us to recursive ordinals. However we can define an expandable recursive notation. The notation is recursive and has a recursive expansion for every recursive ordinal. The natural way to define this property requires self referencing statements of a type not allowed in ZF. We can define the property in terms of sequences of sets but this is awkward. As we expand the hierarchy we need to generalize this definition in complex ways and the corresponding set theory definition becomes more awkward.

Next: A recursive functional Up: Recursive structures for Previous: C ++ constructs
Mountain Math Software