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

Harvey Friedman friedman at math.ohio-state.edu
Sat Oct 3 22:26:53 EDT 2009

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

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

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