FOM: 135:BRT/A Delta fA/A U. fA

[Harvey Friedman]

PREFACE: The claims in this particular posting represent one of the very
biggest advances in the project over the past 35 years. However, I have now
layered so many ideas for the reversals (independence proofs), one on top
of the other, that the formal manuscript is something I am very anxious to
produce. However, this successful run may not yet be over. Maybe more later
...

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

Recall the complementation theorem, which is a basic motivator for BRT
(Boolean relation theory). Here are two of many forms that is most
convenient for our discussion.

COMPLEMENTATION. Let k >= 1 and f:N^k into N be strictly dominating. There
exists A containedin N such that A Delta fA = N.

COMPLEMENTATION. Let k >= 1 and f:N^k into N be strictly dominating. There
exists A containedin N such that A U. fA = N.

Here Delta is symmetric difference.

Obviously, these are equivalent theorems since

A Delta fA = N
A U. fA = N
A = N\fA
fA = N\A

are all equivalent.

For many years, well before BRT, we have been looking for a beautiful
theorem of the following forms:

TEMPLATE. Let f:N^k into N be suitable and strictly dominating. There
exists A containedin N such that A Delta fA is "big" but not "too big".

TEMPLATE. Let f:N^k into N be suitable strictly dominating. There exists A
containedin N such that A U. fA is "big" but not "too big".

for which large cardinals are necessary and sufficient.

A strict interpretation of this Template is not promising. However,
consider these modified templates:

TEMPLATE. Let f:N^k into N be suitable and strictly dominating. There
exists A containedin N such that A Delta fA is "big relative to A" but not
"too big".

TEMPLATE. Let f:N^k into N be suitable and strictly dominating. There
exists A containedin N such that A U. fA is "big relative to A" but not
"too big".

It now appears that we are carrying out this program using piecewise linear
functions.

A k-ary piecewise linear functions (on Z) is a function f:Z^k into Z with
the following property. There is a partition of Z^k into finitely pieces,
each defined by finitely many linear inequalities with integer
coefficients, where T is an affine function with integer coefficients on
each piece.

We need the following more refined notion.

Let E containedin Z. A k-ary piecewise linear function with coefficients
from E is a function f:Z^k into Z with the following property. There is a
partition of Z^k into finitely pieces, each defined by finitely many linear
inequalities where all coefficients lie in E union {0}, and where T is an
affine function on each piece where all coefficients lie in E union {0}.

There are three particularly important special cases.

a. Coefficients from Z. These are the usual integral piecewise linear
functions.
b. Coefficients from N. These functions map N^k into N. The binary function
|x-y| is not in this class.
c. Coefficients from {1}. Here we say "with unit coefficients".

We say that any T:Z^k into Z is strictly dominating if and only if for all
x in Z^k, |T(x)| > |x|, where |x| is the sup norm of x.

*INFINITARY PROPOSITIONS*

PROPOSITION 1. Let k >= 1 and T be a strictly dominating k-ary piecewise
linear function with coefficients from N. There exists A containedin N such
that A Delta TA contains the least value on A^k of every strictly
dominating k-ary piecewise linear function with coefficients from the
factorials, yet contains only finitely many factorials.

PROPOSITION 2. Let k >= 1 and T be a strictly dominating k-ary piecewise
linear function with coefficients from N. There exists A containedin N such
that A U. TA contains the least value on A^k of every strictly dominating
k-ary piecewise lineaer function with coefficients from the factorials, yet
contains only finitely many factorials.

*FINITARY PROPOSITIONS*

PROPOSITION 3. Let k,r >= 1 and T be a strictly dominating k-ary piecewise
linear function with unit coefficients. There exists finite A containedin N
such that A Delta TA contains the least value on A^k of every strictly
dominating k-ary piecewise linear function with coefficients from the first
r factorials, yet contains at most (k+8)!! factorials.

PROPOSITION 4. Let k,r >= 1 and T be a strictly dominating k-ary piecewise
linear function with unit coefficients. There exists finite A containedin N
such that A U. TA contains the least value on A^k of every strictly
dominating k-ary piecewise linear function with coefficients from the first
r factorials, yet contains at most (k+8)!! factorials.

We don't yet have a good feel for the (k+8)!! that appears at the end.
Certainly (k+8)!! needs to be made more beautiful. We have picked a safe
expression, but intend to reduce it considerably. In any case, this will be
gone into in detail at the appropriate time, which is not now.

Note that Propositions 3-4 are explicitly Pi-0-2.

By the Presburger decision procedure, or by more direct methods, we see
that strict domination of the functions involved is a finitary attribute.
In addition, we can replace N by [0,alpha]. where alpha is a suitable
double or triple factorial expression. This results in versions of
Propositions 3 and 4 that are explicitly Pi-0-1.

*RESULTS*

THEOREM. Propositions 1-4 are each provably equivalent to the 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 135th 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  3/11/02  3:34AM
128:Finite BRT/Collapsing Triples  3/11/02  3:34AM
129:Finite BRT/Improvements  3/20/02  12:48AM
130:Finite BRT/More  3/21/02  4:32AM
131:Finite BRT/More/Correction  3/21/02  5:39PM
132: Finite BRT/cleaner  3/25/02  12:08AM
133:BRT/polynomials/affine maps  3/25/02  12:08AM
134:BRT/summation/polynomials  3/26/02  7:26PM