[FOM] 415: Integer Decomposition Theory 2
Harvey Friedman
friedman at math.ohio-state.edu
Sat Apr 24 15:42:34 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/014608.html
We saw a number of serious advantages to moving to one dimension.
One feature I very much wanted to keep was the explicitly Pi01 versions.
However, now I have lost confidence that the stuff in http://www.cs.nyu.edu/pipermail/fom/2010-April/014608.html
is Pi01 instead of Pi02.
I have to look at the details carefully to see if we get Pi02 and high
growth rates - and not Pi01. So at the moment I will leave this up in
the air, but get back to it in a couple of months or so.
In the meantime, I have found explicitly Pi01 forms in one dimension
that are very satisfactory.
So we will start from the beginning again. This corrects and
supersedes http://www.cs.nyu.edu/pipermail/fom/2010-April/014608.html
INTEGER DECOMPOSITION THEORY 2
by
Harvey M. Friedman
April 24, 2010
1. RESTRICTED DECOMPOSITION.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
5. INFINITARY DECOMPOSITION THEOREMS.
6. FINITARY DECOMPOSITION THEOREMS.
7. SYMMETRY, SIZE, AND HEIGHT.
8. EXPLICITLY PI01 THEOREMS.
1. RESTRICTED DECOMPOSITION.
We use N for the set of all nonnegative integers. Every n in N can be
decomposed as
n = m_1 + ... + m_k
where m_1,...,m_k are nonnegative integers other than n.
In restricted decomposition, we use a restriction on (m_1,...,m_k).
Thus we define an ADDITION FUNCTION as a PARTIAL function f:N^k into N
such that for all x in dom(f),
f(x) is the sum of the coordinates of x, none of which are x.
Obviously, addition functions are entirely determined by their domain.
A basis for an addition function f:N^k into N is a set A contained in
N such that
i. Every n in N is either in A or is the value of f at arguments from A.
ii. No element of A is the value of f at arguments from A.
THEOREM 1.1. Every addition function has a unique basis. The unique
basis is infinite.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
We now give the Rudimentary Decomposition Construction, which
constructs the unique basis in the most straightfoward way.
Let f:N^k into N be an addition function. We inductively define sets
A_0,... as follows.
A_0 = emptyset.
For i >= 0, A_i+1 = A_i union {i} if i is not the value of f at
arguments from A_i; A_i otherwise.
THEOREM 2.1. In the Rudimentary Decomposition Construction for any
addition function, the union of the A's is its unique basis.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
We give the alternative Constrained Decomposition Construction. We
prove that this results in the same sequence of sets.
Let f:N^k into N be an addition function. 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 some y_1,...,y_k into A_i+1, where i =
f(y_1,...,y_k).
CONSTRAINT: No element of A is the value of f at arguments from A. We
consider the construction of A_i+1 to be completed if and only if A_i
+1 satisfies the constraint.
THEOREM 3.1. In the Constrained Decomposition Construction, any
y_1,...,y_k 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
Decomposition Construction are the same as the sets A_i in the
Rudimentary Decomposition Construction.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
Let f:N^k into N be an addition function.
In the Rudimentary and Constrained 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 - not just 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 some
y_1,...,y_k into A_i+1, where x = f(y_1,...,y_k).
CONSTRAINT: No element of A is the value of f at arguments from A. We
consider the construction of A_i+1 to be completed if and only if A_i
+1 satisfies the constraint.
Note that this construction is, in general, truly accelerated over the
Constrained 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" instead of "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 Decomposition
Construction of infinite length must be the unique basis.
COROLLARY 4.2. Any Accelerated Decomposition Construction that starts
with a set with elements outside the unique basis, must be of finite
length.
5. INFINITARY DECOMPOSITION THEOREMS.
The general problem under consideration is this. Suppose we are
willing to give up on infinite length Accelerated Decomposition, in
light of Theorem 4.1 and Corollary 4.2. Suppose we focus on length r
Accelerated Decomposition.
Let f:N^k into N be an addition function. We want to give information
on the initial set A_0 of Accelerated Decomposition Constructions for
f, 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 begin with two obvious facts.
THEOREM 5.1. Every Addition Function has an Accelerated Decomposition
Construction of infinite length starting with an infinite set.
THEOREM 5.2. The possible starting sets of Accelerated Decomposition
Constructions of length r for a given Addition Function, are closed
under inclusion.
PROPOSITION 5.3. Every Addition Function has an Accelerated
Decomposition Construction of length r starting with an infinite set
of even integers.
There is a more general form of Proposition 5.2.
PROPOSITION 5.4. Every Addition Function has an Accelerated
Decomposition Construction of length r starting with some infinite
subset of any given infinite subset of N.
Still more generally,
PROPOSITION 5.5. Let an Addition Function and infinite sets E_1,...
contained in N be given. There is an Accelerated Decomposition
Construction of length r 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.
A basic subset of N^k is a subset of N^k that is the solution set to a
finite system of linear inequalities with integer coefficients.
A PL (piecewise linear) subset of N^k is a finite union of basic
subsets of N^k.
A Basic Addition Function is an Addition Function whose domain is basic.
A PL Addition Function is an Addition Function whose domain is PL.
We start with the infinite form.
PROPOSITION 6.1. Every Basic (PL) Addition Function has a length r
Accelerated Decomposition Construction starting with p,p^2,...,
provided p is sufficiently large relative to r and the Addition
Function.
PROPOSITION 6.2. Every Basic (PL) Addition Function has a length r
Accelerated Decomposition Construction starting with p,p^2,...,p^t,
provided p,t are sufficiently large relative to r and the Addition
Function.
Obviously Proposition 6.1 is explicitly Pi02.
THEOREM 6.3. Propositions 6.1, 6.2 are provable in SMAH+ but not in any
consequence of SMAH consistent with EFA. Propositions 6.1, 6.2 imply
Con(SMAH) over EFA, and follow from 1-Con(SMAH) over EFA.
Here EFA is exponential function arithmetic.
7. SYMMETRY, SIZE, AND HEIGHT.
Let A_0,...,A_r be an accelerated decomposition construction for a k-
ary Addition Function.
The size is the cardinality of A_0.
The height is the number of elements of A_r less than all elements of
A_0.
Symmetric if and only if for all 1 <= i <= k, A_r includes all or none
of the nonrepeating i sums from A_0. The height is the number of
elements of A_r that are less than all elements of A_0.
We like symmetric accelerated decomposition constructions of large
size and small height.
8. EXPLICITLY Pi01 THEOREMS.
PROPOSITION 8.1. Every k-ary (Basic, PL) Addition Function has a
symmetric infinite size length r height (8kr)!! Accelerated
Decomposition Construction.
PROPOSITION 8.2. Every k-ary (Basic, PL) Addition Function has a
symmetric p size length r height (8kr)!! Accelerated Decomposition
Construction.
Note that Proposition 8.2 with Basic or PL is explicitly Pi02.
However, because of the well known decision procedure for linear
integer arithmetic (due originally to Presburger), we see that
Proposition 8.2 with Basic or PL is Pi01. Alternatively, we can simply
bound the numbers where the Accelerated Decomposition Construction
lives as a double factorial in k,p,r, and the largest magnitude of the
coefficients used to present the Addition Function.
PROPOSITION 8.3. Propositions 8.1, 8.2 (all four forms) are provable
in SMAH+ but not in any consequence of SMAH consistent with ACA'.
Propositions 8.1, 8.2 (all four forms) are provably equivalent to
Con(SMAH) over ACA'. We can use RCA_0 for Proposition 8.2, and EFA for
Proposition 8.2 with Basic or PL.
**********************
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
Harvey Friedman
More information about the FOM
mailing list