FOM: 142: BRT/A Delta fA/A U. fA/progress

[Harvey Friedman]

I have just realized that the single factorials are not spread apart enough
to be used as coefficients in postings 135 - 141. The double factorials are
spread apart enough.

Instead, I should be using the factorials for the constant coefficients only.

However, we have found it best to avoid using special coefficients in favor
of "specializations".

###########################################

I am still trying to run out of ideas.

This posting is self contained.

###########################################

*TEMPLATES*

We let N be the set of all nonnegative integers and Z be the set of all
integers. For x in Z^k, we write |x| for the sup norm of x, which is the
maximum of the magnitudes of the coordinates of x.

Let f:Z^k into Z. We say that f is strictly dominating if and only if for
all x in Z^k, |f(x)| > |x|. We make the same definition with Z replaced by
N.

Let A containedin Z. We let fA be the set of all values of f at arguments
from A. We make the same definition with Z replaced by N.

Delta is symmetric difference, and U. is disjoint union.

We start with the following versions of the Complementation theorem,
provable in RCA0.

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.

In fact there is a unique solution A to the set equation, and that unique
solution A is infinite.

These Theorems are obviously equivalent. In fact the following conditions
are equivalent for A,B containedin N.

A Delta B = N
A U. B = N
A = N\B
B = N\A.

We now have the following templates.

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

TEMPLATE. Let k >= 1 and f:N^k into N be strictly dominating and suitable.
There exists A containedin N such that A U. fA is "big".

But we have already made A Delta fA and A U. fA as "big" as possible. What
we really want is this.

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

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

It turns out that this plan is not promising, taken literally. However,
consider the following modified templates.

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

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

We endeavor to arrange that it is necessary and sufficient to use large
cardinals (or equivalent) to prove these statements.

Note that The Complementation Theorem gives us a nonempty A containedin N
such that A Delta fA and A U. fA are "big relative to A". However it is so
"big relative to A" that it is "too big", and so does not satisfy Templates
1,2.

There are two closely related Templates that we also work with.

TEMPLATE 3. Let k >= 1 and f:N^k into N be strictly dominating and suitable.
There exists "large" A containedin N such that A Delta fA is "big relative
to A".

TEMPLATE 4. Let k >= 1 and f:N^k into N be strictly dominating and suitable.
There exists "large" A containedin N such that A U. fA is "big relative to A".

The Complementation Theorem does meet Templates 3,4 with "large" being
"infinite" and "big relative to A" being "equal to N". So the plan is to
strengthen the notion of "large" and weaken the notion of "bit relative to
A".

We have apparently succeeded in carrying this out - i.e., finding natural
instances of Templates 1-4 for which it is necessary and sufficient to
use large cardinals (or equivalent).

*LINEAR NOTATION*

A piecewise linear transformation over Z is a function of the form T:Z^k
into Z such that
there is a partition of Z^k into finitely many pieces, where each piece
given by a finite set of linear inequalities with integer coefficients, and
where f agrees with an affine function with integer coefficients on each
piece.

A piecewise linear transformation over N is a piecewise linear function
over Z that can be presented as in the previous paragraph with only
coefficients from N.

The nonnegativity of the coefficients has a major effect on the affine
functions, but no effect on the linear inequalities. This is because
shifting terms from one side to the other in linear inequalities has the
effect of taking negatives of coefficients.

The norm of a presentation of a piecewise linear transformation is the sum
of the arity and the absolute values of all coefficients that appear
throughout the presentation (duplicates counted).

The norm of a piecewise linear transformation is the least norm of any of
its presentations. We write |T| for the norm of the piecewise linear
transformation T.

Using the Presburger decision procedure, or more direct methods, one can
effectively pass from any presentation to a presentation of minimum norm.
So one can effectively determine the norm of any piecewise linear
transformation from any of its presentations. In addition, one can
effectively determine whether any given piecewise linear transformation is
a piecewise linear transformation with nonnegative coefficients from any
presentation of the piecewise linear transformation using the Presburger
decision procedure, or more direct methods. The same effectivity holds for
"strictly dominating".

The specializations of T by integers r1,...,rt are the functions obtained
from T by fixing zero or some or all of the arguments to be among
r1,...,rt. Note that if we fix all of the arguments then we get a 0-ary
function. This allows us to avoid saying "nonempty" in Propositions 5 and
6.

*INFINITARY PROPOSITIONS*

PROPOSITION 1. Let  S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists A containedin N such that A Delta TA
contains the least value over A of every specialization of S by the
infinitely many factorials that lie in A.

PROPOSITION 2. Let  S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists A containedin N such that A U. TA
contains the least value over A of every specialization of S by the
infinitely many factorials that lie in A.

We can sharpen these as follows.

PROPOSITION 3. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists A containedin N such that A Delta TA
contains the least value over A of every specialization of S by the
factorials, almost all of the latter lying in A.

PROPOSITION 4. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists A containedin N such that A U. TA
contains the least value over A of every specialization of S by the
factorials, almost all of the latter lying in A.

Propositions 1-4 conform to Templates 3,4.

*FINITARY PROPOSITIONS*

PROPOSITION 5. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists finite A containedin N such that the
least value over A of every specialization of S by 1!,2!,...,n! lies in A
Delta TA without (|S|+|T|+8)!!!-1.

PROPOSITION 6. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists finite A containedin N such that the
least value over A of every specialization of S by 1!,2!,...,n! lies in A
U. TA without (|S|+|T|+8)!!!-1.

PROPOSITION 7. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists finite A containedin N such that A
Delta TA contains the least value over A of every specialization of S by
1!,2!,...,n!, but not (|S|+|T|+8)!!!-1.

PROPOSITION 8. Let S,T be piecewise linear transformations over N, where T
is strictly dominating. There exists finite A containedin N such that A U.
TA contains the least value over A of every specialization of S by
1!,2!,...,n!, but not (|S|+|T|+8)!!!-1.

Propositions 7,8 conform to Templates 1,2.

We can confrom to Templates 3,4 as follows.

PROPOSITION 9. Let k,n >= 1 and T be a strictly dominating k-ary piecewise
linear function over N. There exists finite A containedin N including
(|S|+|T|+8)!!!, such that A Delta TA contains the least value over A of
every specialization of S by 1!,2!,...,n!.

PROPOSITION 10. Let k,n >= 1 and T be a strictly dominating k-ary piecewise
linear function over N. There exists finite A containedin N including
(|S|+|T|+8)!!!, such that A U. TA contains the least value over A of every
specialization of S by 1!,2!,...,n!.

These are very conservative with the (|S|+|T|+8)!!! and (|S|+|T|+8)!!!-1
and when things settle down, I
will see what number is really needed.

We know that the mere existence of a function of k so that any of these
Propositions holds requires large cardinals (or equivalent) to prove.

Note that if we remove "including ..." or "without ..." then the
Propositions are easily provable in EFA.

THEOREM. Propositions 1-10 are each provably equivalent to the consistency
of MAH over ACA.

Speaking of Presburger, the results hold even if we replace "piecewise
linear" with "Presburger".

NOTE: MAH is ZFC + {there exists a k-Mahlo cardinal}_k. ACA is the system
of arithmetic comprehension with full induction. For the former see, e.g.,
Aki Kanamori's book "The Higher Infinite". For the latter, see Stephen G.
Simpson's book on Reverse Mathematics (SOSOA).

*COMPARISON WITH DISJOINT UNION INCLUSION WORK*

How do these results fit in to the development of Boolean relation theory?

The results here are quite different than the earlier clear milestone
reached in Posting # 126, Sat, 9 Mar 2002 02:10:12. The results in #126
were the subject of the "beautiful" reactions I reported, with the
classification of the 81^2 pairs of clauses. There one has a "beautiful"
category of statements, no one of which is especially natural, but where
only one, up to symmetry, is independent of ZFC.

The results in this posting is an attempt to do two things at once:

a) to give explicitly finite independence results;
b) to give a single statement that conveys specific interseting or
intriguing or otherwise notable information.

Obviously neither #126 nor #142 is yet obsolete.

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

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

This is the 142nd 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
135:BRT/A Delta fA/A U. fA  3/27/02  5:45PM
136:BRT/A Delta fA/A U. fA/nicer  3/28/02  1:47AM
137:BRT/A Delta fA/A U. fA/beautification  3/28/02  4:30PM
138:BRT/A Delta fA/A U. fA/more beautification  3/28/02  5:35PM
139:BRT/A Delta fA/A U. fA/better  3/28/02  10:07PM
140:BRT/A Delta fA/A U. fA/yet better
141:BRT/A Delta fA/A U. fA/grammatical improvement