FOM: 135:BRT/A Delta fA/A U. fA
Harvey Friedman
friedman at math.ohio-state.edu
Wed Mar 27 17:45:43 EST 2002
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
More information about the FOM
mailing list