FOM: 121:Discrepancy Theory/4-revised

[Harvey Friedman]

Here is a revised form of #120, Discrepancy Theory/4. One letter has to be
changed in the set inclusion relation.

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

I have discovered that if one, at least, temporarily, abandons the quest
for perfect symmetry, then one gets some very good compensation. This is my
current favorite:

PROPOSITION 1. For all multivariate f1,f2,f3 from N into N of quadratic
growth, there exist infinite sets A1,A2,A3 containedin N obeying the system
of inclusions

A1 containedin Ai delta fjAk containedin A3 delta f1Ak+1.

Here is a more general form.

PROPOSITION 1. For all n,m >= 1 and multivariate f1,...,fn from N into N of
quadratic growth, there exist infinite sets A1,...,Am containedin N obeying
the system of inclusions

A1 containedin Ai delta fjAk containedin Ar delta f1Ak+1.

THEOREM 2. Propositions 1 and 2 are each provably equivalent to the
1-consistency of ZFC + {there exists an n-Mahlo cardinal}n over ACA.

Note that Propoisiton 1 is clearly part of the original Boolean relation
theory (for three functions and three sets). It does not need a tower
A1,...,Am, and it does not need a notion of largeness. Further, we are
considering only inclusions of the form

U delta gV containedin W delta hX

which has nice symmetry.

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 121st 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