FOM: 125:Disjoint Unions/First Classifications

[Harvey Friedman]

This is a continuation of posting #124. However, because of the milestone
that has just been reached, we will make this posting totally self
contained.

We use the entirely standard disjoint union notation. Thus

A U. B

is the disjoint union of A and B. This is just the union of A and B, but
the appearance of this term implies that A,B are disjoint.

Let f be a multivariate function from N into N. I.e., the domain of f is a
Cartesian power of N and the range of f is a subset of N. (Here N is the
set of all nonnegative integers).

We say that f has quadratic growth if and only if there are c,d > 0 such
that for almost all x in dom(f),

c|x|^2 <= f(x) <= d|x|^2

where |x| is the maximum term of the tuple x.

For A containedin N we write fA for the set of all values of f at arguments
from A. Thus if f is k-ary then fA is just f[A^k].

Here is the simple statement from #124 that is independent.

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

A U. fA containedin C U. gB
A U. fB containedin C U. gC.

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

THEOREM 2. Proposition 1 is provable in MAH+ but not in ZFC (assuming ZFC
is consistent). In fact, Proposition 1 is not provable in MAH (assuming MAH
is consistent). Proposition 1 is provably equivalent to the1-consistency of
MAH over ACA.

We now consider all "disjoint union inclusions" of the form

X U. fY containedin V U. gW

where the letters X,Y,V,W are each among the letters A,B,C.

Note that there are 81 such disjoint union inclusions. Hence there are 2^81
sets S consisting of these 81 disjoint union inclusions.

For each of the 2^81 sets S, consider the assertion *(S) =

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

Obviously Proposition 1 is *(S) for some particular S of cardinality 2.

We have made an intensive study of the *(S) for S of cardinality <= 2.
There are 406 such S.

THEOREM 3. Every *(S), card(S) <= 2, is provable in MAH+ or refutable in
RCA0. This is not true for MAH (assuming MAH is consistent), or for ZFC
(assuming ZFC is consistent).

In fact, the classification of the *(S), card(S) <= 2, is quite striking.

THEOREM 4. The *(S), card(S) <= 2, consists of
i) statements provable in RCA0;
ii) statements refutable in RCA0;
iii) exactly six statements provably equivalent to the 1-consistency of MAH.
Furthermore, the six statements in iii) result from permuting the three
letters A,B,C.

>From Theorem 4, we see that there is essentially one and only one *(S),
card(S) <= 2, that is independent of ZFC, and that one is reprented by the
set consisting of the two elements of S displayed in Proposition 1.

We now report on an earlier classification that was discussed in the
posting 10:41PM 2/24/02.

We say that a disjoint union inclusion is strictly forward if and only if
the capital letters on the left side strictly precede the capital letters
on the right side.

There are seven strictly forward disjoint union inclusions:

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.

THEOREM 5. For all sets S of strictly forward disjoint union inclusions,
*(S) is provable in MAH+ or refutable in RCA0. This is not true for MAH
(assuming MAH is consistent), or for ZFC (assuming ZFC is consistent).

THEOREM 6. For 46 sets S of strictly forward disjoint union inclusions,
*(S) is provable in MAH+. For 82 sets S os strictly forward disjoint union
inclusions, *(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 equivalent
over RCA0).

As usual we can use other notions of growth such as expansive linear
growth, or expansive linearly trapped.

**********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 125th in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:

100:Boolean Relation Theory IV corrected  3/21/01  11:29AM
101:Turing Degrees/1  4/2/01  3:32AM
102: Turing Degrees/2  4/8/01  5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01  11:10AM
104:Turing Degrees/3   4/12/01  3:19PM
105:Turing Degrees/4   4/26/01  7:44PM
106.Degenerative Cloning  5/4/01  10:57AM
107:Automated Proof Checking  5/25/01  4:32AM
108:Finite Boolean Relation Theory   9/18/01  12:20PM
109:Natural Nonrecursive Sets  9/26/01  4:41PM
110:Communicating Minds I  12/19/01  1:27PM
111:Communicating Minds II  12/22/01  8:28AM
112:Communicating MInds III   12/23/01  8:11PM
113:Coloring Integers  12/31/01  12:42PM
114:Borel Functions on HC  1/1/02  1:38PM
115:Aspects of Coloring Integers  1/3/02  10:02PM
116:Communicating Minds IV  1/4/02  2:02AM
117:Discrepancy Theory   1/6/02  12:53AM
118:Discrepancy Theory/2   1/20/02  1:31PM
119:Discrepancy Theory/3  1/22.02  5:27PM
120:Discrepancy Theory/4  1/26/02  1:33PM
121:Discrepancy Theory/4-revised  1/31/02  11:34AM
122:Communicating Minds IV-revised  1/31/02  2:48PM
123:Divisibility  2/2/02  10:57PM
124:Disjoint Unions  2/18/02  7:51AM