[FOM] 401: New Free Reduction Theory 4
Harvey Friedman
friedman at math.ohio-state.edu
Mon Mar 15 16:12:40 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
************************************************
POINCARE - Set theory is a disease from which mathematics will one day
recover.
FRIEDMAN - Set theory provides a method demonstrably necessary for
finite mathematics.
**********************************
According to sources, no quote exactly like that can be really found
from Poincare. Poincare is said to have REALLY said this, the first
sentence in italics:
POINCARE - There is no actual (given complete) infinity. The
Cantorians have forgotten this, and they have fallen into contradiction.
There are various opinions of Poincare on set theory quoted in
Dauben's book on Cantor.
Of course, we are all aware of Poincare's discussions of
predicativity, and these are of course more focused.
******************************
We now give a statement that corresponds to the HUGE cardinal hierarchy.
We also give a statement that is provable from I2 but not from I3.
I1,I2,I3 are the well known large large cardinals, far far stronger
than measurable cardinals or the cardinals used to prove forms of
determinacy. I1 is the strongest large cardinal axiom not known to be
inconsistent with ZFC which is familiar to the majority of logicians.
I1 is "there is a nontrivial elementary embedding from some V(alpha +
1) into V(alpha + 1).
I3 is "there is a nontrivial elementary embedding from some V(alpha)
into V(alpha).
I2 is a more specialized axiom that follows from I1 and proves I3.
*************************
In this posting, we will use order invariant relations on Q^k. The
statements will assert that every order invariant relations on Q^k has
a reduction (function) with an embedding property. By general
principles, the statements will be seen to be provably equivalent to
Pi01 sentences.
In later postings, we intend to give explicitly Pi01 forms that
involve arbitrary relations on N^k and {0,...,t}^k.
*************************
1. PRELIMINARIES.
2. MEASURABLE CARDINALS.
3. HUGE.
4. I3.
1. PRELIMINARIES.
We write Q for the set of all rationals and N for the set of all
nonnegative integers.
We say that x in Q^k is increasing if and only if x_1 <= ... <= x_k.
We work with relations R on Q^k. I.e., R is contained in Q^k x Q^k =
Q^2k. We write x R y for (x,y) in R.
We say that y is a strict R reduction of x if and only if max(x) >
max(y) and x R y. We say that y is an R reduction of x if and only if
y = x in Q^k, or y is a strict R reduction of x.
We say that f is a free R inc reduction if and only if
i. f:Q^k into Q^k is partial.
ii. For all increasing x in dom(f), f(x) is an R reduction of x.
iii. No value of f is a strict R reduction of any increasing value of f.
Let f:Q^k into Q^k be partial, and q in fld(f). We write f|<q for f
intersect (-infinity,q)^2k.
We write f_q for f intersect {q} x Q^2k-1.
We write f<q> for the partial function g:Q into Q given by g(r) =
max(f(q,...,q,r)) if r < q and f(q,...,q,r) is defined; undefined
otherwise.
We say that h self embeds f if and only if h:Q into Q is partial, and
for all x in dom(h), fhx = hfx. For this equation, we extend h
coordinatewise to vectors.
We say that x,y in Q^k are order equivalent if and only if for all 1
<= i,j <= k, x_i < x_j iff y_i < y_j. We say that R contained in Q^2k
is order invariant if and only if R is the union of equivalence
classes of Q^2k under order equivalence.
2. MEASURABLE CARDINALS.
In http://www.cs.nyu.edu/pipermail/fom/2010-March/014430.html we
stated a Proposition involving the Upper Shift, which we claimed
corresponded to HUGE. We take this back, and instead assert that it
corresponds to roughly a MEASURABLE CARDINAL. However, if we use the
lexicographic ordering on Q^k in the definition of free reduction,
then it jumps to HUGE.
In any case, we prefer to work in the present framework, without the
upper shift.
PROPOSITION 2.1. Every order invariant relation on Q^k has a free inc
reduction with inclusion comparable nontrivial self embeddings f<n>, n
in N.
THEOREM 2.2. Proposition 3.1 is provable in ZFC + "there exists a
measurable cardinal" but not in any consequence of ZFC + "there exists
a Ramsey cardinal" consistent with RCA_0. WKL_0 + Proposition 3.1
proves Con(ZFC + "there exists a measurable cardinal"). RCA_0 +
Proposition 3.1 proves Con(ZFC + "there exists a Ramsey cardinal").
3. HUGE.
We now work with the lexicographic ordering. Thus we define
y is a strict R lex-reduction of x.
y is an R lex-reduction of x.
f is a free R inc lex-reduction of x.
PROPOSITION 3.1. For all t in N, every order invariant relation on Q^k
has a free inc lex-reduction f:E^k into E^k with nontrivial self
embeddings f<n+1>|<n, n in {0,...,t}.
PROPOSITION 3.2. Every order invariant relation on Q^k has a free inc
lex-reduction f:E^k into E^k with nontrivial self embeddings f<n+1>|
<n, n in N.
THEOREM 3.3. Propositions 3.1, 3.2 are provable in HUGE+ but not in
any consequence of HUGE consistent with RCA_0. Propositions 3.1. 3.2
are provably equivalent, over WKL_0, to Con(HUGE).
4. I3.
PROPOSITION 4.1. For all t in N, every order invariant relation on Q^k
has a free inc lex-reduction f:E^k into E^k such that for all integers
0 <= n <= m <= t, f<n> is a nontrivial self embedding of f_m|<m.
PROPOSITION 4.2. Every order invariant relation on Q^k has a free inc
lex-reduction f:E^k into E^k such that for all integers 0 <= n <= m,
f<n> is a nontrivial self embedding of f_m|<m.
THEOREM 4.2. Proposition 4.1 is provable in I2 but not in I3. In fact,
the gap can be considerably reduced. E.g., we can use "there is a
proper class of nontrivial self embeddings of ranks".
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 401st 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 4:58PM
400: New Free Reduction Theory 3 3/14/10 11:55AM
Harvey Friedman
More information about the FOM
mailing list