FOM: New Classifications 3

[Harvey Friedman]

Here is a detailed report on the classification presented in
8:16PM 2/21/02:

We consider disjoint inclusions of the form

Ai U. fAj containedin Ap U. gAq

where 1 <= i,j < p,q <= 3. (Here fAj = f(A_j) is the set of all values of f
at arguments from A_j).

Here f,g stand for multivariate functions from N into N, and A1,A2,A3 stand
for subsets of N. Also U. stands for disjoint union.

There are seven such statements:

1. A U. fA containedin B U. gB
2. A U. fA containedin B U. gC
3. A U. fA containedin C U. gB
4. A U. fA containedin C U. gC
5. A U. fB containedin C U. gC
6. B U. fA containedin C U. gC
7. B U. fB containedin C U. gC

There are 128 sets of such statements.

For every set S of these 7 statements, let *(S) be the following assertion:

For all multivariate functions f,g from N into N of quadratic growth, there
exist infinite sets A,B,C containedin N such that S holds.

Let MAH = ZFC + {there exists an n-Mahlo cardinal}n. Let MAH+ be ZFC + "for
all n, there is an n-Mahlo cardinal".

THEOREM 1. For S, *(S) is provable in MAH+ or refutable in RCA0. This
result is finisitically proved.

THEOREM 2. For 46 sets S, *(S) is provable in MAH+. For 82 sets S, *(S) is
refutable in RCA0.

The classification has the following result to date:

1. 82 sets S with *(S) refutable in RCA0.
2. 37 sets S with *(S) provable in RCA0.
3. 7 sets S with *(S) provably equivalent to the 1-consistency of MAH over ACA.
4. 2 sets S with *(S) provable from the 1-consistency of MAH over ACA, but
for which I do not know their metamathematical status. However, I know that
the 2 sets have the same status (i.e., their *'s are provably equivalenct
over RCA0).

So it appears very likely that every *(S) falls into one of the following
three groups:

a) provable in RCA0;
b) refutable in RCA0;
c) provably equivalent to the 1-consistency of MAH over ACA.

I will work some more to complete the sharper classification into a),b),c).
These remaining 2
cases (really one case) seem stubborn. Many of the cases falling into a)
and b) are somewhat tricky.

Recall the "master" case of S = {3,5} which is in category c).

I chose the condition 1 <= i,j < p,q <= 3 in order that

i) the "master" case would be included;
ii) I could actually carry out the classification.

I have carried it out in the sense of Theorems 1 and 2. However, as
indicated, I am not sure what weaker assumptions than Mahlo cardinals might
be sufficient to establish 2 of the 128 cases.

There is an obvious series of more ambitious classifications. Obviously,
one would like to simply remove 1 <= i,j < p,q <= 3, so that there are 81
statements intead of 7, and so there are 2^81 assertions to be analyzed
instead of 127. There are all sort of less ambitious classifications that
will be done before that is done.

In each of the category b) items, there is some sort of strong finite
obstruction. I will report on this later.

COROLLARY 3. The statement "there are exactly 46 true *(S)" is provably
equivalent to the 1-consistency of MAH over ACA. "there are at least 40
true *(S)" is also provably equivalent to the 1-consistency of MAH over ACA.