[FOM] 169:New PA Independence

Harvey Friedman friedman at math.ohio-state.edu
Sun May 11 20:35:54 EDT 2003

```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
```