[FOM] 365:Free Reductions and Large Cardinals 1
Harvey Friedman
friedman at math.ohio-state.edu
Thu Sep 24 12:54:59 EDT 2009
FREE REDUCTIONS AND LARGE CARDINALS 1
by
Harvey M. Friedman
September 24, 2009
1. Free Reductions and Subreductions.
2. Free Subeductions in Order Invariant Relations.
3. Free Reduction Sequences.
1. FREE REDUCTIONS AND SUBREDUCTIONS.
We say that R is a binary relation if and only if R is a set of
ordered pairs. We write dom(R) for the set of all R predecessors,
rng(R) for the set of all R successors, and fld(R) for dom(R) union
rng(R).
Let A be a set. The R reduction functions on A are the functions f
with domain A such that for all x in A, f(x) = x or R(f(x),x).
This notion of reduction is natural if we think of R as "going up".
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 1,2 we will be concerned only with subreductions. In
section 3, we will work with reductions.
We say that A is R free if and only if there are no x,y in A such that
R(x,y).
THEOREM 1.1. Suppose R is finite and there are no cycles. Then fld(R)
has a unique R free R subreduction.
There is an infinite form of Theorem 1.1. We say that R is well
founded if and only if every nonempty subset of fld(R) has an R
minimal element. This is equivalent to asserting that there is no
infinite sequence for which every term is an R successor of the next.
THEOREM 1.2. Suppose R is well founded. Then fld(R) has a unique R
free R subreduction.
THEOREM 1.3. (Reverse Mathematics). Theorem 1.2, for countable R, is
equivalent to ATR_0 over RCA_0.
We can still apply Theorems 1.1, 1.2 to arbitrary R. We let R|A = R
intersect A x A.
THEOREM 1.4. Suppose R|A is finite and has no cycles. Then A has a
unique R free R subreduction contained in A. Suppose R|A is well
founded. Then A has a unique R free R subreduction contained in A.
In Theorem 1.4, A may have R free R subreductions that are not
contained in A. E.g., let R = {(1,2)}, A = {2}. Then {1} is an R free
subreduction of A that is not contained in A.
Theorem 1.1 is equivalent to a well known fundamental theorem of graph
theory: every finite directed acyclic graph has a unique dominator
(and 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 dominators, and the dual notion of kernels.
We now investigate free subreductions for some very concrete binary
relations R.
2. FREE SUBREDUCTIONS IN ORDER INVARIANT RELATIONS.
We use Q for the set of all rationals, N for the set of all
nonnegative integers, and Z for the set of all integers.
We say that x,y in Q^k are order equivalent if and only if they have
the same length, and for all 1 <= x,y <= 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^k is
{x in Q^k: 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
dominating 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).
This is a particularly natural condition in our context, since if
R(x,y) then x is a "reduction" of y in a numerical sense.
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.
SD(Q^k) consists of the strictly dominating relations on Q^k.
SDOI(Q^k) consists of the strictly dominating order invariant
relations on Q^k.
THEOREM 2.1. Let R be in SD(Q^k) and A be a well ordered subset of Q.
Then A^k has a unique R free R subreduction.
We now want to require that the subreductions be closed under various
operations on the ambient space Q^k.
This requirement leads to very subtle considerations even for very
basic operations. We shall see that the subtleties already occur
partial rational piecewise linear f:Q into Q.
We let PFN(Q) be the family of partial functions from Q into Q.
Let f in PFN(Q). We say that A contained in Q^k is f closed if and
only if
for all (x_1,...,x_k) in A intersect dom(f), (f(x_1),...,f(x_k)) in A.
A PFN(Q) system is a tuple of the form M = (f_1,...,f_n), n >= 1,
where each f_i in PFN(Q).
We say that A contained in Q^k is M closed if and only if A is f
closed for each component f of M.
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 is a PFN(Q) system where the component functions lie
in PPL(Q).
TEMPLATE A. Let M be a PPL(Q) system. Does every R in SDOI(Q^k) has an
A^k containedin Q^k, containing the zero vector, with an M closed R
free R subreduction?
The problem to be investigated is: for which choices of PPL(Q) systems
M is this statement true?
We have only scratched the surface of this problem. But what we have
found already requires us to go far beyond ZFC.
THEOREM 2.2. Template A is false for the single function f:Q into Q,
where for all x in Q, f(x) = x+1. (The shift).
THEOREM 2.3. 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).
PROPOSITION 2.4. Template A is true for the single function f:Q into
Q, where f(x) = x+1 if x >= 0; x otherwise. (The upper shift).
THEOREM 2.5. Proposition 2.4 is provable in SUB+ but not in any
consistent fragment of SUB. Proposition 2.4 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.
CONJECTURE. Every instance of the Template is refutable in RCA_0 or
provable in SUB+.
3. FREE REDUCTION SEQUENCES.
Here we straightforwardly restate the Template statement as the
existence of an infinite sequence of finite R free R reductions. This
can be shown to be equivalent to the existence of arbitrarily long
finite sequences, resulting in a Pi02 sentence. Bounds can easily be
placed on the numerators and denominators, resulting in an explicitly
Pi01 sentence.
Let M be a PFN(Q) system and A containedin Q^k.
We begin with an informal description of the process. We start with
the zero vector. At each successive stage, we take the vectors with
coordinates that already appear, choose an R reduction, and apply M.
We require that no two vectors produced by the entire process be
related by R. This is equivalent to the question in Template A for M,
even if we only ask for the process to continue for k steps.
Here is the formal treatment.
We write span(A) for the least superset of A of the form E^k.
We write M<A> for the set consisting of the elements of A together
with all values of the component functions of M applied coordinatewise
to elements of A.
Let R in REL(Q^k) and M be a PFN(Q) system. An R free M,R sequence is
a finite or infinite sequence A_1,A_2,... of finite subsets of Q^k
such that
i. A_1 = {(0,...,0)}.
ii. Every A_i+1 = M<B>, where B is an R reduction of span(A_i).
iii. The union of the A's is R free.
LEMMA 3.1. Every M,R sequence forms a chain under inclusion.
LEMMA 3.2. The union of any infinite M,R sequence is an M closed R
free R subreduction of the union of its span with {(0,...,0)}.
LEMMA 3.3. Let A^k containedin Q^k contain the zero vector, and B be
an R free R subreduction of A^k. There is an infinite R free M,R
sequence whose union is contained in B.
THEOREM 3.4. Let R in REL(Q^k) and M be a PFN(Q) system. The following
are equivalent.
i. There exists A^k containedin Q^k, containing the zero vector, with
an M closed R free R subreduction.
ii. There exists an infinite R free M,R sequence.
TEMPLATE B. Let M be a PPL(Q) system. Does every R in SDOI(Q^k) has an
infinite R free M,R sequence?
TEMPLATE C. Let M be a PPL(Q) system. Does every R in SDOI(Q^k) has
arbitrarily long finite R free M,R sequences?
TEMPLATE D. Let M be a PPL(Q) system. Does every R in SDOI(Q^k) has an
R free M,R sequence of length k?
TEMPLATE E. Let M be a PPL(Q) system. Does every R in SDOI(Q^k) has an
R free M,R sequence of length k whose numerators and denominators have
magnitude at most the factorial of (8k times the maximum magnitude of
those used in M)?
Note that the statements in Templates C,D are explicitly Pi02, and the
statements in Template E is explicitly Pi01.
THEOREM 3.5. It is provable in WKL_0 that Templates A-E have the same
answers. In particular, Theorem 2.5 applies to Templates B-E with M
consisting only of the upper shift.
**********************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 364th 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
362: Simplest Order Invariant Game
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
Harvey Friedman
More information about the FOM
mailing list