[FOM] 561: New Pi01/HUGE

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED

We now have many improvements to #560   and so we now start all over.

Propositions 1.2 and 1.3 are quite new. These are very countably
infinite, but are still equivalent to consistency of certain large
cardinals. They live in the natural numbers (instead of the
rationals), and do not involve order invariance, maximality, or
sections.

Proposition 2.1 is a new explicitly Pi01 statement living in the
integers. It corresponds to SRP.

Proposition 3.2. is a new explicitly Pi01 statement corresponding to HUGE.

1. SMAH
2. SRP
3. HUGE

1. SMAH

All lower case letters represent positive integers unless indicated otherwise.

DEFINITION 1.1. Let R containedin N^2k = N^k x N^k. x red y if and
only if  x R y, and max(x) > max(y). S is irreducible if and only if
there is no x red y, x,y in S. A red B for S if and only if every
element of A^k\S reduces (red) to an element of B^k intersect S.

DEFINITION 1.2. Let R containedin N^2k. S is a basis if and only if S
is irreducible and N red N for S.

THEOREM 1.1. For all k, every R containedin N^2k has a unique basis.

PROPOSITION 1.2. For all k, every R containedin N^2k has an irreducible S for
which some three infinite sets A red B red C red N for S have B+1
containedin C\A.

PROPOSITION 1.3. For all k,p, every R containedin N^2k has an irreducible S for
which some infinite sets A_1 red ... red A_p for S have each (A_i)+1
is contained in A_i+1\A_1.

TEMPLATE A. For all k, every R containedin N^2k has an irreducible S
for which some three infinite sets A red B red C red N for S have a
given Boolean equation in A,B,C,A+1,B+1,C+1.

TEMPLATE B.  Fix p. For all k, every R containedin N^2k has an
irreducible S for which some r infinite sets A_1 red ... red A_p for S
have a given Boolean equation in A_1,...,A_p,(A_1)+1,...,(A_p)+1.

It is morally certain that I will be giving a complete analysis
Template A, and likely also for Template B.

We now consider something like Proposition 1.2 that involves only a
condition relating S and A.

DEFINITION 1.3. Let R containedin N^2k. S is a p-basis over A if and
only if there exists A = A_1 red ... red A_p for S.

STATEMENT. For all k, every R containedin N^2k has a p-basis S over
some infinite A such that S,A have a certain property.

We do not know of a simple property for which the above Statement is strong.

However, we can work successfully with what we call successor bases.

DEFINITION 1.4. Let S containedin N^k. The field of S, fld(S), is the
set of all coordinates of the elements of S. The successor of S is
S+1.

DEFINITION 1.5. Let R containedin N^2k. A sred B for S if and only if
every element of (A+{0,1})^k\S reduces to an element of B^k intersect
S.

DEFINITION 1.6. Let R containedin N^2k. S is a successor p-basis over
A if and only if S is irreducible, and there exist A =  A_1 sred ...
sred A_p  for S.

PROPOSITION 1.4. For all k, every R containedin N^2k has a successor
3-basis over some infinite set disjoint from the successor of its
field.

PROPOSITION 1.5. For all k,p, every R containedin N^2k has a successor
p-basis over some infinite set disjoint from the successor of its
field.

TEMPLATE C. For all k,p, every R containedin N^2k has an successor
p-basis S over some infinite set A obeying a given Boolean equation in
S,A and their integral shifts.

TEMPLATE D. For all k,p, every R containedin N^2k has an successor
p-basis S over some infinite set A with a given universal Presburger
condition involving  S,A.

We believe that Templates C,D are fully amenable to complete analysis.

THEOREM 1.6. Propositions 1.2-1.5 are provably equivalent to Con(SMAH) over ACA.

To obtain simple explicitly Pi01 forms of Propositions 1.2-1.5, we
need to use order invariance. We use [t] = {1,...,t}.

We first concentrate on Proposition 1.2.

PROPOSITION 1.7. Every order invariant R containedin N^2k has an
irreducible S for which some infinite sets A red B red C red N have B+1
containedin C\A.

PROPOSITION 1.8. Every order invariant R containedin N^2k has an
irreducible S for which some (8kN)! red A red B red N have A+1
containedin B\(8kN)!.

PROPOSITION 1.9.  Every order invariant R containedin [t]^2k has an
irreducible S for which some  (8kN)! intersect [t] red A red B red [t]
have A+1 containedin B\(8kN)!.

Note that Proposition 1.9 is explicitly Pi01.

PROPOSITION 1.10. For all k,p, Every order invariant R containedin N^2k has a
successor p-basis over (8kN)! which is disjoint from its field plus 1.

PROPOSITION 1.11.  For all k,p, every order invariant R containedin [t]^2k has a
successor p-basis over (8kN)! intersect [t] which is disjoint from its
field plus 1.

Note that Proposition 1.11 is explicitly Pi01.

THEOREM 1.12. Propositions 1.7 - 1.11 are provably equivalent to
Con(SMAH) over ACA.

2. SRP

DEFINITION 2.1. Let R containedin [-mt,mt]. S is a basis over A if and
only if S is irreducible and there exists A red B red C for S.

DEFINITION 2.2. Let S containedin [-mt,mt]^k. The upper t-shift of S
is the set of all elements of [--mt,mt]^k which are obtained by adding
t to all nonnegative coordinates of some element of S.

PROPOSITION 2.1. Let t  > (8kpm)!!. Every order invariant R
containedin [--mt,mt]^2k has a p-basis over {0} that contains its upper
t shift.

THEOREM 2.2. Proposition 2.1 is provably equivalent to
Con(SRP) over EFA = exponential function arithmetic.

3.  HUGE

We now come to HUGE. For this, we move to tuples of varying lengths,
and also sections obtained by fixing the first coordinate.

DEFINITION 3.1. E^<=k = E^1 union ...  union E^k. Let R containedin
[-mt,mt]^<=2k, x red y if and only if x R y, max(x) > max(y), and x in
[-mt,mt]^k. S is irreducible if and only if no x red y, x,y in S. A
red B for S if and only if every x in A^k intersect [-mt,mt]^k reduces
(red)  to some y in B^<=k. S is a p-basis over A if and only if there
exist A = A_1 red ... red A_r for S.

Firstly, this conversion to multiple lengths does not affect the
status of Proposition 2.1.

PROPOSITION 3.1. Let t > (8kpm)!!. Every order invariant R
containedin [--mt,mt]^<=2k has a basis over {0} that contains its
upper t shift.

DEFINITION 3.2. Let S containedin [-mt,mt]^<=k. S[n] = {x in
[-mt,mt]^<k: (n,x) in S}.

PROPOSITION 3.2. Let t > (8kpm)!!. Every order invariant R
containedin [-mt,mt]^<=2k has a p-basis S over (t+log(t))[m-1] containing
each S[i(t+log(t))] = S+t intersect [it]^<k.

THEOREM 3.3. Proposition 3.1 is provably equivalent to Con(SRP) over
EFA. Proposition 3.2 is provably equivalent to Con(HUGE) over EFA.

************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 561st 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM
542: Templates/LC shadow  9/10/14  12:44AM
543: New Explicitly Pi01  9/10/14  11:17PM
544: Initial Maximality/HUGE  9/12/14  8:07PM
545: Set Theoretic Consistency/SRM/SRP  9/14/14  10:06PM
546: New Pi01/solving CH  9/26/14  12:05AM
547: Conservative Growth - Triples  9/29/14  11:34PM
548: New Explicitly Pi01  10/4/14  8:45PM
549: Conservative Growth - beyond triples  10/6/14  1:31AM
550: Foundational Methodology 1/Maximality  10/17/14  5:43AM
551: Foundational Methodology 2/Maximality  10/19/14 3:06AM
552: Foundational Methodology 3/Maximality  10/21/14 9:59AM
553: Foundational Methodology 4/Maximality  10/21/14 11:57AM
554: Foundational Methodology 5/Maximality  10/26/14 3:17AM
555: Foundational Methodology 6/Maximality  10/29/14 12:32PM
556: Flat Foundations 1  10/29/14  4:07PM
557: New Pi01  10/30/14  2:05PM
558: New Pi01/more  10/31/14 10:01PM
559: Foundational Methodology 7/Maximality  11/214  10:35PM
560: New Pi01/better  11/314  7:45PM

Harvey Friedman