[FOM] 367:Upper Shift Fixed Points and Large Cardinals

[Harvey Friedman]

We now have FIXED POINT THEOREMS proved from large cardinals but not  
in ZFC. There will be more motivational material in some upcoming  
talks to general math audiences.

I handle EXTREME cardinals in a much better way now.

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

1. The Unprovable Upper Shift Fixed Point Theorem.
2. The Unprovable Internal Upper Shift Theorem.
3. Finite Approximations to the Fixed Point Theorem.
4. Finite Approximations to the Internal Theorem.
5. Templates.

1. THE UNPROVABLE UPPER SHIFT FIXED POINT THEOREM.

Let Q be the set of all rationals. We use \ for set theoretic  
difference.

For A contained in Q^k, we write cube(A,0) for the least set B^k  
containing A such that 0 is in B.

We say that x,y in Q^k are order equivalent if and only if they have
the same length, and for all 1 <= i,j <= k,

x_i < x_j if and only if y_i < y_j.

We say that A contained in Q^k is order invariant if and only if for
all order equivalent x,y in Q^k,

x in A if and only if y in A.

Let R be contained in Q^k x Q^k. We say that A is R free if and only  
if A is contained in Q^k and no two elements of A are related by R.

We say that R is order invariant if and only if R is order invariant  
as a subset of Q^2k.

We say that R is strictly dominating if and only if for all x,y in Q^k,

R(x,y) implies max(x) < max(y).

The upper shift of x in Q^k is obtained by adding 1 to all nonnegative  
coordinates of x.

The upper shift of A contained in Q^k is the set of all upper shifts  
of its elements.

We use "us" for the upper shift.

We write SDOI(Q^k) for the family of all strictly dominating order  
invariant R contained in Q^k x Q^k.

UPPER SHIFT FIXED POINT THEOREM 1. For all R in SDOI(Q^k), some A,  
containing its upper shift, is cube(A,0)\R[A].

UPPER SHIFT FIXED POINT THEOREM 2. For all R in SDOI(Q^k), some R free  
A is (cube(A,0)\R[A]) union us(A).

UPPER SHIFT FIXED POINT THEOREM 3. For all R in SDOI(Q^k), some R free  
A contains (cube(A,0)\R[A]) union us(A).

UPPER SHIFT FIXED POINT THEOREM 4. For all R in SDOI(Q^k), some A is  
(cube(A,0)\R[A]) union us(A).

THEOREM 1.1. RCA_0 proves the fourth, and the equivalence of the first  
three. The first three are Unprovable Theorems. They can be proved in  
SUB+ but not in any consistent fragment of SUB. They are provably  
equivalent to Con(SUB), in WKL_0.

Here SUB+ = ZFC + "for all k there exists a k-subtle cardinal". SUB =  
ZFC + {there exists a k-subtle cardinal}_k.

2. THE UNPROVABLE INTERNAL UPPER SHIFT THEOREM.

We write Q^k# be the set of all elements of Q^k whose coordinates are  
distinct. (We use not= instead of # in rich text).

Let A containedin Q^k. The lower cross sections of A are the sets  
LCS(A,x) = {y in Q^k-1: max(y) <= x and (x,y) in A}, x in Q.

We say that B is internal to A if and only if B is contained in A and  
every lower cross section of B is a lower cross section of A.

INTERNAL UPPER SHIFT THEOREM. For all R in SDOI(Q^k), some A, with  
internal upper shift, agrees with cube(A,0)\R[A] on Q^k#.

THEOREM 2.1. The Internal Upper Shift Theorem is an unprovable  
theorem. It can be proved in HUGE+ but not in any consistent fragment  
of HUGE. It is provably equivalent to Con(HUGE), in WKL_0.

Here HUGE+ = ZFC + "for all k there exists a k-huge cardinal". HUGE =  
ZFC + {there exists a k-huge cardinal}_k.

3. FINITE APPROXIMATIONS TO THE FIXED POINT THEOREM.

We use us(A) for the upper shift of A containedin Q^k.

SEQUENTIAL UPPER SHIFT FIXED POINT THEOREM. For all R in SDOI(Q^k),  
there exist finite R free A_1,A_2,... such that for all i >= 1, A_i+1  
= A_i union us(A_i) union cube(A_i+1,0)\R[A_i+2].

FINITE SEQUENTIAL UPPER SHIFT FIXED POINT THEOREM. For all R in  
SDOI(Q^k), there exist finite R free A_1,...,A_k of Q^k such that for  
all 1 <= i <= k-2, A_i+1 = A_i union us(A_i) union cube(A_i+1,0)\R[A_i 
+2].

ESTIMATED SEQUENTIAL UPPER SHIFT FIXED POINT THEOREM. For all strictly  
dominating order invariant R contained in Q^k x Q^k, there exist  
finite R free A_1,...,A_k of Q^k such that for all 1 <= i <= k-2, A_i 
+1 = A_i union us(A_i) union cube(A_i+1,0)\R[A_i+2], where the  
magnitudes of the numerators and denominators used in the A's are at  
most (8k)!.

Note that the Finite Sequential Upper Shift Fixed Point Theorem is  
explicitly Pi02, and the Estimated Finite Sequential Upper Shift Fixed  
Point Theorem is explicitly Pi01.

THEOREM 3.1. All three of these are provably equivalent to Con(SUB),  
in WKL_0. In particular, they are all Unprovable Theorems.

4. FINITE APPROXIMATIONS TO THE INTERNAL THEOREM.

For A contained in Q^k, write fld(A) for the set of all coordinates of  
elements of A.

SEQUENTIAL INTERNAL UPPER SHIFT THEOREM. For all R in SDOI(Q^k), there  
exist finite subsets A_1 containedin A_2 containedin... of Q^k such  
that for all i >= 1,
i. A_i agrees with cube(A_i,0)\R[A_i+1] on Q^k#.
ii. us(A_i) is contained in A_i+1.
iii. for all x in fld(A_i) there exists y in fld(A_i+1) such that  
LCS(us(A_i+2),x) = LCS(A_i+2,y).

FINITE SEQUENTIAL INTERNAL UPPER SHIFT THEOREM. For all R in  
SDOI(Q^k), there exist finite subsets A_1 containedin ... containedin  
A_k of Q^k such that for all 1 <= i <= k-2,
i. A_i agrees with cube(A_i,0)\R[A_i+1] on Q^k#.
ii. us(A_i) is contained in A_i+1.
iii. for all x in fld(A_i) there exists y in fld(A_i+1) such that  
LCS(us(A_i+2),x) = LCS(A_i+2,y).

ESTIMATED SEQUENTIAL INTERNAL UPPER SHIFT THEOREM. For all R in  
SDOI(Q^k), there exist finite subsets A_1 containedin ... containedin  
A_k of Q^k such that for all 1 <= i <= k-2,
i. A_i agrees with cube(A_i,0)\R[A_i+1] on Q^k#.
ii. us(A_i) is contained in A_i+1.
iii. for all x in fld(A_i) there exists y in fld(A_i+1) such that  
LCS(us(A_i+2),x) = LCS(A_i+2,y).
iv. the magnitudes of the numerators and denominators used in the A's  
are at most (8k)!.

THEOREM 4.1. All four of these Internal Upper Shift Theorems are  
provably equivalent to Con(HUGE), in WKL_0. In particular, they are  
all Unprovable Theorems.

5. TEMPLATES.

The Upper Shift Fixed Point Theorem is, quite naturally, an instance  
of a large family of propositions. Note that the upper shift is the  
obvious lifting of the one dimensional upper shift from Q into Q to  
higher dimensions.

We let PPL(Q) be the family of partial f:Q into Q given by

a_1x + b_1 if x in I_1
...
a_nx + b_n if x in I_n

where n >= 1, the a's,b's are rationals, and the I's are pairwise
disjoint nonempty intervals with rational endpoints (or +-infinity).

A PPL(Q) system consists of a finite list of elements of PPL(Q).

Let M be a PPL(Q) system. We say that V is M closed if and only if V
is f closed for all components f of M.

TEMPLATE A. Let M be a PPL(Q) system. Is it the case that for all R in  
SDOI(Q^k), some A containing M[A] is cube(A,0)\R[A]?

TEMPLATE B. Let M,M' be PPL(Q) systems. Is it the case that for all R  
in SDOI(Q^k), some A containing M[A] and with internal M'[A], agrees  
with cube(A,0)\R[A] on Q^k#?

THEOREM 5.1. Template A is false for the single function f:Q into Q,
where for all x in Q, f(x) = x+1. (The shift). Template A is true for
the single function f:[0,infinity) into [0,infinity), where for all x  
 >= 0, f(x) = x+1. (The nonnegative shift). These statements are  
provable in RCA_0.

CONJECTURE. Every instance of Template A is refutable in RCA_0 or
provable in SUB+.

CONJECTURE. Every instance of Template B is refutable in RCA_0 or  
provable in NBG + "there is a nontrivial elementary embedding from V  
into V".

Let M consist of the upper shift. Let M' consist of h:(-infinity,1]  
into (-infinity,1] where h(x) = (x+1)/2 if x in [0,1]; x if x < 0.

THEOREM 5.2. Template B with M = us, and M' = h, can be proved in I2  
but not in I1. It is provable from Con(I2) in WWKL_0. It proves  
Con(ZFC + "there is a proper class of kappa for which there is a  
nontrivial elementary embedding of V(kappa) into V(kappa)").

Nearly the most extreme large cardinal hypotheses are stated in  
Kanamori, The Higher Infinite, page 325:

I1. For some alpha, there is a proper elementary embedding j:V(alpha +
1) into V(alpha + 1).
I2. There is a j:V into M such that V(alpha) is contained in M for
some alpha > crit(j) satisfying j(alpha) = alpha.
I3. For some alpha, there is a proper elementary embedding j:V(alpha)
into V(alpha).

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

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

Harvey Friedman