FOM: Complexity of statements

[Harvey Friedman]

Shipman 2:23PM 4/20/98 writes:

>1)Are any important open problems outside of
>logic, fom, and set theory not equivalent to statements of 2nd-order
>arithmetic?
> 2) What important problems require more than 2 quantifiers in 2nd-order
>arith-
>metic? More than 3? 3) What important (1st-order) arithmetical problem
>needs the
>most quantifiers? 4) What's the most important unsolved pi_0_0 problem?

I would like to make some hopefully clarifying remarks about this.

We need to distinguish between quantifier complexity of open problems in
mathematics, and quantifier complexity of known theorems in mathematics.

The normal way to measure quantifier complexity is by the classes Sigma^n_m
and Pi^n_m. There are many ways to explicit define this, but perhaps the
neatest is that in a Sigma^n_m sentence, there is a block of quantifiers
explicitly range over V(omega + n), where this block starts with an
existential quantifier, and there are m alternations of like quantifiers.
This block of quantifiers is followed by any formula in which all
quantifiers by bounded (to other variables). Here n >= 0 and m >= 1. This
is an appropriate classification scheme for a great deal of mathematical
statements. It obviously isn't appropriate for statements that involve sets
outside of V(omega + omega), nor statements that involve only a finite
number of objects.

As far as open mathematical problems are concerned, what Shipman is asking
us to do is this: given an open mathematical problem A, find (n,m) and a
sentence B in class Sigma^n_m or class Pi^n_m, and a proof that A is
equivalent to B in ZFC. One answer is better than another if the complexity
class of one is properly included in the complexity class of the other. The
proper inclusion relations are only that Sigma^n_m and Pi^n_m are both
properly included in each of Sigma^r_s and Pi^r_s if (n,m) is
lexicographically earlier thn (r,s).

Now what about an existing mathematical theorem? Obviously, it is provably
equivalent to a sentence in the lowest levels of all: (for all x in
V(omega))(x = x), and (there exists x in V(omega))(x = x).

What we need is a notion of intrinsic complexity. Here we need reverse
mathematics, or the approach of reverse mathematics. Here one first
identifies a language L in which mathematical statements are to be cast,
and a base theory T, much weaker than ZFC. Now we have an intrinsic
measure. Let A be a mathematical statement formalized in the language L. We
say that A is essentially in class Sigma^n_m or essentially in class Pi^n_m
if and only if there exists a sentence B literally in class Sigma^n_m or
literally in class Pi^n_m such that T proves "A if and only if B."

I should add that reverse mathematics is mainly concerned with another
related and generally sharper kind of result: to classify theorems up to
provable equivalence over T.

The current status of reverse mathematics supports this development only
with some limitations. First of all, the language L chosen is that of
second order arithmetic - or, equivalently, that of the theory of V(omega +
1).[NOTE: It has become customary to use the natural numbers with + and x
instead of the hereditarily finite sets, V(omega), under epsilon. It makes
no significant difference.] So given a mathematical statement that is not
literally stated in this language, one must translate it into this
language. Normally this is trivial and canonical, and there is no question
of the preservation of the meaning of the sentence. But sometimes this is
an issue, and one must choose a particular representation. Secondly, the
base theory chosen - RCA_0 - is stronger than desirable, in that too much
is already provable in RCA_0. So for too many important mathematical
theorems A, we have that RCA_0 proves A, in which case A is in the lowest
complexity classes trivially.

What is needed is 1) a weaker base theory than RCA_0; and 2) a base theory
whose language is much wider than RCA_0. Reverse mathematics is already
vast and deep as it is, without changing the base theory from RCA_0.
However, this matter is under active investigation on several fronts. There
are some proposals for weakening RCA_0 and keeping the language the same.
There are also some proposals for widening the language, where a first step
is to find very strong set theoretic conservative extensions of RCA_0.

What are the constraints on doing this? Well, the main one is that if the
base theory is too weak then there may be multitudes of different ways of
stating mathematical theorems whose metamathematical status over the base
theory differ. A very good balance is acheived with RCA_0. And if the
language is to be extended to directly incorporate more set theory, then
there is an even greater danger of this. I tend to be an optimist. I
believe that a proper balance can be acheieved with a very robust theory
based on a suitable base theory that both supports set theory and is very
much weaker than RCA_0.

Current reverse mathematics robustly interprets statements that live among
the Borel sets and functions in complete separable metric spaces. However,
abstract measure and probability theory are subject to various issues. One
can of course usually pare this down to Borel sets and functions in
complete separable metric spaces. One can also exploit that one often cares
only up to measure 0, in which case the factor space is quite nice - often
also a complete separable metric space. So probably a very good case can be
carefully made that staying within the language of second order arithmetic
(or of V(omega + 1)) is good enough, and that fooling with it may cause
more problems than it solves. However, the matter is still worthy of
considerable investigation.

There is yet another classification scheme that distinguishes between
different theorems of RCA_0 and in fact different theorems of very weak
fragments of RCA_0. That is if we bring in issues of constructivity. E.g.,
Falting's theorem is Pi^0_3, and we don't know where it can be proved.
Logicians have not gone into this in detail because of the considerable
amount of mathematics involved - although the proof has been substantially
simplified.

But even if Falting's theorem is shown, routinely, to be proved in very
weak fragments of RCA_0, there is still the issue of whether it is
constructively true. We can state this as follows. Is Falting's theorem
provable in HA = Heyting Arithmetic? Here we are in the same position now
that we were when Falting's theorem was simply Mordell's conjecture. So we
can ask: is Falting's theorem at least provably equivalent to a Pi^0_2
sentence in HA? We can ponder this question even if we were to know the
expected fact that Falting's theorem is provable in PA.

**So the intuitionistic classification is to be distinguished from the
classical classification.**

Now I come to Shipman's questions. Here are a few unusual examples. Of
course, I have been quite struck for over 30 years by the overwhelming
preponderance of well known open problems in matheamtics that lie
considerably below the threshold of nonabsoluteness. This is a key reason
why I work so hard on certain pet projects.

1. Hilbert's 10th problem on the rationls. This asserts that the set of all
polynomials of several variables with integer coefficients that have a
rational solution is recursive. The expected answer is no, which is in
class Pi^0_3.

2. Modified Hilbert's 10th problem on the rationals. This asserts that the
set of all polynomials of several variables with integer coefficients that
have finitely many rational solutions is recursively enumerable. This is
known to be false in the integers. The expected answer is no, which is in
class Pi^0_4.

3. "Any two complete analytic sets of reals are in one-one correspondence
by a Borel function" is known to be equivalent over ZFC to (for all x
containedin omega)(x# exists), which is known to be Pi^1_4 and no better.

4. "Every uncountable coanalytic set contains a perfect subset" is known to
be equivalent to (for all x containedin omega)(L[x] has countably many
subsets of omega), which is known to be Pi^1_4.

5. "There exists a Borel set in the plane which meets every line in exactly
two points," an old open problem, is Sigma^1_3.

Good places to look: conjectures about the behavior of analytic functions
on the boundary of the domain. Certain topics in abstract probability
theory. Fourier series, trigonometric series, and pointwise convergence to
discontinuous functions. General topology and point set topology. Countably
infinite Ramsey theory and bqo theory.

Here is my favorite example of a dijunction which is a theorem of PA and
not known to be a theorem of HA:

either e + pi is irrational or e - pi is irrational.

Here is an example of a Pi^0_4 theorem of PA which is not known to be a
theorem of HA, and not known to be equivalent in HA to any Pi^0_3 sentence,
and not known to be effectively true.

For all distinct integers n,m, either e + n(pi) is irrational or e - m(pi)
is irrational.