[FOM] 406: Set Equation Tower Theory 3

Harvey Friedman friedman at math.ohio-state.edu
Wed Mar 24 23:32:57 EDT 2010


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

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

Here we adapt earlier work giving Pi01 sentences corresponding to  
measurable cardinals and beyond - to the new setting of Set Equation  
Tower Theory.

We also restate the SRP level statements using the slightly modified  
terminology.

IMAGE EQUATION TOWER THEORY 3
measurable cardinals and beyond
by
Harvey M. Friedman
March 24, 2010

1. SET EQUATIONS AND TOWERS (for large large cardinals).
2. SET EQUATION TOWER THEOREMS - infinite (for large large cardinals).
3. SET EQUATION TOWER THEOREMS - finite. (for large large cardinals).
4. RESTATEMENT OF THE SRP LEVEL STATEMENTS.

1. SET EQUATIONS AND TOWERS (for large large cardinals).

We use N for the set of nonnegative integers, and N+ for the set of  
all positive integers.

For A contained in N^k, we write fld(A) for the set of all integers  
that appear as coordinates of elements of A. We write A# for fld(A)^k.

We define A^<= = {x in A: x_1 <= ... <= x_k}.

Let R contained in N^k x N^k. We define

R<[A] = {y: there exists x in A such that max(x) < max(y) and R(x,y)}.

We start with the equation

A^<= = N^k<=\R<[A]

where A is an unknown subset of N^k.

As before, we get various negative results for what we want to do. So  
we pass to the weaker equation

A^<= = A#^<=\R<[A].

Again, we get various negative results for what we want to do. So we  
pass, as before, to the towers

{A_i with A_i^<= = A_i#^<=\R<[A_i+1]}, 1 <= i <= p

where a tower is a sequence of sets, each included in the next.

Let A_1,...,A_p be a tower in N^k. We say that h is a self embedding  
if and only if h is a function with domain fld(A_p), where for all 1  
<= i <= p and x_1,...,x_k in dom(h),

x_1 < x_2 iff h(x_1) < h(x_2).
(x_1,...,x_k) in A_i iff (h(x_1),...,h(x_k)) in A_i.

We say that h is a progressive self embedding if and only if h is a  
function with domain fld(A_p), where for all 1 <= i <= p and  
x_1,...,x_k in dom(h),

x_1 < x_2 iff h(x_1) < h(x_2).
(x_1,...,x_k) in A_i iff (h(x_1),...,h(x_k)) in A_i+1.

We say that h is a self embedding through n if and only if h is a  
function with domain fld(A_p) intersect [0,n], where for all 1 <= i <=  
p and x_1,...,x_k in dom(h),

x_1 < x_2 iff h(x_1) < h(x_2).
(x_1,...,x_k) in A_i iff (h(x_1),...,h(x_k)) in A_i.

We say that h is a progressive self embedding below n if and only if h  
is a function with domain fld(A_p) intersect [0,n), where for all 1 <=  
i <= p and x_1,...,x_k in dom(h),

x_1 < x_2 iff h(x_1) < h(x_2).
(x_1,...,x_k) in A_i iff (h(x_1),...,h(x_k)) in A_i+1.

Let A be contained in N^k, k >= 3. We define A<n> = {<b,c>: b,c < n  
and <n,...,n,b,c> in A}. Thus A<n> is a subset of N^2.

2. SET EQUATION TOWER THEOREMS - infinite (for large large cardinals).

PROPOSITION 2.1. For all k,p >= 1 and R contained in N^k x N^k, there  
is a tower {A_i with A_i^<= = A_i#^<=\R<[A_i+1]}, 1 <= i <= p, of  
infinite subsets of N^k, where for all n < m < s from A_1, A_p<s> is a  
self embedding through s with critical point min(fld(A_1)), that  
extends A_4<m>.

THEOREM 2.2. Proposition 2.1 implies Con(ZFC + "there exists a Ramsey  
cardinal") over RCA_0, and follows from ACA' + Con(ZFC + "there exists  
a measurable cardinal"). Proposition 2.1 is provable in ZFC + "there  
exists a measurable cardinal".

Here ACA' = ACA_0 + "for all n in N and x contained in N, the n-th  
Turing jump of x exists".

We modify R<[A] to R<*[A] using the lexicographic ordering as follows.

R<[A] = {y: there exists x in A such that x <lex y and R(x,y)}.

PROPOSITION 2.3. For all k,p >= 1 and R contained in N^k x N^k, there  
is a tower {A_i with A_i^<= = A_i#^<=\R<*[A_i+1]}, 1 <= i <= p, of  
infinite subsets of N^k, where for all n < m < s from fld(A_1), A_p<s>  
is a self embedding below m with critical point min(fld(A_1)), that  
extends A_p<n>.

THEOREM 2.4. Proposition 2.3 is equivalent to Con(HUGE) over ACA'.

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

PROPOSITION 2.5. For all k,p >= 1 and R contained in N^k x N^k, there  
is a tower (A_i with A_i^<= = A_i#<=\R<*[A_i+1]}, 1 <= i <= p, of  
infinite subsets of N^k, where for all n < m from fld(A_i), A_p<m> is  
a progressive self embedding below m with critical point min(fld(A_1)).

THEOREM 2.6. Proposition 2.5 implies Con(I3) over RCA_0, and follows  
from ACA' + Con(I2).

Here I3 = ZFC + "there exists a nontrivial elementary embedding from  
some rank into itself". I2 is a technical system that lies strictly  
between I3 and the stronger I1 = ZFC + "there exists a nontrivial  
elementary embedding from some V(alpha + 1) into itself".

3. SET EQUATION TOWER THEOREMS - finite (for large large cardinals).

PROPOSITION 3.1. For all t >> k,p >= 1 and R contained in {0,...,t}^k  
x {0,...,t}^k, there is a tower {A_i with A_i^<= = A_i#^<=\R<[A_i+1]},  
1 <= i <= p, of subsets of N^k with at least r elements, where for all  
n < m < s from A_1, A_p<s> is a self embedding through m with critical  
point min(fld(A_1)), that extends A_4<m>.

THEOREM 3.2. Proposition 3.1 implies Con(ZFC + "there exists a Ramsey  
cardinal") over SEFA, and follows from SEFA + Con(ZFC + "there exists  
a measurable cardinal"). Proposition 3.1 is provable in ZFC + "there  
exists a measurable cardinal".

Here SEFA is "superexponential function arithmetic" = EFA + Finite  
Ramsey Theorem. Here EFA = exponential function arithmetic.

We modify R<[A] to R<*[A] using the lexicographic order as follows.

R<[A] = {y: there exists x in A such that x <lex y and R(x,y)}.

PROPOSITION 3.3. For all t >> k,p,r >= 1 and R contained in N^k x N^k,  
there is a tower {A_i with A_i^<= = A_i#^<=\R<*[A_i+1]}, 1 <= i <= p,  
of subsets of {0,...,t}^k with at least r elements, where for all n <  
m < s from fld(A_1), A_p<s> is a self embedding below m with critical  
point min(fld(A_1)), that extends A_p<n>.

THEOREM 3.4. Proposition 3.3 is equivalent to Con(HUGE) over SEFA.

PROPOSITION 3.5. For all t >> k,p,r >= 1 and R contained in N^k x N^k,  
there is a tower (A_i with A_i^<= = A_i#<=\R<*[A_i+1]}, 1 <= i <= p,  
of subsets of {0,...,t}^k with at least r+1 elements, where for all n  
< m from fld(A_i), A_p<m> is a progressive self embedding below m with  
critical point min(fld(A_1)). Furthermore, it suffices that t be  
greater than a stack of 2's of height 8kpr.

THEOREM 3.6. Proposition 2.5 implies Con(I3) over SEFA, and follows  
from SEFA + Con(I2).

4. RESTATEMENT OF THE SRP LEVEL STATEMENTS.

PROPOSITION 4.1. For all k,p >= 1 and R contained in N+^k x N+^k,  
there is a tower {A_i = A_i#\R<[A_i+1]}, 1 <= i <= p, of infinite  
subsets of N^k, with an elementary embedding with critical point  
min(fld(A_1)).

PROPOSITION 4.2. For all t >> k,p >= 1 and R contained in {1,...,t}^k  
x {1,...,t}^k, there is a tower {A_i = A_i#\R<[A_i+1]}, 1 <= i <= p,  
of subsets of {0,...,t}^k with at least r+1 elements, with an  
elementary embedding through the second largest element of fld(A_1)  
with critical point min(fld(A_1)). Furthermore, it suffices that t be  
greater than a stack of 2's of height 8kpr.

THEOREM 4.3. Proposition 4.1 is provably equivalent to Con(SRP) over  
ACA'. Proposition 4.2 is provably equivalent to Con(SRP) over SEFA.

Here SRP = ZFC + {there exists a k-SRP ordinal}_k. SRP = "stationary  
Ramsey property".

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 406th 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 at http://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  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
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
367: Upper Shift Fixed Points and Large Cardinals  10/4/09  2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction  10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09  2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09  2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09  2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION  12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10  7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1  2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2  2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3  2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4  2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5  2/22/10
3:50AM
394: Free Reduction Theory 1  3/2/10  7:30PM
395: Free Reduction Theory 2  3/7/10  5:41PM
396: Free Reduction Theory 3  3/7/10  11:30PMs
397: Free Reduction Theory 4  3/8/10  9:05AM
398: New Free Reduction Theory 1  3/10/10  5:26AM
399: New Free Reduction Theory 2  3/12/10  9:36AM
400: New Free Reduction Theory 3  3/14/10  11:55AM
401: New Free Reduction Theory 4  3/15/10  4:12PM
402: New Free Reduction Theory 5  3/19/10  12:59PM
403: Set Equation Tower Theory 1  3/22/10  2:45PM
404: Set Equation Tower Theory 2  3/24/10  11:18PM
405: Some Countable Model Theory 1  3/24/10  11:20PM

Harvey Friedman





More information about the FOM mailing list