FOM: 128:Finite BRT/Collapsing Triples

[Harvey Friedman]

We have been using the hypothesis "expansive linear growth". Here it is
convenient to use the slightly stronger hypothesis "expanively linearly
trapped". I.e., there exist c,d >1 such that for all x in dom(f),

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

PROPOSITION 1. Let f,g be multivariate functions from N into N that are
expansively linearly trapped. There exist infinite A,B,C containedin N such
that

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

Let A,B,C containedin N. The COLLAPSE of (A,B,C) is the triple (hA,hB,hC),
where h is the unique one-one order preserving map from A U B U C onto an
initial segment of Z+.

Eerily reminiscient of "transitive collapse" in set theory due to Godel. Is
this analogy superficial or interesting??

PROPOSITION 2. Let k,p >= 1 and f,g:N^k into N be expansively linearly
trapped. There exist finite A,B,C containedin N containing 1, such that

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

where each term in the collapse of (A,B,C) contains the first p positive
integers raised to 4k^2.

>From general considerations of compactness and finitely branching trees, we
can see that Proposition 2 is a purely finite statement (Pi-0-2). Here is
the obvious finite form.

PROPOSITION 3. Let n >> k,p >= 1 and f,g:[0,n]^k into N be expansively
linearly trapped. There exist  A,B,C containedin [0,n] containing 1, such
that

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

where each term in the collapse of (A,B,C) contains the first p positive
integers raised to 4k^2.

Proposition 2 can be stated just for expansive integral piecewise
polynomials (as multivariate functions from N into N). The resulting
Proposition is automatically a finite statement.

PROPOSITION 4. Let k,p >= 1 and f,g:N^k into N be expansive integral
piecewise polynomials. There exist finite A,B,C containedin N containing 1,
such that

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

where each term in the collapse of (A,B,C) contains the first p positive
integers raised to 4k^2.

As indicated in [1], once we move to "concrete" functions, we have the
option of requiring that A,B,C be nice. This results in purely finite
statements. This avoids the need to consider collapses of triples of sets:

PROPOSITION 5. Let f,g be expansive integral piecewise polynomials. There
exist infinite A,B,C containedin N such that

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

where A,B,C are integral piecewise linear images of double exponential
progressions in N.

In [1], I have been making explicitly hedged claims about using expansive
integral piecewise linear functions. There are some particularly delicate
complications involved.

However, these special complications are largely removed if we use

*strictly dominating N-piecewise linear functions*.

An N-piecewise linear function is a multivariate function f from N into N
which can be defined by finitely many cases, where

i) each case is given by a finite set of linear inequalities with
coefficients from N;
ii) f is defined by an affine function on each piece with coefficients from N.

The use of N instead of Z in i) makes no difference. However, it is an
essential difference in ii).

The N-piecewise linear functions are exactly the multivariate functions
from N into N given by expressions involving IF THEN ELSE, <, +.

We say that a multivariate function f from N into N is strictly dominating
if and only if for all x in dom(f), f(x) > |x|.

With confidence, we can use these functions:

PROPOSITION 6. Let f,g be strictly dominating N-piecewise linear functions.
There exist infinite A,B,C containedin N such that

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

Now consider what happens when we use the idea of Proposition 4:

PROPOSITION 7. Let k,p >= 1 and f,g:N^k into N be strictly dominating
N-piecewise linear functions. There exist finite A,B,C containedin N
containing 1, such that

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

where each term in the collapse of (A,B,C) contains the first p positive
integers raised to 4k^2.

It is easy to give an apriori exponential upper bound on the cardinalities
of A,B,C in terms of k,p. When this is done, note that the conclusion
(i.e., the existence of A,B,C, such that ...) is a statement in Presburger
arithmetic. Thus we have an explicitly Pi-0-1 statement.

We can again avoid using the collapse by dealing with the A,B,C directly:

PROPOSITION 8. Let k,p >= 1 and f,g:N^k into N be strictly dominating
N-piecewise linear functions. There exists infinite A,B,C containedin N
containing 1, such that

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

where A,B,C are integral piecewise linear images of geometric progressions
in N.

With some work, one can give a double exponential bound on the presentation
in the last line in terms of k,p. This also results in an explicitly Pi-0-1
statement.

THEOREM 9. Propositions 1,2 are provably equivalent to the 1-consistency of
MAH over RCA0. 3-5 are provably equivalent to the 1-consistency of MAH over
EFA (exponential function arithmetic). Propositions 7,8 are provably
equivalent to the consistency of MAH over EFA (exponential function
arithmetic). Proposition 6 is provably equivalent to the consistency of MAH
over RCA0. Proposition 5 without the last line is provably equivalent to
the 1-consistency of MAH over RCA0.

[1] Boolean relation theory notes,
http://www.mathpreprints.com/math/Preprint/show/

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

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

This is the 128th 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
127:Combinatorial conditions/BRT