[FOM] 169:New PA Independence

[Harvey Friedman]

PUNCH LINE: Theorem 3.3.

######################################

We use N for the set of all nonnegative integers.

Let f:A^k into N, A containedin N. The rank of f is the cardinality 
of A. Here 1 <= r <= infinity. We write fld(A) for A union rng(f).

We say that g is a restriction of f if and only if there exists B 
contained in A such that g is the restriction of f to B^k. We say 
that g is an extension of f if and only if there exists B containing 
A such that g:B^k into N and f is the restriction of g to A^k.

Let f:A^k into N and g:B^k into N, where A,B containedin N.

We say that f,g are isomorphic if and only if there is an increasing 
bijection h:fld(A) onto fld(B) such that for all x1,...,xk,y in A,

f(x1,...,xk) < y if and only if g(hx1,...,hxk) < h(y).

We say that f is homogenous if and only if any two restrictions of f 
of the same rank are isomorphic.

1. INFINITE STATEMENT.

The following is an immediate consequence of the usual infinite Ramsey theorem.

THEOREM 1.1. Let k >= 1. Every f:N^k into N has a homogenous 
restriction of infinite rank.

2. A RELEVANT CRITERION.

Let f:A^k into N, A finite. There is a technical necessary and 
sufficient combinatorial condition on f in order that f have 
homogenous extensions of every finite rank >= card(A).

The correctness of this criterion is provable in EFA.

Furthermore, in RCA0, one can prove that this is equivalent to the 
existence of an infinite homogenous extension. If the criterion holds 
then an infinite homogenous extension can be found that is extremely 
low level recursive.

2. SEMIFINITE STATEMENTS.

Let f:A^k into N. We say that f is limited if and only if for all 
x1,...,xk, f(x1,...,xk) <= max(x1,...,xk).

The first has no bite.

THEOREM 2.1. Let k >= 1. Every limited f:N^k into N has a homogenous 
restriction of every finite rank.

However, consider this.

THEOREM 2.2. Let k >= 1. Every limited f:N^k into N has a restriction 
of any given finite rank with homogenous extensions of every greater 
finite rank.

And this weakening.

THEOREM 2.3. Let k >= 1. Every limited f:N^k into N has a 
restrictionof rank k, with homogenous extensions of every finite 
rank >= k.

THEOREM 2.4. Theorem 2.1 is provable in RCA0 and even in a weak 
fragment of RCA0. The restriction can be found below a stack of 2's 
of height roughly k with the desired finite rank on top of the stack.

THEOREM 2.5. Theorems 2.2 and 2.3 are each provably equivalent to the 
1-consistency of PA over RCA0. The desired restriction in Theorem 2.2 
can be obtained below f(k,r), where f is an epsilon0 recursive 
function. The smallest function f(k,r), for fixed k, eventually 
dominates every <alpha recursive function, but is alpha recursive, 
where alpha is roughly a stack of k omega's. Also for this smallest 
function, f(k,k) is an epsilon0 recursive function that eventually 
dominates every <epsilon recursive function.

3. FINITE STATEMENTS.

THEOREM 3.1. Let n >> k,r >= 1. Every limited f:[0,n]k into [0,n] has 
a homogenous restriction of rank r.

THEOREM 3.2. Let n >> k,r >= 1. Every limited f:[0,n]k into [0,n] has 
a  restriction of rank r, with homogenous extensions of every rank >= 
r.

THEOREM 3.3.  Let n >> k >= 1. Every limited f:[0,n]k into [0,n] has 
a  restriction of rank k, with homogenous extensions of every finite 
rank >= k.

THEOREM 3.4. Theorem 3.1 is provable in EFA + superexponentiation but 
not in EFA. (Here EFA is exponential function arithmetic). The 
analogous quantitative information in Theorem 2.4 holds here.

THEOREM 3.5. Theorems 3.2 and 3.3 are each provably equivalent to the 
1-consistency of PA over EFA. The analogous quantitative information 
in Theorem 2.5 holds here.

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

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 169th 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-149 can be found at 
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html  in the FOM 
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms, 4/22/0  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM