[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