[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