[FOM] 453: Rational Graphs and Large Cardinals III

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

I now prefer a more direct finite form of the Upper Shift Fixed Point  
Theorem than was presented in 452: Rational Graphs and Large Cardinals  
II http://www.cs.nyu.edu/pipermail/fom/2011-January/015253.html The  
finite form below is also subject to templating as in section 6 of http://www.cs.nyu.edu/pipermail/fom/2011-January/015253.html

The following will update section 2 of http://www.cs.nyu.edu/pipermail/fom/2011-January/015253.html

2. EXPLICITLY Pi01 PROPOSITIONS.

We now give a natural finite form of the Upper Shift Fixed Point  
Theorem. We write ush(A) for the upper shift of A contained in Q^k.

FINITE UPPER SHIFT EQUATION THEOREM. For all order invariant R  
contained in Q^2k, there exists finite A_1 containedin ... containedin  
A_n containedin Q^k, such that each A_i = A_i#\R<A_i+1 contains  
ush(A_i-1).

This statement is explicitly P02. However, it is easy to double  
exponentially bound the size of the finite sets, and then also the  
magnitudes of the numerators and denominators, thereby obtaining  
explicitly P01 sentences.

THEOREM 2.1. The Finite Upper Shift Equation Theorem is provable in SRP 
+. It is provably equivalent to Con(SRP) over EFA. These results hold  
for some fixed k, with n varying.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 453rd 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-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM

Harvey Friedman