[FOM] 394: Free Reduction Theory 1

Harvey Friedman friedman at math.ohio-state.edu
Tue Mar 2 19:30:41 EST 2010


GUICK GLANCE: Propositions 1.7 and 2.1.

FREE REDUCTION THEORY - FRT
by
Harvey M. Friedman
March 2, 2010

1. INFINITE FREE REDUCTIONS.
2. FINITE FREE REDUCTIONS.
3. FREE REDUCTION GAMES.
4. FREE UPPER SHIFT REDUCTION GAMES.
5. STUDENT CHALLENGES.

1. INFINITE FREE REDUCTIONS.

We use Q for the set of all rational numbers. We refer to the reduced  
form of x in Q^k - i.e., (1/3,-1/3,0/1,7/1).

We work with binary relations R on Q^k, which we view as subsets of  
Q^2k. We write x R y if and only if x,y in Q^k and (x,y) in R.

Let R be contained in Q^2k. We say that y is a strict reduction of x  
(relative to R) if and only if max(x) > max(y) and x R y.

We say that y is a reduction of x (relative to R) if and only if y = x  
or y is a strict reduction of x.

Let A,B be subsets of Q^k. We say that B is a free reduction of A if  
and only if every element of A has a reduction in B, and no element of  
B is a strict reduction of any element of B.

Q^k is endowed with its natural subspaces. These are the subsets E^k  
that contain the zero vector. This is in analogy with many spaces in  
mathematics, where the zero vector is also included by default in its  
subspaces.

For A contained in Q^k, we define the cube of A to be the least  
subspace of Q^k containing A.

THEOREM 1.1. In every R contained in Q^2k, every finite set is freely  
reduced by some subset.

THEOREM 1.2. The following is false. In every R contained in Q^2k,  
every cube is freely reduced by some set.

THEOREM 1.3. Let S be a subset of Q. The following are equivalent.
i. In all R contained in Q^2k, there is a free reduction of S^k.
ii. In all R contained in Q^2k, some subset of S^k freely reduces S^k.
iii. In all R contained in Q^2k, there is a unique subset of S^k that  
freely reduces S^k.
iv. S is well ordered.

We work with two kinds of shifts. The shift of x in Q^k is the result  
of adding 1 to all coordinates. The upper shift of x in Q^k is the  
result of adding 1 to all nonnegative coordinates.

The shift (upper shift) of A contained in Q^k is the set of shifts  
(upper shifts) of elements of A. The nonnegative shift of A contained  
in Q^k is the set of all shifts of those elements of A all of whose  
coordinates are nonnegative. The weakest of the three shifts of sets  
is the nonnegative shift.

THEOREM 1.4. THe following is false. In every R contained in Q^2k,  
some set containing its nonnegative upper shift freely reduces its cube.

Since general R can be constructed to work against the +1 function, we  
focus attention on "concrete innocent R" as follows.

We say that x,y in Q^r are order equivalent if and only if for all 1  
<= i,j <= r, x_i < x_j iff y_i < y_j. We say that E contained in Q^r  
is order invariant if and only if E is the union of equivalence  
classes of Q^r under order equivalence.

THEOREM 1.5. THe following is false. In every order invariant R  
contained in Q^2k, some set containing its shift freely reduces its  
cube.

THEOREM 1.6. In every order invariant R contained in Q^2k, some set  
containing its nonnegative shift freely reduces its cube.

What about containing its upper shift?

PROPOSITION 1.7. In every order invariant R contained in Q^2k, some  
set containing its upper shift freely reduces its cube.

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. Here  
lambda is said to have the k-SRP if and only if for all partitions of  
the unordered k-tuples from lambda into two pieces, there is a  
homogeneous set which is a stationary subset of lambda. The SRP  
hierarchy is intertwined with the subtle, almost ineffable, and  
ineffable cardinal hierarchies.

THEOREM 1.8. Proposition 1.7 is provable in SRP+ but not from any  
consequence of SRP consistent with EFA. Proposition 1.7 is provably  
equivalent to Con(SRP) over WKL_0.

THEOREM 1.9. Theorem 1.8 holds for a fixed small dimension k.

Thus we are not approaching SRP in a hierarchy. How small can k be? We  
have postponed this kind of investigation for a long time, preferring  
to settle on a particular statement. However, I think I can safely try  
to come up with a sufficient k shortly. At the moment, if I am forced  
to name a number, I would name k = 4 to 6. I will try hard for k = 3.

2. FINITE FREE REDUCTIONS.

Let x,y in Q^k. We say that y is controlled by x if and only if the  
magnitudes of the numerators and denominators of each coordinate of y  
in reduced form is at most the sum of the magnitudes of the numerators  
and denominators of the coordinates of x in reduced form.

Let A,B be subsets of Q^k. We say that B is a controlled free  
reduction of A if and only if B is a free reduction of A, where every  
element of B controls a reduction in A.

NOTE: We have not gone into just how much "control" is needed here for  
the results. Too much control, and Proposition 2.1 will be refutable,  
not having enough room to make the controlled reductions. Having too  
little control never causes any difficulties here. When we go into the  
numerics of this more deeply, we might find that we do need more room  
- e.g., "at most twice the sum of ..." or "at most eight times the sum  
of ...".

For A contained in Q^k, write ush(A) for the upper shift of A, and  
cube(A) for the cube of A.

PROPOSITION 2.1. In every order invariant R contained in Q^2k and  
finite E contained in Q^k, some finite A containing ush(A) intersect E  
is a controlled free reduction of cube(A) intersect E.

Proposition 2.1 is easily seen to be Pi01 since E gives an obvious  
bound on the magnitudes of the numerators and denominators involved.

THEOREM 2.2. Proposition 2.1 is provable in SRP+ but not from any  
consequence of SRP consistent with EFA. Proposition 2.1 is provably  
equivalent to Con(SRP) over EFA = exponential function arithmetic.

THEOREM 2.3. Theorem 1.2 holds for a fixed small dimension k.

How small can k be? See the remarks at end of section 1 above.

3. FREE REDUCTION GAMES.

Let R contained in Q^2k. We define the game G(R) as follows.

Alice and Bob alternately play elements of Q^k. There are requirements  
on Alice's moves which she can always meet. There are requirements of  
Bob's moves which he may always be able to meet. If Bob can't meet  
these requirements, then the game stops. Bob is focused on trying to  
play as many moves as possible - i.e., he tries to keep the game going  
as long as he can.

ALICE. Except for Alice's first move, Alice must play vectors all of  
whose coordinates have been seen before; i.e., in earlier moves of  
Alice and Bob. Obviously, Alice can always merely repeat her first  
move, although that may make it too easy for Bob to make moves.

BOB. Bob must play a reduction of Alice's last previous move, which is  
not a strict reduction of any of Bob's previous moves.

THEOREM 3.1. For all R contained in Q^2k, Bob has a strategy for  
playing infinitely many moves in G(R).

4. UPPER SHIFT FREE REDUCTION GAMES.

Let R contained in Q^2k. We define the game G(R,ush).

Alice and Bob alternately play elements of Q^k. There are requirements  
on Alice's moves which she can always meet. There are requirements of  
Bob's moves which he may always be able to meet. If Bob can't meet  
these requirements, then the game stops. Bob is focused on trying to  
play as many moves as possible - i.e., he tries to keep the game going  
as long as he can.

ALICE. Except for Alice's first move, Alice must play vectors all of  
whose coordinates have been seen before; i.e., in earlier moves of  
Alice and Bob. Obviously, Alice can always merely repeat her first  
move, although that may make it too easy for Bob to make moves.

BOB. Bob must play a reduction of Alice's last previous move, which is  
not a strict reduction of any of Bob's previous moves or their upper  
shifts.

PROPOSITION 4.1. For all order invariant R contained in Q^2k, Bob has  
a strategy for playing infinitely many moves in G(R,ush).

PROPOSITION 4.2. For all order invariant R contained in Q^2k, Bob has  
a strategy for playing any given finite number of moves in G(R,ush).

PROPOSITION 4.3. For all order invariant R contained in Q^2k, Bob has  
a strategy for playing k moves in G(R,ush).

Note that Propositions 4.2 and 4.3 are Pi01 on the following grounds.  
For each choice of R and number of moves, the statement is obviously  
an effectively given first order sentence in the very decidable  
structure (Q,<,+1). But also, an estimate can be given of the  
numerators and denominators needed for Bob's strategy.

THEOREM 4.4. Propositions 4.1 - 4.3 are provable in SRP+ but not from  
any consequence of SRP consistent with EFA. Proposition 4.1 is  
provably equivalent to Con(SRP) over WKL_0. Propositions 4.2, 4.3 are  
provably equivalent to Con(SRP) over EFA = exponential function  
arithmetic.

5. STUDENT CHALLENGES.

i. Prove Theorem 1.1.
ii. Prove Theorem 1.2.
iii. Prove Theorem 1.3.
iv. Prove Theorem 1.4.
v. Prove Theorem 1.5.
vi. Prove Theorem 1.6.
vii. Show that the order invariant subsets of Q^r have a canonical  
presentation as finite subsets of N^r, where the range of each element  
is an initial segment of N.
viii. Compute the number of order invariant subsets of Q, Q^2, Q^3, Q^4.
ix. Prove Proposition 1.7 for k = 1.
x. Prove Proposition 1.7 for k = 2.
xi. Prove Theorem 3.1.
xii. Prove Proposition 4.1 for k = 1.
xiii. Prove Proposition 4.1 for k = 2.

**********************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 394th 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, 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

Harvey Friedman


More information about the FOM mailing list