FOM: 3:Simplicity

[Harvey Friedman]

This is the third in a series of positive self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.

Cohen proved the underivability of the continuum hypothesis in ZFC
(assuming ZFC is consistent) in the early sixties. Thus combining this with
Godel's work in the late thirties, the independence of the continuum
hypothesis from ZFC was established. This was the first mathematical
independence result from ZFC.

Of course, in the thirties, Godel had shown the independence of the
consistency of ZFC from ZFC. This result, of course, has its own special
staggering importance for f.o.m. But CH provides normal mathematical
information about normal mathematical objects - as long as abstract set
theory in the style of Cantor is included as normal. This distinction is of
course informal at the present time. However, this does not diminish the
importance of the distinction, and does not mean that the distinction is
unclear.

PROBLEM: Make a formal distinction between, say, the continuum hypothesis
and Con(ZFC).

Well, there is an obvious one, namely the latter is an assertion about
finite objects and the former is not. However, this is not the relevant
distinction at this point in this discussion. So we refocus this as:

PROBLEM: Make a formal distinction between CH and an arbitrary sentence in
the language of set theory.

Here one can say that CH is naturally formulated as a statement about the
initial segment of the cumulative hierarchy, V(w+2). However, it is clear
that CH is a preferred statement even about V(w+2). So we can now refocus
the problem again.

PROBLEM: Construct a basic set theoretic language in which CH is
particularly simple. Prove that CH is the simplest sentence in the language
which is independent of ZFC.

We need a good candidate for a relevant set theoretic language. This should
be investigated for a variety of proposed languages.

Let R be the set of all real numbers. As a simple first pass, let's have
variables over sets of real numbers, constant symbols N and R standing for
the set of all natural numbers (as a subset of R) and the set of all real
numbers, and function variables ranging over everywhere defined functions
from R into R. We use only the following primitive concepts:

a. f maps A into B.
b. f maps A onto B.
c. f maps A one-one into B.

No equality and no epsilon. "Theory of maps." We should start at this
perhaps quite easy but not totally trivial level.

CH is stated in many simple ways: e.g., (forall A)(exists f)(f maps N onto
A or f maps A onto R).

Here are some conjectures.

1. The set of all true sentences in this language is decidable.
2. The set of all sentences in this language that are provable in ZFC is
decidable.
3. Every sentence in this language is provably equivalent, over ZFC, to
1=0, 1=1, or a disjunction of statements of the form 2^w = w_n, where n is
in N.
4. Any sentence in this language of smallest "size" that is independent of
ZFC is equivalent to CH.

After this is done, slowly beef up this language. E.g., add 1 or more of
the following:

a. Equality between sets, and equality between functions.
b. Variables over reals, with epsilon.
c. Function application.
d. < on N.
e. Functions of more than one variable.

At some point when algorithmic undecidability creeps in, it becomes crucial
to look at, say, only AE sentences, or restrictions involving size or other
structural features.

This can be viewed as part of a wider program not necessarily directed at
independence results. Namely, the construction and investigation of simple
languages tailor made to basic mathematical situations, where one does not
always look for algorithmic decidability of the entire set of true
sentences in the language, but rather to weak fragments - in order to find
the border between decidability and undecidability. And also to investigate
detailed questions of simplicity.

Mathematicians are definitely interested in and acutely aware of
simplicity. We can start to consider the idea of making something of a
science of it.

NOTE: I was starting to write to you about independence results concerning
Borel functions, and when setting the stage for my discussion, this
occurred to me. So I have not worked on these problems, and hence the
formulations may well have defects that need to be modified. Nevertheless,
I hope that the main points are clear and interesting to you. This process
is systematic f.o.m.