[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