[FOM] 416: Integer Decomposition Theory 3
Harvey Friedman
friedman at math.ohio-state.edu
Mon Apr 26 16:43:27 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
**********************************************************************
This is a follow up to http://www.cs.nyu.edu/pipermail/fom/2010-April/014620.html
There seem to be a number of breakthrough ideas, some expositional,
some more substantive.
There is no reason to actually form an Addition Function. We need only
talk about "decomposition subject to a condition", or "conditional
decomposition".
There are some new infinite versions, including versions based on
integral piecewise linear sets. These are explicitly arithmetical, or
arithmetical using a finitely branching tree argument.
We did lose the Pi01 character as indicated in http://www.cs.nyu.edu/pipermail/fom/2010-April/014620.html
and we had to use "symmetry and height" which is still fairly good.
However, we lose the very attractive idea of just talking about what's
in the first set.
So we made a determined search to get as close as we can to "what's in
these sets" rather than regularity conditions - AND still have Con
instead of 1-Con, and explicit Pi01 statements.
We do have something very good for this now. We just have to say that
the first set is a "suitably tame subset" of the the intersection of
the last set with 2N. No regularity condition is needed on the sets.
We do, however, need to assume that the data is integral piecewise
linear.
The easiest to read is Proposition 5.3.
The explicitly Pi01 sentence is Proposition 8.1.
This posting is self contained.
INTEGER DECOMPOSITION THEORY 3
by
Harvey M. Friedman
April 26, 2010
1. CONDITIONAL DECOMPOSITION.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
5. INFINITARY DECOMPOSITION THEOREMS.
6. FINITE DECOMPOSITION THEOREMS.
7. INFINITARY PL DECOMPOSITION THEOREMS.
8. FINITARY PL DECOMPOSITION THEOREMS.
9. REMARK.
1. CONDITIONAL DECOMPOSITION.
We use N for the set of all nonnegative integers. A decomposition of n
in N takes the form
n = m_1 + ... + m_k
where m_1,...,m_k are nonnegative integers < n.
Let E be contained in N^k. An E decomposition of n in N takes the form
n = m_1 + ... + m_k are nonnegative integers < n, where (m_1,...,m_k)
lies in E.
An E decomposition of n in N is said to be from A contained in N if
and only if each of its k summands lies in A.
A basis for E decomposition is a set A contained in N such that
i. Every n in N is either in A or has an E decomposition from A (i.e.,
using only integers from A).
ii. No element of A has an E decomposition from A.
THEOREM 1.1. Any E decomposition has a unique basis. The unique basis
is infinite.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
We now give the Rudimentary E Decomposition Construction, which
constructs the unique basis in the most straightfoward way.
Let E be contained in N^k. We inductively define sets A_0,... as
follows.
A_0 = emptyset.
For i >= 0, A_i+1 = A_i union {i} if i does not have an E
decomposition from A_i; A_i otherwise.
THEOREM 2.1. In the Rudimentary E Decomposition Construction for any
E decomposition, the union of the A's is its unique basis.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
We give the alternative Constrained E Decomposition Construction. We
prove that this results in the same sequence of sets.
Let E contained in N^k. We inductively define sets A_0,... as follows.
Set A_0 = emptyset.
For i >= 0, first throw the elements of A_i into A_i+1. Then either
throw i into A_i+1, or throw the summands of some E decomposition of i
into A_i+1.
CONSTRAINT: No element of A has an E decomposition from A.
We consider the construction of A_i+1 to be finished if and only if A_i
+1 satisfies the constraint.
THEOREM 3.1. In the Constrained E Decomposition Construction, any
summands thrown into A_i+1 during the process of constructing A_i+1 as
above, must already lie in A_i. The sets A_i in any Constrained E
Decomposition Construction are the same as the sets A_i in the
Rudimentary E Decomposition Construction.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
Let E contained in N^k.
In the Rudimentary and Constrained E Decomposition Constructions, we
process the integer i at stage i+1. In the Accelerated Decomposition
Construction, we accelerate the processing of integers. We will
consider one form of Accelerated Decomposition.
Set A_0 to be any subset of N - no longer required to be the empty set.
For i >= 0, first throw the elements of A_i into A_i+1. Then for each
x in (A_i + A_i) union {i}, either throw x into A_i+1, or throw the
summands of some E decomposition of x into A_i+1.
CONSTRAINT: No element of A has an E decomposition from A.
We consider the construction of A_i+1 to be finished if and only if A_i
+1 satisfies the constraint.
Note that the Accelerated E Decomposition Construction is, in general,
truly accelerated over the
Constrained E Decomposition Construction, since, in general, A_0 is
nonempty, i gets processed at stage i+1, and more than just i gets
processed at stage i+1.
In the construction of A_i+1, we can process the x in (A_i + A_i)
union {i} in numerical order - although this is not important.
NOTE: We have used (A_i + A_i) union {i} because we are "accelerating"
over the usual construction. However, we could use A_i + A_i instead,
and we would get the same independence results - except that we have
to use "odd" and not "even" in Propositions 5.3. This will certainly
be covered in the manuscript - including an analysis of what we can
use. We would, however, lose the background results Theorem 4.1,
Corollary 4.2.
THEOREM 4.1. The union of the sets in any Accelerated E Decomposition
Construction of infinite length must be the unique basis for E
decomposition.
COROLLARY 4.2. Any Accelerated E Decomposition Construction that
starts with a set with elements outside the unique basis for E
decomposition, must be of finite length.
5. INFINITARY DECOMPOSITION THEOREMS.
Let E contained in N^k. We want to give information on the initial set
A_0 of an Accelerated E Decomposition Construction, of length r.
If the construction builds exactly the sets A_0,...,A_r, then we say
that the construction is of length r. We are allowed to abort the
construction at any stage.
We begin with two obvious facts. In 5.1 - 5.5, E is an arbitrary
subset of N^k, where k is an arbitrary positive integer.
THEOREM 5.1. There is an Accelerated E Decomposition Construction of
infinite length starting with an infinite set.
THEOREM 5.2. The possible starting sets for Accelerated E
Decomposition Constructions of length r are closed under inclusion.
PROPOSITION 5.3. There is an Accelerated E Decomposition Construction
of any given finite length starting with an infinite set of even (odd)
integers.
There is a more general form of Proposition 5.3.
PROPOSITION 5.4. There is an Accelerated E Decomposition Construction
of any given finite length starting with some infinite subset of any
given infinite subset of N.
Still more generally,
PROPOSITION 5.5. Let infinite sets E_1,... contained in N be given.
There is an Accelerated E Decomposition Construction of any given
finite length starting with some set that has infinite intersection
with every E_j.
THEOREM 5.6. Propositions 5.3 - 5.5 are provable in SMAH+ but not in
any consequence of SMAH consistent with RCA_0. Propositions 5.3 - 5.5
imply Con(SMAH) over ACA', and follow from 1-Con(SMAH) over ACA'.
Here SMAH+ = ZFC + "for all k there exists a strongly k-Mahlo
cardinal". SMAH = ZFC + {there exists a strongly k-Mahlo cardinal"_k.
ACA' is ACA_0 + "for all n in N and x contained in N, the n-th
Turing jump of x exists".
6. FINITARY DECOMPOSITION THEOREMS.
Let A contained in N. We say that B is a p-tame subset of A if and
only if the number of elements in B less than any given x in A is at
most p to the number of elements in A less than x.
Here is a sharper form of Proposition 5.3.
PROPOSITION 6.1. For all E contained in N^k, there is an Accelerated E
Decomposition Construction of length k, where A_0 contained in 2N is
an infinite (8k)!! tame subset of A_k.
Now for the semi finite form. Note that any Accelerated E
decomposition Construction starting with a finite set, must consist of
finite sets.
PROPOSITION 6.2. For all E contained in N^k, there is an Accelerated E
Decomposition Construction of length k, where A_0 contained in 2N is
an r element (8k)!! tame subset of A_k.
Now for the Pi02 form. We give two forms.
PROPOSITION 6.3. For all k,r there exists t such that the following
holds. For all E contained in {0,...,t}^k, there is an Accelerated E
Decomposition Construction of length k, where A_0 contained in
{0,2,4,...,2t} is an r element (8k)!! tame subset of A_k.
The expression (8k)!! is just safe and convenient, and are far higher
than what is needed. We will be more frugal at a later time.
THEOREM 6.4. Propositions 6.1 - 6.3 are provable in SMAH+ but not in
any consequence of SMAH consistent with RCA_0. Propositions 6.1 - 6.3
imply Con(SMAH) over ACA', and follow from 1-Con(SMAH) over ACA'.
Here EFA is exponential function arithmetic.
7. INFINITARY PL DECOMPOSITION THEOREMS.
Here we assume that E is an integral piecewise linear (PL) subset of
N^k, with integer coefficients. We view this as a subset of R^k
intersected with N^k. These are Boolean combinations of half planes.
We also use the more restricted class of basic subsets of N^k, which
is the solution set in N^k of a finite set of linear inequalities with
integer coefficients.
We can use rational coefficients throughout without changing the
results.
PROPOSITION 7.1. Let E contained in N^k be integral piecewise linear
(basic). There is an Accelerated E Decomposition Construction of
length k starting with all sufficiently large powers of 2 (the powers
of some p in N, the powers of any sufficiently large p in N).
Furthermore, we can arrange that the k sets are each the image of some
integral piecewise linear function of the starting set.
Note that the forms of Proposition 6.1 with the "furthermore" are all
explicitly arithmetical. They can be easily seen to be in Pi02 form
using the decision procedures for exponential Presburger arithmetic.
The statement before "furthermore" can also be seen to be
arithmetical, using a finitely branching tree argument.
THEOREM 7.2. Proposition 7.1 (all forms) are provable in SMAH+ but not
in any consequence of SMAH consistent with RCA_0. Proposition 7.1 (all
forms) implies Con(SMAH) over RCA_0, and follows from 1-Con(SMAH) over
RCA_0.
8. FINITARY PL DECOMPOSITION THEOREMS.
PROPOSITION 8.1. Let E contained in N^k be piecewise linear (basic),
and r >= 1. There is an Accelerated E Decomposition Construction of
length k, where A_0 contained in 2N is an r element (8k)!! tame subset
of A_k.
Obviously, Proposition 8.1 is explicitly Pi02. However, using the well
known decision procedure for linear integer arithmetic, it is
immediate that Proposition 8.1 is Pi01.
We can add a bound to make this explicitly Pi01 as follows.
PROPOSITION 8.2. Let E contained in N^k be piecewise linear (basic)
with coefficients of magnitude at most p, and r >= 1. There is an
Accelerated E Decomposition Construction of length k, where A_0
contained in {0,2,4,...,(8kpr)!!!} is an r element (8k)!! tame subset
of A_k.
THEOREM 8.3. Propositions 8.1, 8.2 are provable in SMAH+ but not in
any consequence of SMAH consistent with EFA. Propositions 8.1, 8.2 are
provably equivalent to Con(SMAH) over ACA'.
9. REMARK.
For more detailed study, it is appropriate to add a parameter m for
the length of the Accelerated E Decomposition Constructions throughout.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 415th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-349 can be found athttp://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.
350: one dimensional set series 7/23/09 12:11AM
351: Mapping Theorems/Mahlo/Subtle 8/6/09 10:59PM
352: Mapping Theorems/simpler 8/7/09 10:06PM
353: Function Generation 1 8/9/09 12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1 8/9/09 6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2 8/10/09 6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem 8/14/09 9:31AM
357: HIGH SCHOOL Games/Update 8/20/09 10:42AM
358: clearer statements of HIGH SCHOOL Games 8/23/09 2:42AM
359: finite two person HIGH SCHOOL games 8/24/09 1:28PM
360: Finite Linear/Limited Memory Games 8/31/09 5:43PM
361: Finite Promise Games 9/2/09 7:04AM
362: Simplest Order Invariant Game 9/7/09 11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1 9/24/09 1:06PM
366: Free Reductions and Large Cardinals/polished 9/28/09 2:19PM
367: Upper Shift Fixed Points and Large Cardinals 10/4/09 2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction 10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement 10/29/09 2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09 12:14PM
371: Vector Reduction and Large Cardinals 11/21/09 1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09 5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals 12/7/09 9:17AM
374: Upper Shift Greedy Chain Games 12/12/09 5:56AM
375: Upper Shift Clique Games and Large Cardinals 1graham
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09 2:23PM
377: The Polynomial Shift Theorem 12/25/09 2:39PM
378: Upper Shift Clique Sequences and Large Cardinals 12/25/09 2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems 12/28/09 7:06AM
381: Trigonometric Shift Theorem 12/29/09 11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals 12/30/09 2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09 3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION 12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences 1/1/10 7:35PM
386: Terrifically and Extremely Long Finite Sequences 1/1/10 7:35PM
387: Better Polynomial Shift Translation/typos 1/6/10 10:41PM
388: Goedel's Second Again/definitive? 1/7/10 11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1 2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2 2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3 2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4 2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5 2/22/10
3:50AM
394: Free Reduction Theory 1 3/2/10 7:30PM
395: Free Reduction Theory 2 3/7/10 5:41PM
396: Free Reduction Theory 3 3/7/10 11:30PM
397: Free Reduction Theory 4 3/8/10 9:05AM
398: New Free Reduction Theory 1 3/10/10 5:26AM
399: New Free Reduction Theory 2 3/12/10 9:36AM
400: New Free Reduction Theory 3 3/14/10 11:55AM
401: New Free Reduction Theory 4 3/15/10 4:12PM
402: New Free Reduction Theory 5 3/19/10 12:59PM
403: Set Equation Tower Theory 1 3/22/10 2:45PM
404: Set Equation Tower Theory 2 3/24/10 11:18PM
405: Some Countable Model Theory 1 3/24/10 11:20PM
406: Set Equation Tower Theory 3 3/25/10 6:24PM
407: Kernel Tower Theory 1 3/31/10 12:02PM
408: Kernel tower Theory 2 4/1/10 6:46PM
409: Kernel Tower Theory 3 4/5/10 4:04PM
410: Kernel Function Theory 1 4/8/10 7:39PM
411: Free Generation Theory 1 4/13/10 2:55PM
412: Local Basis Construction Theory 1 4/17/10 11:23PM
413: Local Basis Construction Theory 2 4/20/10 1:51PM
414: Integer Decomposition Theory 4/23/10 12:45PM
415: Integer Decomposition Theory 2 4/24/10 3:49PM
Harvey Friedman
More information about the FOM
mailing list