FOM: 126:Correction

[Harvey Friedman]

I need to change "quadratic growth" to "expansive linear growth" in
postings #124,#125. With "quadratic growth", Proposition 1 can be easily
proved in ZFC, and even in RCA0.

The origin of this oversight is as follows. In the recent earlier postings
on Boolean relation theory, before we had the disjoint union inclusion
formulations, we used "expansive linear growth" or "expansively linear
trapped".

When making postings #124,#125, I used "quadratic growth" with the idea
that this concept is slightly simpler. Slightly simpler only in the sense
that in "quadratic growth" one uses only positive constants, whereas in
"expansive linear growth", one uses constants > 1.

However, I didn't think through the consequences of making this change.
Note that "expansive linear growth" is nicely closed under composition, but
"quadratic growth" is certainly not: in fact, "quadratic growth" can be
viewed as "anticompositional". This is the source of the difference between
"quadratic growth" and "expansive linear growth".

In a later posting, we will address the issue of the proper generality of
the results in terms of growth conditions. For the moment, let it suffice
to say that we can instead use "nonlinear polynomial growth" or
"superlinear power growth". Again, these classes are nicely closed under
composition. We will return to this topic soon.

We now give the corrected self contained version of postings #124,#125.

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

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 expansive linear growth if and only if there are c,d > 1 such
that for almost all x in dom(f),

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

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].

PROPOSITION 1. For all multivariate f,g from N into N of expansive linear
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 seek to determine the truth and falsity of all statements of the
following form:

For all multivariate f,g from N into N of expansive linear growth, there
exist infinite sets A,B,C containedin N such that

X U. fY containedin V U. gW
X' U. fY' containedin V' U. gW'.

Here X,Y,V,W,X',Y',V',W' are among the three letters A,B,C. There are 3^4 =
81 such clauses, and C(81,2) + 81 such unordered pairs (including
singletons), for a total of 3240+81 = 3321 unordered pairs. We can invoke
the symmetry of A,B,C, which results in approximately 500 statements.

We have succeeded in determining the status of all such statements.

THEOREM 3. These statements fall into the following three categories:
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 3, we see that there is essentially one and only one such
statement that is independent of ZFC, and that one is reprented by the pair
displayed in Proposition 1.

We now report on an earlier classification that was discussed in the
posting 10:41PM 2/24/02. Again, this must be formulated with "expansive
linear growth" rather than "quadratic growth".

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 clauses. Thus there are 128 statements obtained
by using these sets for the conclusion of Proposition 1.

THEOREM 4. Every such statement 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 5. 46 of these 128 statements are provable in MAH+. 82 of these 128
statements are refutable in RCA0.

The classification has the following result to date:

1. 82 statements refutable in RCA0.
2. 37 statements provable in RCA0.
3. 7 statements provably equivalent to the 1-consistency of MAH over ACA.
4. 2 statemeants 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 statements are provably equivalent over RCA0.

We can also use expansively linear trapped and obtain the same results.
This means that the inequality in the definition of expansive linear growth
holds with no exceptions.

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

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
125:Disjoint Unions/First Classifications  3/1/02  6:19AM