FOM: Does Mathematics Need New Axioms? Research Update

[Harvey Friedman]

This is an update to my posting Do We Need New Axioms? Results/Conjectures
8:09PM 2/11/00.

The main conjectures remain the same (although we now think it best to use
linear growth rather than quadratic growth), but the particular weakenings
of the main conjectures that look both promising to establish and quite
strong have been improved. Also, we have added the dimensionality
conjectures.

This posting is self contained.

**********

Let N be the set of all nonnegative integers. A multivariate function on N
is a function f such that

i) there exists k >= 1 such that the domain of f is  N^k;
ii) the range of f is a subset of N.

For A containedin N, we write fA = {f(x): every coordinate of x lies in A}.

The main conjectures concern the following family of 2^2^9 statements (up
to formal Boolean equivalence):

*Let f,g be multivariate functions on N obeying the inequality c|x| <=
f(x),g(x) <= d|x|, where c,d are rational constants > 1. There exist
infinite sets A,B,C containedin N such that a given Boolean equation in
A,B,C,fA,fB,fC,gA,gB,gC holds.*

Here |x| can be taken to be any l_p norm, 0 < p <= infinity - the
inequality has the same meaning for any such norm. And Boolean equations
are simply equations between terms using the Boolean operations of union,
intersection, and complement (relative to N).

Note that there are 2^2^9 formally inequivalent = semantically inequivalent
Boolean equations, but in this case, the number can readily be cut down
somewhat because of relations like A containedin B implies fA containedin
fB.

THEOREM 1 (66%). There is an instance of * that is provably equivalent to
the 1-consistency of Mahlo cardinals of finite order, over ACA. Conjectures
2 and 3 for * (see below) each imply the 1-consistency of Mahlo cardinals
of finite order, over ACA.

CONJECTURE 1. Informally speaking, it is necessary and sufficient to use
Mahlo cardinals of all finite orders in order to determine the truth values
of all instances of *. In particular, every instance of * is either
refutable in RCA_0, provable in ACA, or provably equivalent to the
1-consistency of Mahlo cardinals of finite order over ACA, with all three
possibilities present. Furthermore, in the first of the three cases, the
refutation proof can be given with fewer than 100,000 symbols in RCA_0 with
abbreviations.

DIMENSIONALITY CONJECTURE 2. If in *, we require that the given functions
are binary, then we obtain the same true instances.

FINITE OBSTRUCTION CONJECTURE 3. Any particular instance of * that holds
with "infinite" replaced by "arbitrarily large finite" must hold in its
original form.

Consider the following more general family of statements, indexed by n,m >=
1 and Boolean equations in (n+1)m set variables:

**Let f_1,...,f_n be multivariate functions on N obeying the inequality
c|x| <= f_1(x),...,f_n(x) <= d|x|, where c,d are rational constants > 1.
There exist infinite sets A_1,...,A_m containedin N such that a given
Boolean equation in
A_1,...,A_m,f_1A_1,...,f_nA_m,f_2A_1,...,f_2A_m,...,f_nA_1,...,f_nAm
holds.**

EXTENDED CONJECTURES 4,5,6. Same as conjectures 1,2,3, but for **.

At this time, even the proofs of conjectures 1-3 are some distance into the
future. In order to tame these conjectures for near term results, we first
restate them slightly where we insist that the A's form a tower under
proper inclusion, and fix on the case of two functions and three sets as in
*:

***Let f,g be multivariate functions on N obeying the inequality c|x| <=
f(x),g(x) <= d|x|, where c,d are rational constants > 1. There exist
infinite sets A properlycontainedin B properlycontainedin C containedin N
such that a given Boolean equation in A,B,C,fA,fB,fC,gA,gB,gC holds.***

And we have

THEOREM 2 (66%). There is an instance of *** that is provably equivalent to
the 1-consistency of Mahlo cardinals of finite order, over ACA. Conjectures
2 and 3 for *** imply the 1-consistency of Mahlo cardinals of finite order,
over ACA.

And we restate conjectures 1-3 using ***.

However, even the proofs of these restricted conjectures are some distance
into the future. So further taming is necessary for near term progress.

So we consider

****Let f,g be multivariate functions on N obeying the inequality c|x| <=
f(x),g(x) <= d|x|, where c,d are rational constants > 1. There exist
infinite sets A properlycontainedin B properlycontainedin C containedin
N\gC such that a given Boolean equation in A,B,C,fA,fB,fC,gA,gB,gC
holds.****

And again we have

THEOREM 3 (66%). There is an instance of **** that is provably equivalent
to the 1-consistency of Mahlo cardinals of finite order, over ACA.
Conjectures 2 and 3 for **** imply the 1-consistency of Mahlo cardinals of
finite order, over ACA.

And we restate conjectures 1-3 using ****.

We have now weakened this conjecture sufficiently so that we are hopeful of
proving it. We are making considerable progress on this.

And if we get stuck with this, here is an attractive further restriction,
which should be considerably easier to handle:

*****Let f,g be multivariate functions on N obeying the inequality c|x| <=
f(x),g(x) <= d|x|, where c,d are rational constants > 1. There exist
infinite sets A properlycontainedin B properlycontainedin C containedin
N\gC such that a given Boolean equation in A,B,C,fA,fB,gB,gC holds.*****

THEOREM 4 (66%). There is an instance of ***** that is provably equivalent
to the 1-consistency of Mahlo cardinals of finite order, over ACA.
Conjectures 2 and 3 for ***** imply the 1-consistency of Mahlo cardinals of
finite order, over ACA.

Obviously, conjectures 1-3 for ***** are going to be a lot easier since we
have only to work with Boolean equations in 7 variables rather than in 9
variables.