[FOM] 392: Finite Games, Vector Reduction, and Large Cardinals 4
Harvey Friedman
friedman at math.ohio-state.edu
Mon Feb 22 09:15:10 EST 2010
In this installment, we focus on SUBBASES and R-EXPANSIONS. In the
latter, we focus on finitary aspects.
More to come!
NOTE: We forgot to define order invariant R contained in NFS(Q), in http://www.cs.nyu.edu/pipermail/fom/2010-February/014397.html
Here is the missing definition (also given below):
We say that R contained in NFS(Q)^2 is order invariant if and only if
for all order equivalent (x,y), (z,w), x R y iff z R w.
*****************************
1. SUBBASES OF FINITE SETS OF RATIONALS.
2. FINITE R-EXPANSIONS.
3. CHALLENGES.
1. SUBBASES OF FINITE SETS OF RATIONALS.
Let Q be the set of rationals and N be the set of nonnegative
integers. We write NFS(Q) for the set of all nonempty finite subsets
of A.
Let R be contained in NFS(Q)^2. We view R as a binary relation on
NFS(Q).
We say that y is a strict R reduction of x if and only if x R y and
min(y) < min(x). We say that y is an R reduction of x if and only if x
= y or y is a strict R reduction.
We say that E is a subbasis for R if and only if
i. E is contained in NFS(Q).
ii. Every finite subset of the union of E has an R reduction in E.
iii. No element of E is a strict R reduction of any element of E.
THEOREM 1.1. There exists R contained in NFS(Q)^2 where the subbases
in R are the empty set and the singletons. This holds for R = NFS(Q)^2.
THEOREM 1.2. Let S be contained in NFS(Q). The following are equivalent.
i. Every R contained in NFS(Q)^2 with domain disjoint from S, has a
subbasis containing S with the same union as S.
ii. Every R contained in NFS(Q)^2 with domain disjoint from S, has a
unique subbasis containing S with the same union as S.
iii. The union of S is well ordered.
We look for more structural information about subbases.
For q in Q, we define the upper shift of q to be q+1 if q >= 0; q
otherwise. We define the upper shift of x in NFS(Q) as the set of
upper shifts of its elements.
We say that A contained in NFS(Q) is upper shift closed if and only if
A contains the upper shifts of its elements.
THEOREM 1.3. The following is false. Every R contained in NFS(Q)^2
whose domain excludes x in NFS(Q) has an upper shift closed subbasis
that includes x.
The problem is that the upper shift involves +1, whereas arbitrary R
can be constructed that work against +1. To remedy this, we need to
focus on "innocent" R.
For x,y,z,w in NFS(Q), we say that (x,y) and (z,w) are order
equivalent if and only if
i. x,z have the same cardinality.
ii. y,w have the same cardinality.
iii. The i-th element of x is less than the j-th element of y if and
only if the i-th element of z is less than the j-th element of w.
We say that R contained in NFS(Q)^2 is order invariant if and only if
for all order equivalent (x,y), (z,w), x R y iff z R w.
Note that there are countably many limited order invariant R contained
in NFS(Q)^2. In fact, every such has a canonical presentation in the
form of a finite set of pairs (x,y), where x,y are nonempty, and x
union y is a finite initial segment of N.
PROPOSITION 1.4. Every order invariant R contained in NFS(Q)^2 whose
domain excludes x_1,...,x_k in NFS(Q) has an upper shift closed
subbasis that includes x_1,...,x_k.
Let SRP+ = ZFC + (for all k)(there exists lambda with the k-SRP). Let
SRP = ZFC + {there exists lambda with the k-SRP}_k. Here SRP =
"stationary Ramsey property", which asserts that any partition of the
unordered k-tuples has a stationary homogenous set. The SRP hierarchy
is intertwined with the subtle, almost ineffable, and ineffable
cardinal hierarchies.
THEOREM 1.5. Proposition 1.4 is provable in SRP+ but not in any
consistent fragment of SRP that proves RCA_0. Proposition 1.4 is
provably equivalent to Con(SRP) over WKL_0.
Here SRP+ = ZFC + (for all k)(there exists lambda with the k-SRP). Let
SRP = ZFC + {there exists lambda with the k-SRP}_k. Here SRP =
"stationary Ramsey property", which asserts that any partition of the
unordered k-tuples has a stationary homogenous set. The SRP hierarchy
is intertwined with the subtle, almost ineffable, and ineffable
cardinal hierarchies.
Although the R in Proposition 1.4 is finitary, the subbasis is not. In
fact, the cited subbasis must be infinite, provided k >= 1.
2. FINITE R-EXPANSIONS.
In this section, we emphasize concreteness.
We write NS(Q,<=k) for the set of all finite subsets of Q with at most
k elements. We write NS(Q,k) for the set of all subsets of Q with k
elements.
Let R contained in NS(Q,<=k)^2. We say that B is an R-expansion of A
if and only if
i. A,B are subsets of NS(Q,<=k+1).
ii. B contains A and the upper shift of A.
iii. Every subset of the union of A with at most k+1 elements has an R
reduction in B.
iv. No element of B is a strict R reduction of any element of B.
v. No proper subset of B has properties i-iv.
It is clear that every R-expansion of a finite set (if it exists) is
finite.
PROPOSITION 2.1. For all order invariant R contained in NS(Q,<=k)^2
and finite A contained in NS(Q,k+1), some B is an R-expansion of A
union B.
If A is nonempty, then clearly B is infinite.
PROPOSITION 2.2. For all order invariant R contained in NS(Q,<=k)^2
and finite A contained in NS(Q,k+1), there are infinitely many
successive R-expansions of A.
Still some infinity here.
PROPOSITION 2.3. For all order invariant R contained in NS(Q,<=k)^2
and finite A contained in NS(Q,k+1), there are k successive R-
expansions of A.
PROPOSITION 2.4. For all order invariant R contained in NS(Q,<=k)^2,
finite A contained in NS(Q,k+1), and n >= 1, there are n successive R-
expansions of A.
Infinity removed!
We can give an explicitly Pi01 form as follows.
PROPOSITION 2.5. For all order invariant R contained in NS(Q,<=k)^2
and finite A contained in NS(Q,k+1), there are k successive R-
expansions of A, in which the magnitudes of the numerators and
denominators used are at most (8k|A|)!!.
PROPOSITION 2.6. For all order invariant R contained in NS(Q,<=k)^2,
finite A contained in NS(Q,k+1), and n >= 1, there are n successive R-
expansions of A, in which the magnitudes of the numerators and
denominators used are at most (8kn|A|)!!.
Here (8k)!! is merely a crude but safe estimate.
PROPOSITION 2.7. For all order invariant R contained in NS(Q,<=k)^2,
there are 2 successive R-expansions of {{0,...,k}}.
PROPOSITION 2.8. For all order invariant R contained in NS(Q,<=k)^2,
there are 2 successive R-expansions of {{0,...,k}}, in which the
magnitudes of the numerators and denominators used are at most (8k)!!.
THEOREM 2.9. For all order invariant R contained in NS(Q,<=k)^2 and
finite A contained in NS(Q,k+1), A has an R-expansion.
THEOREM 2.10. Propositions 2.1 - 2.8 are provable in SRP+ but not in
any consistent fragment of SRP that proves RCA_0. Propositions 2.1 -
2.8 are provably equivalent to Con(SRP) over WKL_0. Propositions 2.3 -
2.8 are provably equivalent to Con(SRP) over EFA = exponential
function arithmetic.
3. CHALLENGES.
Investigate these Propositions in the case k = 2, starting with
Proposition 2.7, using accepted mathematical methods. There are 2^23 =
8,388,608 order invariant subsets of NS(Q,<=2)^2. Consider using a
computer.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 392nd 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 and Large Cardinals 1 2/9/10 3:32PM
390: Finite Games and Large Cardinals 2 2/14/10 10:27PM
391: Finite Games and Large Cardinals 3 2/21/10 5:54AM
Harvey Friedman
More information about the FOM
mailing list