[FOM] 395 Free Reduction Theory 2
Harvey Friedman
friedman at math.ohio-state.edu
Sun Mar 7 06:34:31 EST 2010
Here we deal with the n-huge cardinal hierarchy. We include a general
finiteness principle, which is properly a part of Free Reduction
Theory 1 http://www.cs.nyu.edu/pipermail/fom/2010-March/014422.html -
it applies to both Free Reduction Theory 1 and this Free Reduction
Theory 2.
FREE REDUCTION THEORY 2
by
Harvey M. Friedman
March 7, 2010
1. INFINITE FREE REDUCTIONS - huge cardinals.
2. GENERAL FINITENESS PRINCIPLE.
3. FINITE FREE REDUCTIONS - huge cardinals.
4. FREE REDUCTION GAMES - huge cardinals.
1. INFINITE FREE REDUCTIONS - huge cardinals.
We use Q for the set of all rational numbers, and Z for the set of all
integers. For E contained in Q, we write E^k,k+1 for E^k union E^k.
Until we state Proposition 1.1, we fix a subsets R,A,B of,
respectively, Q^k x Q^k,k+1, Q^k, Q^k,k+1.
We write x R y if and only if (x,y) in R. We say that y is a strict
reduction of x (relative to R) if and only if x,y are in Q^k,k+1,
max(x) > max(y), and x R y.
We say that y is a reduction of x if and only if y = x or y is a
strict reduction of x.
We say that B is a free reduction of A if and only if every element of
A has a reduction in B, and no element of B is a strict reduction of
any element of B.
The k-cube of B is the set of all k-tuples of rationals appearing in B.
We say that A is a cross section of B if and only if A = {x: (q,x) in
B} for some q in Q. We say that A is amenable (in B) if and only if A
is a subset of B, and for all n in Z, {x in A: max(x) < n} is a cross
section of B.
The upper shift of x in Q^k is obtained by adding 1 to all nonnegative
coordinates. The k-upper shift of A is the set of all upper shifts of
elements of A.
PROPOSITION 1.1. In every order invariant R contained in Q^k x Q^k,k
+1, some subset of Q^k,k+1 with an amenable k-upper shift, freely
reduces its k-cube.
Let HUGE+ = ZFC + "for all k there exists a k-huge cardinal". Let HUGE
= ZFC + {there exists a k-huge cardinal}_k.
THEOREM 1.2. Proposition 1.1 is provable in HUGE+ but not in any
consequence of HUGE that is consistent with RCA_0. Proposition 1.1 is
provably equivalent to Con(HUGE) over WKL_0.
2. GENERAL FINITENESS PRINCIPLE.
We present a general principle whereby statements like Proposition 1.1
can be seen to be provably equivalent, over WKL_0, to a Pi01 sentence,
merely from their form. In fact, there is a very effective conversion
procedure.
First let us consider sentences phi of the following form.
*) Fix positive integers n,m, and rationals c_1,...,c_m. "There exists
subsets A_1,...,A_n of various Cartesian powers of Q, such that psi
holds in (Q,<,0,+c_1,+c_2,...,+c_m,A_1,...,A_n)". Here all quantifiers
in psi are bounded.
THEOREM 2.1. Pi01 Conversion. There is an algorithm that can be
described in practical terms, which accepts any sentence phi of form
*) and computes
i. An algorithm phi* with no input.
ii. A proof in WKL_0 of the equivalence of phi with "phi* never
terminates".
We now indicate how we can apply Theorem 2.1 to Proposition 1.1 above
and Proposition 1.7 of http://www.cs.nyu.edu/pipermail/fom/2010-March/014422.html
to obtain the following.
THEOREM 2.2. Specific Pi01 Conversion. There is an algorithm alpha
with no input and a proof in WKL_0 of the equivalence of Proposition
1.1 above with "alpha never terminates". The same holds for
Proposition 1.7 of Free Reduction Theory 1.
To see this, note that for each order invariant R, Proposition 1.1 can
easily be put into form *). Using Theorem 2.1, Proposition 1.1 now
asserts that for each order invariant R, some algorithm computed from
R does not terminate. We can then form a single algorithm that runs
through all of the order invariant R (in all dimensions 2k), where the
assertion that it does not terminate is equivalent to Proposition 1.1.
The same argument works for Proposition 1.7 of http://www.cs.nyu.edu/pipermail/fom/2010-March/014422.html
.
3. FINITE FREE REDUCTIONS - huge cardinals.
Let x,y in Q^k. We say that y is controlled by x if and only if the
magnitudes of the numerators and denominators of each coordinate of y
in reduced form is at most the sum of the magnitudes of the numerators
and denominators of the coordinates of x in reduced form.
Until we state Proposition 2.1, we fix a subsets R,A,B,E of,
respectively, Q^k x Q^k,k+1, Q^k, Q^k,k+1, Q^k.
We say that B is a free controlled E-reduction of A if and only if
every x in A intersect E has a reduction y in B that is controlled by
x, and no element of B is a strict reduction of any element of B.
We say that A is E-captured in B if and only if A intersect E is a
subset of B, and x in E with max(x) <= k, x in A iff (k+(1/2),x) in B.
PROPOSITION 3.1. In every order invariant R contained in Q^k x Q^k,k+1
and finite E contained in Q^k, some finite subset of Q^k,k+1 with an E-
captured k-upper shift, is a free controlled E-reduction of its k-cube.
THEOREM 3.2. Proposition 3.1 is provable in HUGE+ but not from any
consequence of HUGE consistent with EFA. Proposition 3.1 is provably
equivalent to Con(HUGE) over EFA = exponential function arithmetic.
4. FREE REDUCTION GAMES - huge cardinals.
Let R contained in Q^2k. We define the game G(R,huge) as follows.
Alice and Bob alternately make moves. Every move of Alice is an
element of Q^k. Every move of Bob consists of three elements of Q^k,k
+1. There are requirements on Alice's moves which she can always meet.
There are requirements on Bob's moves which he may not always be able
to meet. If Bob can't meet these requirements, then the game stops.
Bob is focused on trying to play as many moves as possible - i.e., he
tries to keep the game going as long as he can.
ALICE. Except for Alice's first move, Alice must play vectors all of
whose coordinates have been seen before; i.e., in earlier moves of
Alice and Bob. Obviously, Alice can always merely repeat her first
move, although that may make it too easy for Bob to make moves.
BOB. Suppose Alice has just played x in Q^k. Bob plays any y,z,w in
Q^k subject to the following requirements. Thus on every move, Bob
makes 3 plays.
i. y is a reduction of x that is not a strict reduction of any of
Bob's plays in any of his previous moves.
ii. If y in [0,infinity)^k then z = y+1.
iii. if y = (k+3/2,v) in {k+(3/2} x [0,k]^k, then z = y-1.
iv. If x in [0,k]^k then w = (k+(3/2),x+1).
PROPOSITION 4.1. For all R contained in Q^2k, Bob has a strategy for
playing infinitely many moves in G(R,huge).
THEOREM 4.2. Proposition 4.1 is provable in HUGE+ but not in any
consequence of HUGE that is consistent with RCA_0. Proposition 1.1 is
provably equivalent to Con(HUGE) over WKL_0.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 395th 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
Harvey Friedman
More information about the FOM
mailing list