[FOM] 366:Free Reductions and Large Cardinals/polished
Harvey Friedman
friedman at math.ohio-state.edu
Mon Sep 28 14:19:06 EDT 2009
This is a self contained update of http://www.cs.nyu.edu/pipermail/fom/2009-September/014090.html
with new material added related to extremely large cardinals.
FREE REDUCTIONS AND LARGE CARDINALS
by
Harvey M. Friedman
September 28, 2009
1. Introduction.
2. Free Reductions and Subreductions.
3. Free Subeductions in Order Invariant Relations.
4. Free Reduction Sequences.
5. Extreme Cardinals.
1. INTRODUCTION.
In order to give the reader a clear idea as to the nature of the
results, as quickly as possible, we present most of them (not in
strongest form) without giving the key definitions.
The full presentations are given in sections 2-5.
We use Q,N,Z for the set of all rationals, nonnegative integers,
integers, respectively.
We focus on the strictly dominating order invariant relations R
contained in Q^k x Q^k. There are only finitely many such R, and they
have very concrete canonical presentations.
We define the very elementary notions
an R reduction of a set A contained in Q^k.
an R subreduction of a set A contained in Q^k.
an R free set A contained in Q^k.
The upper shift of x in Q^k is obtained from x by adding 1 to every
nonnegative coordinate of x.
The following appears as Proposition 3.2.
PROPOSITION. For all strictly reducing order invariant R contained in
Q^k x Q^k, some E^k containing the zero vector has an R free R
subreduction closed under the upper shift.
We have proved this Proposition using so called large cardinal axioms,
and have shown that this Proposition cannot be proved in ZFC.
Note that the upper shift is the result of lifting the one dimensional
upper shift to higher dimensions. This leads to the following Template:
TEMPLATE. Let f be a piecewise linear function from Q into Q. Is it
the case that for all strictly reducing order invariant R contained in
Q^k x Q^k, some E^k containing the zero vector has an f closed R free
R subreduction?
We conjecture that every instance of the Template is provable using
large cardinals or refutable in ZFC.
The Proposition naturally lends itself to finite approximations. These
finite approximations are given by sequences of finite R free sets,
each included in the next.
We prove, using large cardinals, that there are such sequences of
infinite length. However, we show that ZFC is not enough to prove that
there are such sequences of length k (R is contained in Q^k x Q^k).
This creates explicitly Pi02 independence results. Obvious a priori
estimates on the magnitudes of the numerators and denominators of the
rationals appearing in these sequences are easily given. This creates
explicitly Pi01 independence results.
We then modify the Proposition and associated finite approximations in
a satisfactory way so that the large cardinal axioms needed are among
the most extremely powerful that have been studied in set theory.
Again, this creates explicitly Pi01 independence results.
2. FREE REDUCTIONS AND SUBREDUCTIONS.
Here we discuss reductions and subreductions in a general context. In
sections 3-5, we focus on the more specific context of Q^k x Q^k.
For our purposes, a binary relation is a pair (E,R), where E is a set
and R is contained in E x E. We suppress the E whenever this creates
no ambiguity.
We define the R reduction functions on A contained in E. These are the
functions f
with domain A such that for all x in A, f(x) = x or R(x,f(x)).
This notion of reduction is natural if we think of R as "going down".
The R reductions of A are the ranges of reduction functions on A.
The R subreductions of A are the R reductions of A that are contained
in A.
In sections 2,3 we will be concerned only with subreductions. In
sections 4,5 we will work with reductions.
We say that A containedin E is R free if and only if there are no x,y
in A such that
R(x,y).
THEOREM 2.1. Let R be a binary relation on E. Suppose E is finite and
there are no R cycles. Then every A containedin E has a unique R free
R subreduction.
There is an infinite form of Theorem 2.1. A path in R is a finite or
infinite sequence x_1 R x_2 R ... .
THEOREM 2.2. Suppose R has no infinite paths. Then fld(R) has a unique
R free R subreduction.
THEOREM 2.3. (Reverse Mathematics). Theorem 2.2, for countable R, is
equivalent to ATR_0 over RCA_0.
We can still apply Theorem 2.2 to arbitrary R. We let R|A = R
intersect A x A.
THEOREM 2.4. Suppose R|A has no infinite paths. Then A has a unique R
free R subreduction contained in A.
In Theorem 2.4, A may have R free R subreductions that are not
contained in A. E.g., let R = {(2,1)}, Then {1} is an R free
subreduction of {2} that is not contained in {2}.
Theorem 2.1 is equivalent to a well known fundamental theorem of graph
theory: every finite directed acyclic graph has a unique kernel. This
result is generally credited to J. von
Neumann from his book on game theory with Morgenstern (1944). There is
an extensive literature on kernels, and the dual notion of dominators.
We now investigate free subreductions for some very concrete binary
relations R.
3. FREE SUBREDUCTIONS IN ORDER INVARIANT RELATIONS.
We use Q,N,Z for the set of all rationals, nonegative integers,
integers, respectively.
For A contained in Q^k, we write fld(A) for the set of all rationals
that are a coordinate of some element of A.
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.
Note that there are finitely many equivalence classes of elements of
Q^k under order equivalence.
We say that A contained in Q^r is order invariant if and only if for
all order equivalent x,y in Q^r,
x in A if and only if y in A.
Note that there are finitely many order invariant subsets of Q^r.
We say that a binary relation R contained in Q^k x Q^k is order
invariant if and only if R is order invariant as a subset of Q^2k.
Again, there are finitely many order invariant relations on Q^k (i.e.,
subsets of Q^k x Q^k).
There is a convenient canonical presentation of the order invariant
subsets of Q^r, and hence the order invariant relations on Q^k.
These presentations take the form of a subset E of {1,...,r}^r such that
i. No two distinct elements of E are order equivalent.
ii. The set of coordinates of each element of E forms an initial
segment of 1,...,r.
The corresponding order invariant subset of Q^r is
{x in Q^r: x is order equivalent to some element of E}.
We have only investigated a natural subclass of the order invariant
relations on Q^k that are obviously cycle free. These are the strictly
reducing R contained in Q^k x Q^k. I.e., for all x,y in Q^k,
R(x,y) implies max(x) > max(y).
It is convenient to use the following notation.
REL(Q^k) consists of the relations on Q^k; i.e., the R contained in
Q^k x Q^k.
OI(Q^k) consists of the order invariant relations on Q^k.
SR(Q^k) consists of the strictly reducing relations on Q^k.
SROI(Q^k) consists of the strictly reducing order invariant
relations on Q^k.
THEOREM 3.1. Let R be in SR(Q^k) and A be a well ordered subset of Q.
Then A^k has a unique R free R subreduction.
A set V is closed under a function H if and only if for all x in V
intersect dom(H), H(x) is in V.
The upper shift of any tuple x from Q is obtained from x by adding 1
to every nonnegative coordinate of x, and leaving the negative
coordinates fixed.
PROPOSITION 3.2. For all R in SROI(Q^k), some A^k containing the zero
vector has an upper shift closed R free R subreduction.
THEOREM 3.3. Proposition 3.2 is provable in SUB+ but not in any
consistent fragment of SUB. Proposition 3.2 is 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.
Proposition 3.2 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
SROI(Q^k), some A^k containing the zero vector has an M closed R free
R subreduction?
Template A, where M is just the upper shift from Q into Q, is just
Proposition 3.2.
THEOREM 3.4. 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).
CONJECTURE. Every instance of Template A is refutable in RCA_0 or
provable in SUB+.
4. FREE REDUCTION SEQUENCES.
Proposition 3.2 lends itself to finite approximations. This leads
directly to explicitly Pi02 and explicitly Pi01 independence results.
For A containedin Q^k. The upper shift of A is the set of upper shifts
of elements of A. We write this as us(A).
For a_1,...,a_p, p >= 0, write span(A,a_1,...,a_p)) for (fld(A) union
{a_1,...,a_p})^k.
Let R in SROI(Q^k). An R upper shift sequence is a finite or infinite
sequence of finite R free subsets emptyset = A_1 containedin A_2 ...
contained in Q^k such that each defined A_i+1 is the union of us(A_i)
with some R reduction of span(A_i,0).
PROPOSITION 4.1. For all R in SROI(Q^k), there exists an infinite R
upper shift sequence.
PROPOSITION 4.2. For all R in SROI(Q^k), there exist R upper shift
sequences of every finite length.
PROPOSITION 4.3. For all R in SROI(Q^k), there exists an R upper shift
sequence of length k.
PROPOSITION 4.4. For all R in SROI(Q^k), there exists an R upper shift
sequence of length k where the magnitudes of the numerators and
denominators of rationals appearing in the sequence are at most (8k)!.
Note that Propositions 4.2, 4.3 are explicitly Pi02, and Proposition
4.4 is explicitly Pi01.
THEOREM 4.5. Propositions 3.2, 4.1 - 4.4 are provably equivalent in
WKL_0. In particular, Theorem 3.3 applies to each of these Propositions.
We can also Template Propositions 4.1 - 4.4 using any PPL(Q) system M.
For A containedin Q^k, write M(A_i) for the set of vectors obtained by
applying the component partial functions of M to the elements of A_i,
coordinatewise.
An R,M sequence is a finite or infinite sequence of finite R free
subsets emptyset = A_1 containedin A_2 ... of Q^k such that each
defined A_i+1 is A_i union M(A_i) union some R reduction of span(A_i,0).
We obtain four Templates, B,C,D,E, corresponding to Propositions 4.1 -
4.4.
THEOREM 4.6. Templates A-E are provably equivalent in WKL_0.
5. EXTREME CARDINALS.
We show how this development can be modified to correspond to the
extreme upper end of the large cardinal axioms studied by set theorists.
From 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).
We write Q^k<= for the set of all x in Q^k such that each coordinate
is at most the next.
Let B containedin Q^k. The restriction of B below n is B intersect (-
infinity,n)^k.
We write CS(B,n) for the cross section of B obtained by fixing the
first k-1 arguments to be n.
We say that h embeds B into B if and only if dom(h) containedin rng(h)
= Q, and for all (x_1,...,x_k) in B, (h(x_1),...,h(x_k)) in B.
PROPOSITION 5.1. For all R in SROI(Q^k<=), some A^k<= containing N^k<=
has an R free R reduction B contained in A^k such that for all n in N,
CS(B,n) embeds B|<n into B|<n and omits 0.
THEOREM 5.2. Proposition 5.1 is provable in NBG + AxC + I2 but not in
any
consistent fragment of ZFC + I3. The following is provable in ACA.
Con(NBG + AxC + I2) implies A implies Con(ZFC + I3).
Let R in SROI(Q^k). An exotic R sequence is a finite or infinite
sequence of finite R free subsets A_1 containedin A_2 ... of Q^k such
that each defined A_i+1 contains some R reduction of span(A_i,0,...,i
+1) such that CS(A_i+1,i) embeds A_i+1|<i into A_i+1|<i and omits 0.
PROPOSITION 5.3. For all R in SROI(Q^k), there exists an infinite
exotic R sequence.
PROPOSITION 5.4. For all R in SROI(Q^k), there exist exotic R
sequences of every finite length.
PROPOSITION 5.5. For all R in SROI(Q^k), there exists an exotic R
sequence of length k.
PROPOSITION 5.6. For all R in SROI(Q^k), there exists an exotic R
sequence of length k where the magnitudes of the numerators and
denominators of rationals appearing in the sequence are at most (8k)!.
Note that Propositions 5.4, 5.5 are explicitly Pi02, and Proposition
5.6 is explicitly Pi01.
THEOREM 5.7. Propositions 5.1, 5.3 - 5.6 are provably equivalent in
WKL_0. In particular, Theorem 5.2 applies to each of these Propositions.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 366th 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
Harvey Friedman
More information about the FOM
mailing list