[FOM] 385:Shifts and Extreme Greedy Clique Sequences

Fri Jan 1 13:04:57 EST 2010

In #383, I issued the following alert:

> ***We now think that instead of using the upper shift, with its  
> discontinuity at 0, we can use simply the +1 function defined only  
> on the nonnegative rationals***
>
> I.e., the new upper shift would be defined as us:Q into Q, where
>
> us(x) = x+1 if x >= 0; undefined otherwise.
>
> Of course, this has the proper bite only because we incorporate 0  
> properly into the definitions.
>
> I want to think a bit more about this important improvement.

This definitely does not work for the SRP level statements. However, I  
am convinced that it does work for the HUGE level statements.

In fact, we can use the positive shift or the nonnegative shift:

ps:Q into Q, given by ps(x) = x+1 if x > 0; undefined otherwise.
nns:Q into Q, given by nns(x) = x+1 if x >= 0; undefined otherwise.

We use nns below in order to simplify the Extreme Greedy Set Sequences.

This supersedes the earlier definitions of Extreme Greedy Set Sequences.

The use of z there was not erased (it should have been). Some 2's  
should have been 4's. I used SRP instead of HUGE in the statement of  
the result.

ALSO, I am going to change terminology for all of the Extreme stuff -  
now that I am using down cliques, I might as well use "Greedy Down  
Cliques" instead of "Greedy Sets". (Greedy Down Cliques will only  
appear in the Extreme Greedy Down Clique Theorem, and not here, which  
only concerns Sequences).

Thus we will have

THE UPPER SHIFT GREEDY (DOWN) CLIQUE THEOREM.
THE UPPER SHIFT GREEDY (DOWN) CLIQUE GAME THEOREM.
THE UPPER SHIFT GREEDY (DOWN) CLIQUE SEQUENCE THEOREM.

THE EXTREME GREEDY DOWN CLIQUE THEOREM.
THE EXTREME GREEDY DOWN CLIQUE SEQUENCE THEOREM.

For the first three, there are two options: cliques, and down cliques.

CURRENT BOILER PLATE

I am scheduled to give a talk at the upcoming Richard Laver conference
in Boulder. That is my target date for having solid sketches of the
greedy stuff at SRP and HUGE, and also I3/I2 (I3/I2 not discussed here).

This plan will smoke out any errors, as there are now some NONTRIVIAL
LAYERED IDEAS that need to be CAREFULLY CHECKED.

In the short run, I am tied up with finishing touches on my book
Boolean Relation Theory and Incompleteness (March 2009 version on my
website).

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

THE EXTREME GREEDY DOWN CLIQUE SEQUENCE THEOREMS.

The length k subsequences of any sequence are ordered by their  
sequence of positions, using the reverse lexicographic ordering of  
strictly increasing sequences of positive integers.

A digraph on Q^k union Q^k+1 is a graph G with vertex set Q^k union Q^k
+1, whose edge set is a set of ordered pairs from Q^k union Q^k+1.

We say that A is a down clique in G if and only if for all x > y from
A intersect Q^k, (x,y) is not an edge of G.

We define [a,b] = {q in Q: a <= q <= b}.

HUGE+ = ZFC + "for all n, there is an n-huge cardinal". HUGE = ZFC +
{there exists an n-huge cardinal}_n.

Let G be a digraph on Q^k union Q^k+1. A G-sequence is a nonempty
sequence x[1],...,x[n] from Q^k union Q^k+1 with the following
properties.

i. x[1] and x[2] are the 0 vector in Q^k.
ii. Let 3 <= 3m <= n-2. Let y be the m-th subsequence of length k of  
the concatenation of x[1],...,x[3m-1]. Then
     a. x[3m] = y, or (x[3m] < y and (y,x[3m]) is not an edge of G).
     b. If x[3m] is in [0,k]^k then x[3m+1] = x[3m]+1 and x[3m+2] = (k+ 
(1/2),x[3m]+1]).
     c. If x[3m] = (k+(1/2),z) is in Q^k+1 then x[3m+1] = z-1.
iii. {x[2],...,x[n]} is a down clique in G.

We also define G-sequences of infinite length in the obvious way.

THEOREM 1. THE EXTREME GREEDY DOWN CLIQUE SEQUENCE THEOREM. Every  
order invariant digraph G on Q^k union Q^k+1 has a G-sequences of  
every finite length.

THEOREM 2. Every order invariant digraph G on Q^k union Q^k+1 has an  
infinite G-sequence.

THEOREM 3. For every order invariant digraph G on Q^k union Q^k+1 has  
a G-sequence of length k.

THEOREM 4. THE CONCRETE EXTREME GREEDY DOWN CLIQUE SEQUENCE THEOREM.  
Every order invariant digraph G on Q^k union Q^k+1 has a G-sequence of  
length k, whose terms have complexity at most (8k)!!. (A ridiculously  
large but safe upper bound).

Note that Theorems 1,3 are explicitly Pi02. Note that Theorem 4 is  
explicitly Pi01.

THEOREM 5. Theorems 1-4 are provable in HUGE+ but not in any  
consistent fragment of HUGE that proves RCA_0. Theorem 2 is provably  
equivalent to Con(HUGE) over WKL_0. Theorems 1,3,4 are provably  
equivalent to Con(HUGE) over EFA.

COMPLETENESS CONJECTURES

We let PPL(Q) be the family of partial rational piecewise linear
functions 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).

COMPLETENESS CONJECTURE 1. In The Upper Shift Greedy Clique Theorem,
if we fix k and replace the upper shift by any finite list from
PPL(Q), then the resulting statement is provable or refutable in SRP.

COMPLETENESS CONJECTURE 2. In The Extreme Greedy Down Clique Theorem,  
if we fix k and replace the the positive or nonnegative shift by any  
finite list from PPL(Q), then the resulting statement is provable or  
refutable in HUGE.

I believe in the Completeness Conjecture 1, but not in the
Completeness Conjecture 2. I think that I can go well beyond I3, and
likely beyond I1 - but I am not ready to claim it. However, I do think
it holds if we replace HUGE by the NBG + "there exists a nontrivial
elementary embedding from V into V".

The Upper Shift Greedy (Down) Clique Theorem, with upper shift replace  
by the positive or nonnegative shift is provable in RCA_0.

The Upper Shift Greedy (Down) Clique Theorem, with upper shift  
replaced by the shift, is refutable in RCA_0.

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

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

Harvey Friedman