FOM: 127:Combinatorial condition/BRT

[Harvey Friedman]

We present two combinatorial conditions for Proposition 1 of posting
#126:Correction, 2:10AM  3/9/02. There we used "expansive linear growth".

This combinatorial condition is easily verified in every case I know is
sufficient for Proposition 1 in #126 to be provable in MAH+.

We wish to thank Misha Gromov for asking for a combinatorial condition in
connection with Proposition 1 in #126..

Let f,g be multivariate functions from N into N and A containedin N. We
define the f,g,<=n terms as follows.

i) every i in [0,n] is an f,g,<=n term;
ii) if s1,...,sp and t1,...,tq are f,g,<=n terms then so are the
expressions f(s1,...,sp) and g(t1,...,tq).

Here p is the arity of f and q is the arity of g. The length of an f,g,<=n
term is the total number of f's, g's, and integers that appear.

Obviously every f,g,<=n term has a well defined value since f,g are actual
functions of arities p,q.

PROPOSITION 1. Let f,g be multivariate functions from N into N. Assume that
for all n,r >> k >= 1, no f,g,<=n term with r n's has the same value as an
f,g,<=n term of length at most k. There exist infinite A,B,C containedin N
such that
A U. fA containedin C U. gB
A U. fB containedin C U. gC.

We define the upper and lower traces of f, U(f),L(f):N into N, by

U(f)(n) = max{f(x): |x| <= n}, L(f)(n) = min{f(x): |x| <= n}.

As usual, |x| is the sup norm of x.

We say that f is eventually strictly dominating if and only if there exists
c > 0 such that for all x in dom(f), if |x| >= c then f(x) > |x|.

PROPOSITION 2. Let f,g be multivariate functions from N into N, where
i) f,g are eventually strictly dominating;
ii) U(f) is eventually strictly dominated by an iterate of L(g);
iii) U(g) is eventually strictly dominated by an iterate of L(f).
There exist infinite A,B,C containedin N such that
A U. fA containedin C U. gB
A U. fB containedin C U. gC.

These Propositions do not cover all of the interesting cases where we know
the conclusion in question to be true using MAH+, and in fact where the
statement is provably equivalent to the 1-consistency of MAH over ACA.
These additional interesting cases are amenable to a more subtle abstract
treatment such as what we have given. We don't have the time right now to
polish and report on this additional work.

Here are some cases which are covered. Make the following definitions for a
multivariate function f from N into N.

f is of expansive linear growth if and only if there exists c,d,e > 1 such
that for all x in dom(f), if |x| >= e then c|x| <= f(x) <= d|x|.

f is expansively power like if and only if there exists c,d,e > 1 such that
for all x in dom(f), if |x| >= e then |x|^c <= f(x) <= |x|^d.

f is compound exponential like if and only if there exists n,m,r in Z+ such
that for all x in dom(f), if |x| >= r then 2^[n](|x|) <= f(x) <=
2^[m](|x|), where 2^[n] indicates iterated exponentiation.

f has nonlinear polynomial growth if and only if there exists an integer n
> 1 and c,d,e > 0 such that for all x in dom(f), if |x| >= e then c|x|^n <=
f(x) <= d|x|^n.

f has expansive power growth if and only if there exist c,d,e > 0 and r > 1
such that for all x in dom(f), if |x| >= e then c|x|^r <= f(x) <= d|x|^r.

1. f,g are of expansive linear growth.

2. f,g are expansively power like.

3. f,g are compound exponential like.

4. f,g have expansive power growth.

THEOREM 3. Propositions 1 and 2, as well as if any of 1-4 above are used,
are provably equivalent to the 1-consistency of MAH over ACA.

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

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

This is the 127th 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
126:Correction  3/9/02  2:10AM