FOM: FoundationalCompleteness

[Harvey Friedman]

Some of my e-mailings will be in the form of detailed replies to others,
and some of them will be self contained discussions of a foundational (of
math) matter. You can easily tell from the Subject header. This is of the
latter kind.

I didn't intend to write this one, but the topic came to mind in reading
the postings of those who are, in some way, unsatisfied with the usual set
theoretic foundations for mathematics, and strive for a kind of
"structuralist" viewpoint - particularly, Pratt and Barwise.

The usual set theoretic foundations is very powerful, coherent, concise,
successful, explanatory, impressive, and totally dominating at this time.
Taken as a whole, with the major supporting classical developments, it is
certainly one of the few greatest acheivments of the human mind of all time.

However, it also does not come close to doing everything one might demand
of a foundation for mathematics. At the present time, there is no full
blown proposal for scrapping it and replacing it with anything
substantially different that isn't far more trouble than its worth. Present
cures are far far far worse than any perceived disease.

Now this does not mean that the usual set theoretic foundations might not
give way to a better foundations, or might not be altered in some very
significant and permanent way. In fact, I can tell you that I work on this
from time to time. It just that people should recognize what's involved in
doing such an overhaul, and not fool themselves into either

	i) embracing something that is either essentially the same as the
usual set theoretic foundations of mathematics; or
	ii) embracing something that doesn't even minimally accomplish what
is so successfully accomplished by the usual set theoretic foundations of
mathematics.

Now before I remind everybody of some of the most vital features of the
usual set theoretic foundations for mathematics, let me state a great,
great, great, theorem in the foundations of mathematics:

THEOREM. Sets under membership form the simplest foundationally complete
system.

There is one trouble with this result: I don't know how to properly
formulate it. In particular, I don't know how to properly formulate
"foundational completeness" or "simplest."

Making sense of this "Theorem" and closely related matters are typical
major issues in genuine foundations of mathematics. Now before coming back
to this, let me summarize the greatest of the usual set theoretic
foundations of mathematics.

First of all, set theory is unabashedly materialistic - a perhaps
nonstandard word I use to describe the opposite of structuralistic. The
viewpoint is that the empty set of set theory has a unique unequivocal
meaning independently of context. There is the empty set, and that's that.
It doesn't need any context. There is no talk of identifying distinct empty
sets because they form the same function.

This materialistic concept of set seems to be very congenial to almost
everybody for a while. Thus {emptyset} also has a unique unequivocal
meaning independently of context. In fact, one can construct the so called
hereditarily finite (HF) sets by the following process:

	i) the emptyset is HF;
	ii) if x,y are HF then x union {y} is HF.

This has a clarity and congeniality for most people, without invoking any
structuralist ideas.

Now I can already hear the following remark: see, you have used an
inductive construction that has not only not been formalized in set
theoretic terms yet, but is not even best formulated in set theoretic
terms.

Yes, this is true. And yes, there is an idea of inductive construction - at
least for the natural numbers - which is not directly faithfully conceived
of in purely set theoretic terms. However, look at the costs of scrapping
the set theoretic approach in favor of "inductive construction." Can this
really be done? I have certainly thought about this, but without success.
It is certainly an attractive idea, and we explicitly formulate this:

FOUNDATIONAL ISSUE. Is there an alternative adequate foundation for
mathematics that is based on "inductive construction?" In particular, one
wants to capture set theory viewed as an inductive construction. If not,
one wants to construct a significant portion of set theory as an inductive
construction.

Now, instead of scrapping the set theoretic approach in favor of "inductive
construction," what about incorporating both? Yes, this can be done in
various ways. However, so what? This is only really interesting if one can
isolate a small handful of additional ideas that one wishes to directly
faithfully incorporate into the prospective foundation for mathematics.
Better yet - prove some sort of completeness of this handful.

However, consider the situation in mathematics that was one of the major
precipitating factors that made people realize the urgency of foundations.
Namely, people were creating all kinds of mathematical concepts - groups,
rings, fields, integers, rationals, reals, complexes, division rings,
functions of a real and complex variable, series, etcetera. There was no
unifying principle as to what is or is not a legitimate construction.
Mathematicians do not want to go down that road again, and are comforted by
the fact that this matter has been resolved by set theory - even if it does
not provide for a directly faithful formalization of the way they actually
visualize and think. In summary, there is a danger of the cure being far
far far worse than the disease.

Now, coming back to set theory and HF. Obviously, it is congenial and
natural to most people to form the set HF. And then there is the natural
idea of subset of HF. Then for each natural number n, one can form the n-th
power set of HF; let's write this as V(w+n).

Let us give the name V(w+w) for the universe of all sets that are members
of some V(w+n). There are a number of beautiful axioms one immediately
writes down about this universe. A small number of them allow for the
derivation of lots of others. This is a very coherent and workable system
of objects, under epsilon, for a foundation of a very very large portion of
mathematical practice. Now I have been very concerned with the following
for nearly 30 years:

FOUNDATIONAL ISSUE. What interesting mathematics is missing if one uses
V(w+w) (with the obvious associated axioms)? Obviously, one does not mean
simply that V(w+w) itself is missing, since V(w+w) is meant to provide
ontological overkill. Instead, one means that what mathematical information
of an ordinary mathematical character cannot be derived in such a
foundation?

Ex: Let E be a subset of the unit square in the plane, which is symmetric
about the line y = x. Then E contains or is disjoint from the graph of a
Borel measurable function.

This cannot be proved in such a Foundation, but can be proved in a somewhat
more encompassing foundation. This resuilt is a typical acheivement in
foundations of mathematics.

TO BE CONTINUED SYSTEMATICALLY IN SEVERAL DIRECTIONS AND LEVELS.