[FOM] 434: Digraph Kernel Structure Theory 1
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jul 3 19:38:52 EDT 2010
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.
######################################################################
In Finite Games and Incompleteness 5 http://www.cs.nyu.edu/pipermail/fom/2010-June/014848.html
we mentioned the exact correspondence between kernels in finite dags
and the winning set of the finite game associated with the finite dag.
At the time, we didn't notice that the exact correspondence breaks
down when we consider infinite dags (although it holds if there are no
infinite walks). So the infinite form of the independent statement in
section 4 there is not Pi01 as stated, but is instead much less
concrete - I think Sigma12.
This tips the balance, in my opinion, to switching over to digraph
kernels, from game theory. Hence this posting.
Sneak preview:
PROPOSITION 4.1. In every downward order invariant digraph on Q^k,
some kernel of some (E union {0})^k is upper shift closed.
PROPOSITION 5.1. In every downward order invariant digraph on Q^k, the
kernels of some strong chain of r finite sets form an upper shift chain.
Proposition 4.1 with some fixed k, Proposition 5.1 with some fixed k
(r varying), and Proposition 5.1 with some fixed r (k varying), are
provable with large cardinals but not without.
We also present a more ambitious templating than in http://www.cs.nyu.edu/pipermail/fom/2010-June/014848.html
We propose to Template both strong chains and upper shift chains, at
the same time:
TEMPLATE INF. Let f,g be in PL(Q^2k). In every downward order
invariant digraph on Q^k, some nonempty f closed set has a g closed
kernel.
TEMPLATE FIN. Let f,g be in PL(Q^2k). In every downward order
invariant digraph on Q^k, the kernels of some f chain of r nonempty
finite sets form a g chain.
THIS POSTING IS ENTIRELY SELF CONTAINED.
########################################s
1. DIGRAPHS AND KERNELS.
2. DOWNWARD ORDER INVARIANT DIGRAPHS.
3. CHAINS AND THE UPPER SHIFT.
4. INFINITE KERNEL THEOREM.
5. FINITE KERNEL THEOREMS.
6. TEMPLATES.
1. DIGRAPHS AND KERNELS.
Kernels in digraphs are intensively studied with a large literature,
including applications to game theory and elsewhere.
A digraph is a pair G = (V,R), where R is contained in V x V. The
vertices of G are the elements of V, and the edges of G are the
elements of R.
A dag is a digraph in which there are no cycles.
We say that E is independent in G if and only if E is a subset of G,
where there is no edge from any element of E to any element of E.
We say that E is a kernel in G if and only if E is independent in G,
and for all x in V\E, there is an edge from x to some element of E.
The following is due to Von Nuemannr 1944, in his book with
Morgenstern on Game Theory.
THEOREM 1.1. There is a unique kernel in every finite dag.
This can be extended to
THEOREM 1.2. There is a unique kernel in every digraph with no
infinite walk.
THEOREM 1.3. Theorem 1.2 for countable digraphs, with or without
uniqueness, is equivalent to ATR_0 over RCA_0.
For A contained in V, we write G|A for the subdigraph of G induced by A.
We say that E is a kernel of A in G if and only if E is a kernel in G|A.
Note that E is a kernel of V in G if and only if E is a kernel in G.
We will investigate the way the kernels of A in G vary as A varies
among the subsets of V.
2. DOWNWARD ORDER INVARIANT DIGRAPHS.
We now focus on digraphs (Q^k,R). We say that these digraphs are on Q^k.
We say that (Q^k,R) is downward if and only if x R y implies max(x) >
max(y).
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 A contained in Q^k is order invariant if and only if for
all order equivalent x,y in Q^k, x in A iff y in A.
An order invariant digraph on Q^k is a digraph (Q^k,R), where R is an
order invariant subset of Q^2k.
3. CHAINS AND THE UPPER SHIFT
A strong chain of subsets of Q^k is a finite or infinite sequence
A_1,...,A_n, where for all 1 <= i < n, every k tuple of consisting of
0 and coordinates of elements of A_i lies in A_i+1.
Let f:Q^k into Q^k. An f chain of subsets of Q^k is a finite or
infinite sequence A_1,...,A_n, where for all 1 <= i < n, A_i union
f[A_i] is contained in A_i+1.
We will focus on the upper shift function, mapping Q^k into Q^k. it is
obtained by adding 1 to all nonnegative coordinates, and keeping all
negative coordinates fixed.
4. INFINITE KERNEL THEOREM.
PROPOSITION 4.1. In every downward order invariant digraph on Q^k,
some kernel of some (E union {0})^k is upper shift closed.
THEOREM 4.2. Proposition 4.1 is provable in SRP+ but not from any
consequence of SRP that is consistent with RCA_0. Proposition 4.1
is provably equivalent, over WKL_0, to Con(SRP). These results hold if
we fix k to be any particular sufficiently large integer in
Proposition 4.1.
Here SRP+ = ZFC + "for all k there exists a limit ordinal with the k-
SRP. SRP = ZFC + {there exists a limit ordinal with the k-SRP}_k. The
k-SRP asserts that every partition of the unordered k-tuples from
lambda into two pieces has a homogeneous set that is a stationary
subset of lambda.
EFA is exponential function arithmetic.
5. FINITE KERNEL THEOREMS.
PROPOSITION 5.1. In every downward order invariant digraph on Q^k, the
kernels of some strong chain of r finite sets form an upper shift chain.
Note that Proposition 5.1 is explicitly Pi02.
The norm of a finite subset of Q^k is the maximum of the magnitudes of
the denominators and numerators in the reduced form of the coordinates
of the elements of its terms if the set is finite; infinite otherwise.
PROPOSITION 5.2. In every downward order invariant digraph on Q^k, the
kernels of some strong chain of r sets of norm at most (8kr)!! form an
upper shift chain.
Note that Proposition 5.2 is explicitly Pi01.
Here (8kr)!! is a safe and convenient upper bounds, which
can be sharply reduced.
THEOREM 5.3. Propositions 5.1, 5.2 are provable in SRP+, but not from
any consequence of SRP that is consistent with EFA. Propositions 5.1,
5.2 are provably equivalent, over EFA, to Con(SRP). These results hold
if we fix k to be any particular sufficiently large integer in these
Propositions. These results also hold if we alternatively fix r to be
any particular sufficiently large integer in these Propositions.
6. TEMPLATES.
Let PL(Q^2k,Q^k) be the class of all piecewise linear functions from
Q^2k into Q^k.
Let f:Q^2k into Q^k We say that E is f closed if and only if f[E^2] is
contained in E is contained in Q^k.
We say that E_1,...,E_k is an f chain if and only if or all 1 <= i <
k, E_i union f([E_i)^2) is contained in E_i+1 is contained in Q^k.
TEMPLATE INF. Let f,g be in PL(Q^2k,Q^k). In every downward order
invariant digraph on Q^k, the kernel of some nonempty f closed set is
g closed.
TEMPLATE FIN. Let f,g be in PL(Q^2k,Q^k). In every downward order
invariant digraph on Q^k, the kernels of some f chain of r finite sets
form a g chain.
The plan is to determine the status of all instances of these Templates.
We know that there is an instance of both Templates which is
independent of ZFC. In fact, provably equivalent to Con(SRP) over
WKL_0 (EFA for the Template Fin).
We expect to be able to accomplish this first for f,g chosen from some
natural restricted subclasses of PL(Q^2k). We expect, ultimately, to
be able to carry this through for the full PL(Q^2k,Q^k).
This looks like it may be the right problem to dig one's teeth in for
a very extended period of time. It this is the case, then posing this
is a very major breakthrough.
We can also allow partial piecewise linear functions, or even finite
lists of (partial) piecewise linear functions such functions, for more
powerful Templates.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 434th 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 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 1graham
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:30PM
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 9:36AM
400: New Free Reduction Theory 3 3/14/10 11:55AM
401: New Free Reduction Theory 4 3/15/10 4:12PM
402: New Free Reduction Theory 5 3/19/10 12:59PM
403: Set Equation Tower Theory 1 3/22/10 2:45PM
404: Set Equation Tower Theory 2 3/24/10 11:18PM
405: Some Countable Model Theory 1 3/24/10 11:20PM
406: Set Equation Tower Theory 3 3/25/10 6:24PM
407: Kernel Tower Theory 1 3/31/10 12:02PM
408: Kernel tower Theory 2 4/1/10 6:46PM
409: Kernel Tower Theory 3 4/5/10 4:04PM
410: Kernel Function Theory 1 4/8/10 7:39PM
411: Free Generation Theory 1 4/13/10 2:55PM
412: Local Basis Construction Theory 1 4/17/10 11:23PM
413: Local Basis Construction Theory 2 4/20/10 1:51PM
414: Integer Decomposition Theory 4/23/10 12:45PM
415: Integer Decomposition Theory 2 4/24/10 3:49PM
416: Integer Decomposition Theory 3 4/26/10 7:04PM
417: Integer Decomposition Theory 4 4/28/10 6:25PM
418: Integer Decomposition Theory 5 4/29/10 4:08PM
419: Integer Decomposition Theory 6 5/4/10 10:39PM
420: Reduction Function Theory 1 5/17/10 2:53AM
421: Reduction Function Theory 2 5/19/10 12:00PM
422: Well Behaved Reduction Functions 1 5/23/10 4:12PM
423: Well Behaved Reduction Functions 2 5/27/10 3:01PM
424: Well Behaved Reduction Functions 3 5/29/10 8:06PM
425: Well Behaved Reduction Functions 4 5/31/10 5:05PM
426: Well Behaved Reduction Functions 5 6/2/10 12:43PM
427: Finite Games and Incompleteness 1 6/10/10 4:08PM
428: Typo Correction in #427 6/11/10 12:11AM
429: Finite Games and Incompleteness 2 6/16/10 7:26PM
430: Finite Games and Incompleteness 3 6/18/10 6:14PM
431: Finite Incompleteness/Combinatorially Simplest 6/20/10 11:22PM
432: Finite Games and Incompleteness 4 6/26/10 8:39PM
433: Finite Games and Incompleteness 5 6/27/10 3:33PM
Harvey Friedman
More information about the FOM
mailing list