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 |