[FOM] 419: Integer Decomposition Theory 6

Harvey Friedman friedman at math.ohio-state.edu
Tue May 4 22:39:47 EDT 2010


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

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

Arguable Breakthroughs again, in our opinion.

Here we consider only constructions that process the integers, one at  
a time, in increasing order. There is no acceleration. We modify the  
goal of creating the unique basis. The outputs are to be weaker than  
being a basis, in some respects, and also stronger in other respects.  
We need large cardinals (the SMAH+ hierarchy) in order to prove the  
assertions.

INTEGER DECOMPOSITION THEORY 6
by
Harvey M. Friedman
May 4, 2010

1. f DECOMPOSITIONS AND BASES.
2. f CONSTRUCTIONS.
3. SPANS FROM f CONSTRUCTIONS.
4. INFINITARY DECOMPOSITION THEOREMS.
5. FINITE DECOMPOSITION THEOREMS.
6. INFINITARY PL DECOMPOSITION THEOREMS.
7. FINITARY PL DECOMPOSITION THEOREMS.
8. USE OF ALTERNATING SUMS.

1. f DECOMPOSITIONS AND CONSTRUCTIONS.

We use N for the set of all nonnegative integers.

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. 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 lie in A.

A basis for f is an 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. Every f:N^k into N has a unique basis.

2. f CONSTRUCTIONS AND THEIR SPANS.

Let f:N^k into N. The f basis construction is the following  
construction that constructs the unique f basis, A.

At stage n >= 0, we put n into A if and only if n has an f  
decomposition among A (i.e., the integers that have been thrown into A  
already).

Note that in this construction, an integer n gets put into A only at  
stage n. Of course, n may or may not be put into A.

THEOREM 2.1. The f basis construction constructs the unique basis A  
for f.

We now add some nondeterminism. In what we call an f construction, we  
may put an integer n into A, for the first time, only at stages later  
than n. Of course, once an integer is put into A, it remains in A.

Here are the details of an f construction.

At stage n, n >= 0, we put n into A, or we put the k arguments of some  
f decomposition of n, into A.

Of course, we could simply carry out this f construction by always  
retaining n, thereby creating A = N.

But we will be interested in what we call "the strong constraint":

*No element of A has an f decomposition from A*.

Henceforth, we will make the following

CONVENTION. Whenever we see "f construction" in a statement, and we  
also see the letters k,A, then f:N^k into N, and A is the set  
resulting from the construction.

THEOREM 2.2. Any f construction constructs an infinite A. Any f  
construction that meets the strong constraint must be identical to the  
f basis construction, and hence construct the unique basis for f.

We are interested in f constructions that don't necessarily meet the  
strong constraint.

We wish to approximate the strong constraint. Let S be a subset of N.  
We say that a construction f is good for S if and only if

"no element of A has an f decomposition from A intersect S".

Obviously, any f construction meets the strong constraint if and only  
if it is good for N if and only if it is the f basis construction.

3. SPANS FROM f CONSTRUCTIONS.

Let V be contained in N. We use V to generate elements of N, out of  
any f construction.

The 0 span of V is V union {0,1}.

The i+1 span of V is the union of the i span of V, V+V, and the  
arguments used in all f decompositions of elements of V+V that were  
made in the f construction.

Obviously, the union of the i spans of any V contained in N, is all of  
N.

4. INFINITARY DECOMPOSITION THEOREMS.

We begin with an immediate Corollary of Theorem 2.2.

THEOREM 4.1. There is an f construction that is good for N.

In fact, the above is true of the f basis construction, and only the f  
basis construction.

PROPOSITION 4.2. Some f construction is good for the k span of some  
infinite subset of A intersect 2N.

We can strengthen this as follows.

PROPOSITION 4.3. For all infinite E contained in N, some f  
construction is good for the k span of some infinite subset of A  
intersect E.

We now state a semi finite consequence of Proposition 4.3.

PROPOSITION 4.4. For all infinite E contained in N, some f  
construction is good for the k span of some m element subset of A  
intersect E.

THEOREM 4.5. Propositions 4.2 - 4.4 are provable in SMAH+ but not in
any consequence of SMAH consistent with RCA_0. Propositions 4.2 - 4.4
imply Con(SMAH) over ACA', and follow from 1-Con(SMAH) over ACA'.

I now believe that we have equivalence with 1-Con(SMAH) over ACA',  
although more details need to be checked.

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".

5. FINITARY DECOMPOSITION THEOREMS.

We have been using the k span of V under f constructions. We are  
interested in how V sits in the k span of V.

We say that the k span of V is p tame if and only if

the number of elements in the k span of S less than any given x in S  
is at most p to the number of elements in S less than x.

Here is a strengthening of Proposition 4.2.

PROPOSITION 5.1. Some f construction is good for the (8k)!! tame k  
span of some infinite subset of A intersect 2N.

Our use of (8k)!! here and elsewhere is simply meant to be safe and  
not too ridiculous. Much lower functions of k should suffice, but it  
is rather delicate to see just what is needed.

Now for the semi finite form.

PROPOSITION 5.2. Some f construction is good for the (8k)!! tame k  
span of some m element subset of A intersect 2N.

Now for the Pi02 form. For f:{0,...,t}^k into {0,...,t}, it is  
understood that f constructions process only the integers 0,...,t.  
Hence A is a subset of {0,...,t}.

PROPOSITION 5.3. For all k,m there exists t such that the following  
holds. Let f:{0,...,t}^k into {0,...,t}. Some f construction is good  
for the (8k)!! tame k span of some m element subset of A intersect 2N.

THEOREM 5.4. Propositions 5.1 - 5.3 are provable in SMAH+ but not in
any consequence of SMAH consistent with RCA_0. Propositions 5.1 - 5.3
imply Con(SMAH) over ACA', and follow from 1-Con(SMAH) over ACA'.

I now believe that we have equivalence with 1-Con(SMAH) over ACA',  
although more details need to be checked.

6. 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 6.1. Let f be integral piecewise linear. Some f  
construction is good for the k span of a tail of powers of 2 lying in  
A. Furthermore, we can take the f construction to be exponential  
Presburger.

It is clear, in light of the decision procedure for exponential  
Presburger, that Proposition 6.1 is Pi02.

THEOREM 6.2. Proposition 1.1 is provable in SMAH+ but not in any  
consequence of SMAH consistent with RCA_0. Proposition 6.1 implies  
Con(SMAH) over RCA_0, and follows from 1-Con(SMAH) over RCA_0.

I now believe that we have equivalence with 1-Con(SMAH) over ACA',  
although more details need to be checked.

7. FINITARY PL DECOMPOSITION THEOREMS.

PROPOSITION 7.1. Let f be integral piecewise linear with coefficients  
of magnitude at most p. Some f construction processing 0,...,(9kpr)!!  
is good for the (8k)!! tame k span of some r element subset of A  
intersect 2N.

Note that Proposition 7.1 is explicitly Pi01.

THEOREM 7.2. Proposition 7.1 is provable in SMAH+ but not in
any consequence of SMAH consistent with EFA. Proposition 7.1 is
provably equivalent to Con(SMAH) over ACA'.

8. USE OF ALTERNATING SUMS.

We can use alternating sums instead of f decompositions. We replace f  
by a subset E of N^k. An E decomposition of n in N takes the form

n = m_1 - m_2 + ... +- m_k

where 0 <= m_1,...,m_k and (m_1,...,m_k) is in E.

The results will be the same.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 418th 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
417: Integer Decomposition Theory 4  4/28/10  6:25PM
418: Integer Decomposition Theory 5  4/29/10  4:08PM

Harvey Friedman


More information about the FOM mailing list