FOM: 119:Discrepancy Theory/3
Harvey Friedman
friedman at math.ohio-state.edu
Tue Jan 22 17:27:39 EST 2002
I have been using too strong a notion of largeness in postings in #117 and
#118. I have been using
1. Arbitrarily long runs in subsets of N.
2. Positive upper density in subsets of N.
3. Upper density 1 in subsets of N.
These have a much stronger flavor than the old standby of Boolean relation
theory: bi-infinite subsets of Z.
The appropriate notion of largeness for discrepancy theory seems to be:
*containing infinitly many 16 point intervals*
where subsequent investigation will reveal how much 16 can be lowered.
Certainly 16 can be raised to any specific positive integer. (An interval
in N is just a set of consecutive elements of N).
The first Proposition is in the style of posting #118, correcting earlier
versions.
PROPOSITION A. Let f,g,h be multivariate functions from N into N that are
expansively trapped (expansive linear growth, quadratic growth, etcetera).
There exist A containedin B containedin C containedin N containing
infinitely many 16 point intervals, such that the 9 element discrepancy
poset contains a copy of the inverted tree
*
/ | \
* * *
/ | \
* * *
Things simplify nicely if we involve the Boolean combinations of the 3 sets
as follows. Note the symmetry.
PROPOSITION B. Let f,g,h be multivariate functions from N into N that are
expansively trapped (expansive linear growth, quadratic growth, etcetera).
There exist nonempty A,B,C containedin N whose nonempty Boolean
combinations each contain infinitely many 16 point intervals, such that the
9 element discrepancy poset contains a copy of the inverted tree
*
/ | \
* * *
/ | \
* * *
Here is a more general statement. Note the symmetry.
PROPOSITIOIN C. Let n,m,r >= 1 and f1,...,fn be multivariate functions from
N into N that are expansively trapped (expansive linear growth, quadratic
growth, etcetera). There exist A1,...,Am containedin N whose nonempty
Boolean combinations each contain infinitely many r point intervals, such
that the nm element discrepancy poset contains a copy of the inverted tree
with exactly m levels, where in each of the upper m-1 levels, one vertex
sits above exactly n immediate predecessors, and the remaining vertices are
minimal.
THEOREM. Propositions A,B,C are provably equivalent to the 1-consistency of
ZFC + {there exists an n-Mahlo cardinal}_n over ACA.
We can get away without saying that the A's are nonempty here but not in
Proposition B.
Note that the inverted tree in Proposition C for n = m = 3 is the same as
the one diagrammed in Propositions A,B.
**********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 118th 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
More information about the FOM
mailing list