[FOM] 532: More General Theory/Perfect Pi01

Sat Aug 23 07:02:21 EDT 2014

In posting #531, we pointed out that the perfect Pi01 independent
statements of
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#82 involving order invariant subsets of Q[0,n]^2k and order invariant
graphs on Q[0,n]^k all take the following form, for any fixed k,n,r:

Every order invariant subset of Q[0,n]^2k has a maximal square (root) with
a specific purely universal property with parameters from Q[0,n].
Every order invariant graph on Q[0,n]^k has a maximal clique with a
specific purely universal property with parameters from Q[0,n].

For this general theory, we can conveniently remove n (as was done in
posting #531):

Every order invariant subset of Q[0,1]^2k has a maximal square (root) with
a specific purely universal property with parameters from Q[0,1].
Every order invariant graph on Q[0,1]^k has a maximal clique with a
specific purely universal property with parameters from Q[0,1].

NOTE: All instances of the above 4 templates are easily seen to be
implicitly Pi01 through a nice undergraduate logic exercise, using Goedel's
completeness theorem.

I conjectured that all instances of the above can be proved or refuted in
SRP. In fact, proved in SRP or refuted in RCA_0. Of course,
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#82
provides simple perfectly natural instances of all four of the above
templates that are provable in SRP but not in ZFC (assuming ZFC is
consistent, which, by the way, I believe).

This conjecture is not going to be easy to deal with, although I haven't
really struggled with it yet. So in #531, I looked at a restricted but
natural class of universal properties with parameters on subsets of
Q[0,1]^k. Here the universal condition takes the form of a finite number of
inclusions between lower general sections of the subset of Q[0,1]^k. Here
sections fix front arguments, whereas general sections fix arguments at any
positions. Lower general sections are the parts of general sections that
live entirely less than the least fixed argument giving rise to the general
section.

For universal conditions of the above form, we can prove the conjecture -
that all instances are provable in SRP or refutable in RCA_0.

Actually this suggests yet another perfect Pi01 independent statement using
comparability of lower sections:

NEW VARIANTS

Every order invariant subset of Q[0,n]^2k has a maximal square (root) whose
lower sections at strictly increasing r tuples of positive integers are
inclusion comparable.
Every order invariant graph on Q[0,n]^k has a maximal clique whose lower
sections at strictly increasing r tuples of positive integers are inclusion
comparable.

These are also provably equivalent to Con(SRP) over WKL_0, if we are
quantifying over all k,n,r.

WHY DIDN"T I THINK OF ALL THIS WHEN I WAS A PHD STUDENT AT MIT IN THE
1960"S? MY PHD THESIS WOULD HAVE BEEN MORE NOTABLE!

I now turn to the main point of this posting. In
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#82,
I also gave perfect Pi01 via what I call STEP MAXIMAL SQUARES, ROOTS,
CLIQUES. S is step maximal means that if you chop off everything at or
below any given positive integer, then you have the usual maximality. The
advantage of step maximality is that we can work in Q^k instead of
Q[0,n]^k, and also use only sections at blocks (i.e., consecutive tuples).
The disadvantage is that step maximality has to be defined, as natural as
it is. AFTER 47 YEARS OF DOING THIS, I SHOULD BE GETTING FUSSY.

NOTE: I of course could have stated everything on Q^k instead of Q[0,n]^k,
but then I don't know how to show unprovability. I am rescued by step
maximality if I use Q^k.

Here is the main point. I now have the STEP MAXIMAL TEMPLATES:

Every order invariant subset of Q^2k has a step maximal square (root) with
a specific purely universal property with parameters from Q.
Every order invariant graph on Q^k has a step maximal clique with a
specific purely universal property with parameters from Q.

Probably still requires a serious struggle to deal with this. HOWEVER!!!!
HOWEVER,

Every order invariant subset of Q^2k has a step maximal square (root) with
a specific purely universal property with positive integer parameters.
Every order invariant graph on Q^k has a step maximal clique with a
specific purely universal property with positive integer parameters.

These look very very tractable! I have to calm down before claiming that
each instance is provable in SRP or refutable in RCA_0.

So I am going to, for the time being, use step maximality and Q^2k, Q^k,
and see how far I can go with purely universal conditions on the S.

I'll stop here, because I am getting some more ideas...

Harvey Friedman

 special cases of a perfectly natural family of statements. We conjecture
that all of the statements in this natural family can be decided in SRP and
even in WKL_0 + Con(SRP)., or still further in WKL_0 + {Con(SRP_k): k >= 1}.

This is going to be quite a challenge, so in the meantime we have looked at
some smaller classes of statements for which we can establish such
completeness for the SRP hierarchy.

TEMPLATE (square). Let phi be a purely universal sentence in <, with atomic
formulas t epsilon S, s < t, where s,t are either variables ranging over
Q[0,1], or constants from Q[0,1]. Let k >= 1. Every order invariant subset
of Q^2k has a maximal square obeying phi.

TEMPLATE (root). Let phi be a purely universal sentence in <, with atomic
formulas t epsilon S, s < t, where s,t are either variables ranging over
Q[0,1], or constants from Q[0,1]. Let k >= 1. Every order invariant subset
of Q^2k has a maximal root obeying phi.

TEMPLATE (clique). Let phi be a purely universal sentence in <, with atomic
formulas t epsilon S, s < t, where s,t are either variables ranging over
Q[0,1], or constants from Q[0,1]. Let k >= 1. Every order invariant graph
on Q^k has a maximal clique obeying phi.

CONJECTURE. Each instance of each of the above 3 templates is provable or
refutable in SRP and WKL_0 + {Con(SRP_k): k >= 1}. In fact, provable there
or refutable in RCA_0.

THEOREM. There are instances of each of the above 3 templates that rise in
SRP cofinally. In particular, ones that are provable in SRP but not
provable in ZFC (assuming ZFC is consistent).

It is evident that for each k,n,r, the following statement is a special
case, presented in two forms. Note that the second is taken from
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#82

Every order invariant subset of Q[0,1]^2k has a maximal square (root) whose
sections at strictly increasing tuples from {1,1/2,...,1/n} agree below 1/n.

Every order invariant subset of Q[0,n]^2k has a maximal square (root) whose
sections at strictly increasing tuples of positive integers <= n agree
below 1.

and the same for the graph formulations:

Every order invariant graph on Q[0,1]^k has a maximal clique whose sections
at strictly increasing tuples from {1,1/2,...,1/n} agree below 1/n.

Every order invariant graph on Q[0,n]^k has a maximal clique whose sections
at strictly increasing tuples of positive integers <= n agree below 1.

Now what are we in a position to claim here?

We can recast our statements in terms of the inclusion between the "lower
section" at tuples. We can also use general sections, where we fix
arguments that are not necessarily in front.

DEFINITION. Let S be containedin Q[0,1]^k. The lower general sections of S
are obtained by fixing at least 1 and less than k coordinates with
rationals from [0,1], and taking the set of tuples of the remaining
arguments, provided that the arguments are less than all of the fixed
arguments.

DEFINITION. A k dimensional lower general section inclusion condition, or
k-LGSIC, is a condition on S containedin Q[0,1]^k asserting that one
particular lower general section of S is contained in another particular
lower general section of S.

THEOREM. The above Conjecture holds for the three Templates for finite sets
of k-LGCIS, k varying.

****************************************
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 53
2nd

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

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20140823/96ff3e59/attachment-0001.html>