The barber in the small town shaves everyone in town who does
not shave himself. Does the barber shave himself? This version of
the Russell paradox illustrates the
difficulty with having a universal set in a mathematical formalism.
Russell felt the solution to this problem was an explicitly typed
hierarchy of sets. Functions or operations between sets at one
level in the hierarchy could only be defined at a higher level.
With Whitehead he formalized a large body of mathematics in this
way in Principia Mathematica. Zermelo Fraenkel set theory as described in Appendix 
turned out to be a far simpler
and more powerful system. It provided a similar typed hierarchy
thorough the Axiom of replacement . Today
Principia Mathematica is primarily of historical
interest.
Computers allow us to automate much of the tedious work involved in explicitly typed system like that of in Principia Mathematica. Further if we restrict notations and operations to recursive structures we can build models of these systems and play with them on computers to aid our understanding. The driving force for such a system is not to make the hierarchy explicit for its own sake. Rather it is to make the hierarchy explicit enough so that all operations on it can be programmed in a computer and we can can thus use computer technology to explore the consequences.
The value in a recursive hierarchy of functional types is in the power of the operations that can be defined. If one only has functions on the integers one can explicitly construct a new function using an old one. Every repetition of this process requires an explicit step. If one has functions operating on functions on the integers then one can automate such constructions and diagonalize them. That is one can define a function on functions that generates a new function for any integer N and one can can diagonalize this series of functions. The next level is of course are recursive functions that operate on recursive functions on the integers. Of course one can iterate this game in many different ways but the idea of well foundedness captures all the natural iterations that one might think of in a straightforward way. We can have a recursive functional on the integers that has as its range either another functional on the integer or an integer. The output of the functional must indicate whether it is an integer or the representation of another functional. It we have an arbitrary sequence of integers we can apply the first integer to the functional. If that output is a functional we can apply the second integer to it. Again of that output is a functional we can apply the third integer to it. If for every infinite sequence we always get an integer output after a finite number of steps than we say the original functional is well founded. Any recursively specifiable hierarchy functions operating on lower type functions can be specified in this way. At the same time this creates a new class of object that we can do induction on. We can construct recursive functional that will operate on any recursive functional well founded for the integers.
The notion of well foundedness does not follow in a logical way from the lower levels of functional hierarchies that it is generalization of. There is something inherently creative about this concept. Gödel 's proof insures that there are infinite number of powerful general concepts that are not in any sense a natural consequence of formalizable laws of mathematics. This underscores the creative nature of mathematics.
Note the difference between well foundedness for recursive
integer functionals and the general notion of a well founded set in
mathematics. The set theory version is more general. We will
generalize integer functional well foundedness to well foundedness
for any sequence of recursive functionals that operate on well
founded integer functionals. This generalization and others is in a
sense already covered by the set theory notion. However the
recursive function notion is much richer in structure in a way that
has the potential to suggest much more powerful generalizations.
The pristine nature of well foundedness in set theory makes it
independent of this structure. Of course within set theory one can
build the same hierarchy and get the same recursive structures. The
point is that you must build the hierarchy to see the richness of
this structure and as the hierarchy gets more complex pencil an
paper methods will not suffice. You must write computer programs to
construct a fragment of the hierarchy as we do in Appendix .
| home | consulting | videos | book | QM FAQ | contact |