[FOM] 414: Integer Decomposition Theory

Harvey Friedman friedman at math.ohio-state.edu
Fri Apr 23 17:43:22 EDT 2010


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

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

We have been using vectors in Local Basis Construction Theory

We have been thinking about transferring this point of view to  
elements of N (the set of all nonnegative integers).

Multiple breakthroughs on both the conceptual side and the technical  
side have emerged as a result.

On the conceptual side, we have the important motivating idea of  
"additive decomposition". In its most basic form, let n be a  
nonnegative integer. We can "additively decompose" n by

n = m_1 + ... + m_k

where m_1,...,m_k are nonnegative integers other than n. Here we will  
use restrictions on the tuple m_1,...,m_k.

On the technical side, again we have a unique "basis", and the very  
simple and natural deterministic inductive construction to build it.  
The idea of a basis is that every nonnegative integer is either in the  
basis, or can be decomposed using only elements from the basis, AND,  
no basis element can be decomposed using only basis elements. This is  
directly analogous to the notion of basis that occurs all through  
mathematics. However, in at least in the most standard examples from  
mathematics, we have a form of transitivity: if an object can be  
decomposed into simpler objects, and those simpler objects can be  
decomposed into yet simpler objects, then the original object can be  
decomposed into the yet simpler objects. This form of transitivity is  
NOT assumed here.

We first present the natural deterministic inductive construction for  
building the unique basis - which we call the Rudimentary  
Decomposition Construction.

We then give a reformulation of this same construction, using the  
crucial constraint that no integer in the set can be decomposed by f  
using integers from the set.

We show that this constraint reformulation gives the same construction  
as the original deterministic formulation.

This constraint formulation has a very natural extension to  
Accelerated Decomposition, where we process integers ahead of time.

Of course, in Accelerated Decomposition, the only way to complete the  
entire construction (for infinitely many stages) is to construct the  
unique basis.

But suppose that we attempt to insert lots of elements at the first  
stage that are NOT in the unique basis? Of course, we will ultimately  
fail to meet the crucial constraint. But how long can we prolong the  
inevitable?

We establish theorems to the effect that we can start Accelerated  
Decomposition with certain sets of integers disjoint from the unique  
basis, and survive for any given number of stages.

However, these results cannot be proved in ZFC - they can be proved  
using certain large cardinal hypotheses.

It also appears that there is a wider subject called

Accelerated Inductive Definitions.

But here we concentrate on a special case involving Integer  
Decomposition.

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

INTEGER DECOMPOSITION THEORY 1
by
Harvey M. Friedman
April 23, 2010

1. RESTRICTED DECOMPOSITION.
2. RUDIMENTARY DECOMPOSITION CONSTRUCTION.
3. CONSTRAINED DECOMPOSITION CONSTRUCTION.
4. ACCELERATED DECOMPOSITION CONSTRUCTION.
5. INFINITARY DECOMPOSITION THEOREMS.
6. FINITARY DECOMPOSITION 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 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.

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.

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.
66
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  
are provably equivalent to 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.

PROPOSITION 6.1. Every Basic (PL) Addition Function has a length r  
Accelerated Decomposition Construction starting with p,p^2,...,p^t,  
provided p is sufficiently large relative to r and the Addition  
Function, and t is arbitrary. Furthermore, it suffices that p >  
(8krs)!!.

When we go into this carefully, we expect to see something much lower  
than (8krs)!!.

Obviously Proposition 6.1 is explicitly Pi01.

THEOREM 6.2. Proposition 6.1 is provable in SMAH+ but not in any  
consequence of SMAH consistent with EFA. Propositions 5.3- 5.5 are  
provably equivalent to Con(SMAH) over EFA.

Here EFA is exponential function arithmetic.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 412th 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

Harvey Friedmans






























More information about the FOM mailing list