[FOM] complexity of open questions

[Harvey Friedman]

What is the range of quantifier complexity of major open questions in
mathematics? What does the distribution look like?

There are some issues that need to first be resolved in order to set the
ground rules for answering, or shedding light, on this question.

One issue that needs to be resolved is just what constitutes a major open
question in mathematics.

Since the answer seems to greatly depend on whether one is talking about
separable or nonseparable mathematics, let us divide this into two
questions:

1. What is the range of quantifier complexity of major open questions in
separable mathematics? What does the distribution look like?

2. What is the range of quantifier complexity of major open questions in
nonseparable mathematics? What does the distribution look like?

Further divisions are also fruitful or illuminating. E.g., by subject matter
- like algebraic number theory, or partial differential equations, etcetera.

Another issue is the word "major". This can be roughly gauged by, e.g., the
number of published papers that mention the problem, perhaps weighted by the
"quality" of the Journals in which they appear. Another measure might be the
number of faculty at "top mathematics Departments" that have included work
on the problem in their grant proposals.

A more logical issue is the following. It may be that with some known work,
the problem is known to be equivalent to a statement whose quantifier
complexity, Y, is lower than that of the problem, X. In this case, it should
be noted that 

the quantifier complexity of the problem is X, and Y by equivalence.

There are also some more subtle situations where there is a widely believed
conjecture that implies the answer to the problem, and that conjecture has
lower complexity than the statement of the problem. In this case, it should
be noted that 

the quantifier complexity of the problem is X, and Y by conjecture.

A typical example of this is major open questions that are Pi03. Often one
believes a conjecture that the existential quantifier can be nicely bounded
in terms of the outermost universal quantifier, thereby reducing the
quantifier complexity to Pi01 "by conjecture".

These ideas can be applied to previous major open questions that have been
settled. One can, in retrospect, sometimes - may often - see that the
original statement is, say, Pi03, but one actually proves a Pi01 statement
that was well known to imply the original statement before the problem was
solved, Then we can say that

the quantifier complexity of the problem is X, and was found to be Y by
solution.  

With this last point in mind, we should reformulate our two questions as
follows.

1'. What is the range of quantifier complexity of (current, or past) major
open questions in separable mathematics (by equivalence, conjecture, or
solution)? What does the distribution look like?

2'. What is the range of quantifier complexity of (current, or past) major
open questions in nonseparable mathematics (by equivalence, conjecture, or
solution)? What does the distribution look like?

It is my own feeling that for 1', Pi01 is dominant, especially by
equivalence, and more so by conjecture and yet more so by solution.

For 1', next, is Pi02 and Pi03. I am not sure about the comparison between
Pi02 and Pi03. I think that Pi02 is next, and Pi03 is close to, but rarer
than Pi02. I think that the jump from Pi01 to Pi02 is significantly greater
than the jump from Pi02 to Pi03.

For 1', next is Pi11. Then next is Pi12.  Whether we have examples beyond
Pi12 for 1' may depend on the interpretation of "major open question" and
"separable mathematics". I take "separable mathematics" to mean that the
objects are all "essentially countable", so that all objects are to be Borel
measurable sets and functions on complete separable metric spaces.

This discussion is not meant to apply to the Exotic Statement in BRT. But we
can still discuss this in these terms. It is a separable statement, an open
question, and of quantifier complexity Pi12, and of quantifier complexity
Pi02 by equivalence. It is open in the sense that we do not know the status
of Mahlo cardinals of finite order. If we do know the status of Mahlo
cardinals of finite order (controversial), then the statement is Pi12, and
Pi02 by solution. 

I am also interested in 2', although I certainly have not thought too much
about this.

Harvey Friedman