[FOM] 417: Integer Decomposition Theory 4
Harvey Friedman
friedman at math.ohio-state.edu
Wed Apr 28 00:01:30 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
**********************************************************************
The notion of Integer Decomposition I have been using seems to be too
strict, and so I must do something more general. Fortunately, this
reads as a simple change.
Specifically, we can view any f:N^k into N as a "notion of
decomposition". I.e., n is "decomposed" by
n = f(m_1,...,m_k)
provided 0 <= m_1,...,m_k < n.
So we will updates Integer Decomposition Theory 3 http://www.cs.nyu.edu/pipermail/fom/2010-April/014646.html
accordingly.
The easiest to read is Proposition 5.3.
The Pi01 sentences are Propositions 8.1, 8.2.
This posting is self contained.
INTEGER DECOMPOSITION THEORY 4
by
Harvey M. Friedman
April 27, 2010
1. DECOMPOSITION AND BASES.
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. DECOMPOSITION AND BASES.
Let f:N^k into N. An f decomposition of n in N takes the form
n = f(m_1,...,m_k)
where 0 <= m_1,...,m_k < n. THe "arguments" of the f decomposition are
m_1,...,m_k.
An f decomposition of n in N is said to be from A contained in N if
and only if each of the k arguments lies in A.
A basis for f decomposition is a set A contained in N such that
i. Every n in N is either in A or has an f decomposition from A.
ii. No element of A has an f decomposition from A.
THEOREM 1.1. Any f decomposition has a unique basis. The unique basis
is infinite.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
We now give the Rudimentary f Decomposition Construction, which
constructs the unique basis in the most straightfoward way.
Let f:N^k into N. We inductively define sets A_0,... as follows.
A_0 = emptyset.
For i >= 0, A_i+1 = A_i if i has an f decomposition from A_i; A_i
union {i} otherwise.
THEOREM 2.1. In the Rudimentary f Decomposition Construction, the
union of the A's is its unique basis.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
We give the alternative Constrained f Decomposition Construction. We
prove that this results in the same sequence of sets.
Let f:N^k into N. 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 arguments of some f decomposition of i
into A_i+1.
CONSTRAINT: No element of A has an f 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 f Decomposition Construction, any
arguments 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 f
Decomposition Construction are the same as the sets A_i in the
Rudimentary f Decomposition Construction.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
Let f:N^k into N.
In the Rudimentary and Constrained f 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
arguments of some f decomposition of x into A_i+1.
CONSTRAINT: No element of A has an f 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 f Decomposition Construction is, in general,
truly accelerated over the
Constrained f 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 f Decomposition
Construction of infinite length must be the unique basis for E
decomposition.
COROLLARY 4.2. Any Accelerated f Decomposition Construction that
starts with a set with elements outside the unique basis for f
decomposition, must be of finite length.
From now on, we concentrate on Accelerated f Decomposition
Construction. It will be convenient to refer to these as: f
constructions.
5. INFINITARY DECOMPOSITION THEOREMS.
Let f:N^k into N. We want to give information on the initial set
A_0 of an f-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.
THEOREM 5.1. There is an f construction of infinite length starting
with an infinite set.
THEOREM 5.2. The possible starting sets for f constructions of length
4 are closed under inclusion.
PROPOSITION 5.3. There is an f construction of any given finite length
starting with some infinite set of even (odd) integers.
There is a more general form of Proposition 5.3.
PROPOSITION 5.4. There is an f 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 f-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
i. B is a subset of A.
ii. 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 f
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 f construction starting
with a finite set, must consist of finite sets.
PROPOSITION 6.2. For all f:N^k into N, there is an f 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 f:{0,...,t}^k into N, there is an f 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'.
7. INFINITARY PL DECOMPOSITION THEOREMS.
Here we assume that f is an integral piecewise linear (PL) subset of
N^k, with integer coefficients. We can use rational coefficients
throughout without changing the results.
PROPOSITION 7.1. Let f:N^k into N be integral piecewise linear. There
is an f 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 f:N^k into N be integral piecewise linear, and r
>= 1. There is an f 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 f:N^k into N be integral piecewise linear with
coefficients of magnitude at most p, and r >= 1. There is an f
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 417th 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 at http://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
416: Integer Decomposition Theory 3 4/26/10 7:04PM
Harvey Friedman
More information about the FOM
mailing list