[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