# [FOM] 565: Perfectly Natural Review #4

Harvey Friedman hmflogic at gmail.com
Sat Dec 6 18:29:10 EST 2014

```THIS POSTING IS SELF CONTAINED.

There has been so many improvements that we will START OVER.

MAXIMALITY, BASES, AND INCOMPLETENESS
abridged extended abstract
full extended abstract will appear on my website

1. Introduction.
2. Templates for Maximality.
2.1. Preliminaries.
2.2. Templates in Q[0,1] - maximal roots.
2.3. Templates in Q - step maximal roots.
2.4. Further templates.
3. Specifics for Maximality.
3.1. Sections in Q[0,1] and Q.
3.2. Relations and functions in Q[0,1] and Q.
4. # Bases in Q..
5. #+ Bases in Q.
6. n# Bases in Q.
7. n#+ Bases in Q.

1. INTRODUCTION

Gives an overview of the sections 2-5 in terms of how the material is
structured. Some features are highlighted. There is an explanation of
why Q[0,1] is used in section 2. Most importantly, in the
Introduction, I feature a handful of the results that have the most
immediate impact.

2. TEMPLATES FOR MAXIMALITY

2.1. PRELIMINARIES

DEFINITION 2.1.1. A relation R on a set X is a subset of X^2. R is
univalent if and only if x R y and x R z implies y = z. We write x R y
if and only if the relation holds of x,y. A root of R is a set S such
that A^2 containedin R. A square of R is a set S^2 containedin R.

DEFINITION 2.1.2. A graph G on a set V is a pair (V,E), where E is a
relation on V which is irreflexive and symmetric. A clique of G is a
set S containedin V such that for all distinct x,y in S, x E y.

DEFINITION 2.1.3. Maximal roots, maximal squares, maximal cliques are
roots, squares, cliques that are not a proper subset of any root,
square, clique.

Step maximality makes sense only in the context of Q^k.

DEFINITION 2.1.4. N is the set of all nonnegative integers. Z is the
set of all integer., Q is the set of all rational numbers, and Q[0,1]
is Q intersect [0,1]. For S containedin Q^k, S^+ is the set of all
elements of S all of whose coordinates are > 0. We use k,n,m,i,j,r,s,t
are positive integers unless indicated otherwise. For tuples x,y, x*y
is the concatenation of x,y. For x in Q^k, min(x), max(x) is the
least, greatest coordinate of x. Let S containedin Q^k. S|<p = {x in
S: max(x) < p}.

DEFINITION 2.1.5. Let R be a relation on Q^k. S is a step maximal root
of R if and only if for all n, S intersect (-infinity,n]^k is a
maximal root of R intersect (-infinity,n]^2k. S is a step maximal
square of R if and only if for all n, S intersect (-infinity,n]^2k is
a maximal square of R intersect (-infinity,n]^2k. Let G be a graph on
Q^k. S is a step maximal clique of G if and only if for all n, S
intersect (-infinity,n]^k is a maximal clique of ((-infinity,n]^k,E
intersect (-infinity,n]^2k). Here all intervals are intervals in Q.

DEFINITION 2.1.6. Let S containedin X and P be a relation on X. S is P
invariant if and only if for all x P y, we have x in S iff y in S. Let
S' containedin X^k. S' is diagonally P invariant if and only if for
all x_1,...,x_k,y_1,...,y_k with each x_i P y_i, we have
(x_1,...,x_k) in S' iff (y_1,...,y_k) in S.

The most familiar use of invariance is for equivalence relations.

THEOREM 2.1.1. Let S containedin X and P be an equivalence relation on
X. S is P invariant if and only if S is the union of equivalence
classes of E.

DEFINITION 2.1.7. Let x,y be tuples from Q. x,y are order equivalent
if and only if x,y are of the same length, and for all 1 <= i,j <=
lth(x), x_i < x_j iff y_i < y_j. S containedin Q^k is order invariant
if and only if S containedin Q^k is invariant with respect to order
equivalence on Q^k. S containedin Q[0,1]^k is order invariant fi and
only if S containedin Q[0,1]^k is invariant with respect to order
equivalence on Q[0,1]^k.

DEFINITION 2.1.8. Relations on Q^k, Q[0,1]^k are order invariant if
and only if they are order invariant as subsets of Q^2k, Q[0,1]^2k.
Graphs on Q^k, Q[0,1]^k are order invariant if and only if their edge
relations are order invariant as subsets of Q^2k, Q[0,1]^2k.

THEOREM 2.1.2. For each k, the number of order invariant subsets of
Q^k and Q[0,1]^k are the same positive integer.

Note how we have used the ambient spaces Q^k and Q[0,1]^k for order
invariant sets, relations and graphs. This is significant in light of
the following.

THEOREM 2.1.3. The order invariant subsets of Q[0,1]^k are the same as
the intersection of order invariant subsets of Q^k with Q[0,1]^k.
Q[0,1]^k is not an order invariant subset of Q^k, but is an order
invariant subset of Q[0,1]^k.

We now introduce the important wider category of order theoretic sets
and relations, which is not sensitive to the ambient space. We need
only use the ambient spaces Q^k.

DEFINITION 2.1.9. S containedin Q^k is order theoretic if and only if
S is defined by a propositional combination of inequalities s < t,
where s,t are either variables v_1,...,v_k, or elements (parameters)
from Q. We identify partial functions f:Q^n into Q^m with their
graphs, which are subsets of Q^n+m. A relation on Q^k is order
theoretic if and only if it is order theoretic as a subset of Q^2k.

THEOREM 2.1.4. S conainedin Q^k is order invariant if and only if S
containedin Q^k is order theoretic using no parameters.

There is an important well known theorem about parameter sets of order
theoretic subsets of Q^k.

THEOREM 2.1.5. For every order theoretic subset S of Q^k, there is a
minimum set of parameters sufficient to order theoretically define S
as in Definition 2.1.9. The elements of this minimum set are called
the parameters of S. If S is an order theoretic subset of Q[0,1]^k
then its parameters lie in Q[0,1].

DEFINITION 2.1.10. Let P containedin Q^k. P' is embeddable in P if and
only if there is an order preserving bijection h:A into B, A,B
containedin Q, such that for all (x_1,...,x_k) in P implies
(h(x_1),...,h(x_k)) in P.

THEOREM 2.1.2. There is an algorithm for deciding whether one order
theoretic subset of Q^k is embeddable in another. The algorithm is
uniform in k. If there is an embedding then there is an order
invariant embedding.

DEFINITION 2.1.11. SRP is ZFC + {there exists lambda with the
k-SRP}_k. SRP^+ is ZFC + "for all k there exists lambda with the
k-SRP". HUGE is ZFC + {there exists an n-huge cardinal}_k. HUGE^ is
ZFC + "for all k there exists ann-huge cardinal". RCA_0 and WKL_0 are
my first two base theories for Reverse Mathematics.

2.2. TEMPLATES IN Q[0,1] - MAXIMAL ROOTS

maximal roots in Q[0,1]. We have been able to give a complete analysis
of the last two of these four templates within SRP^+ (SRP for C), and
show that this is best possible. For the first two templates, we know
that SRP is required. However, for the first two templates, we only
conjecture that SRP^+ is sufficient. This is a tractable problem.

TEMPLATE A. Let P_1,...,P_r be order theoretic relations on Q[0,1]^k.
Every order invariant relation on Q[0,1]^k has a P_1,...,P_r invariant
maximal root.

TEMPLATE B. Let P_1,...,P_r be order theoretic relations on Q[0,1].
Every order invariant relation on Q[0,1]^k has a diagonally
P_1,...,P_r invariant maximal root.

TEMPLATE C. Let P_1,...,P_r be order theoretic relations on Q[0,1]^k.
For all order theoretic relations P_1',...,P_s' on Q[0,1]^k, each
embeddable in some P_i, every order invariant relation on Q[0,1]^k has
a P_1',...,P_k' invariant maximal root.

TEMPLATE D. Let P_1,...,P_r be order theoretic relations on Q[0,1].
For all order theoretic relations P_1',...,P_s' on Q[0,1], each
embeddable in some P_i, every order invariant relation on Q[0,1]^k has
a diagonally P_1',...,P_r' invariant maximal root.

THEOREM 2.2.1. Every instance of Templates A - D is provably
equivalent to a Pi01 sentence over WKL_0.

THEOREM 2.2.2. Every instance of Template C is either provable in SRP
or refutable in RCA_0. Every instance of Template C is either provable
in WKL_0 + some Con(SRP[k]) or refutable in RCA_0. Every instance of
Template D is either provable in SRP^+ or refutable in RCA_0. Every
instance of Template D is either provable in WKL_0 + Con(SRP) or
refutable in RCA_0.

THEOREM 2.2.3.  For all k, there exists instances of Templates A - D
that are not provable in SRP[k], provided SRP[k] is consistent. There
exist instances of Templates B and D that are not provable in SRP,
provided SRP is consistent. There is no k such that 1) every instance
of Templates A and C are provable or refutable in SRP[k], and  2)
SRP[k] is 1-consistent. Not every instance of Templates B or D is
provable or refutable in SRP, assuming SRP is 1-consistent.

CONJECTURE 2.2.4. Theorem 2.2.2 holds with C,D replaced by A,B, respectively.

We now present the least general templates under consideration for
maximal roots in Q[0,1] for which we have obtained ZFC incompleteness.

TEMPLATE E. Let P be an order theoretic equivalence relation on
Q[0,1]^k. Every order invariant relation on Q[0,1]^k has a P invariant
maximal root.

TEMPLATE F. Let P be an  order theoretic univalent relation on
Q[0,1]^k. Every order invariant relation on Q[0,1]^k has a P invariant
maximal root.

TEMPLATE G. Let P,P'  be order theoretic univalent relations on
Q[0,1]. Every order invariant relation on Q[0,1]^k has a diagonally
P,P' invariant maximal root.

TEMPLATE H. Let P be an order theoretic univalent relation on Q[0,1].
For all order theoretic univalent relations P_1, P_2 on Q[0,1]
embeddable in P, every order invariant relation on Q[0,1]^k has a
diagonally P_1,P_2 invariant maximal root.

THEOREM 2.2.5. Theorem 2.2.1 holds for Templates E-H. Theorem 2.2.2
holds with D replaced by H. Theorem 2.2.3 holds with A,C replaced by
E,F,G, and B,D replaced by H.

CONJECTURE 2.4.6. Theorem 2.2.2 holds with C replaced by E,F,G and D
replaced by H.

DEFINITION 2.2.1. Let P be a relation on Q[0,1]^k. P is order
preserving if and only if x P y implies x,y are order equivalent.

We now give an attractive sufficient condition for all of the above templates.

PROPOSITION 2.2.7. In Templates A - H, condition 1 is necessary,
condition 2 is neither necessary or sufficient, and conditions 1,2 are
sufficient but not necessary.
1. All P's in the template are order preserving.
2. For all P's in the template, If x P y then every x_i not= y_i are
both parameters of P that are greater than every x_i = y_i.

THEOREM 2.2.8. The necessary, not necessary, and not sufficient parts
of Proposition 2.4.7 are provable in RCA_0. The sufficiency of 1,2,
for each of the templates, is provably equivalent to Con(SRP) over
WKL_0. These results hold even if we require that P be univalent in
Templates A,B.

2.3. TEMPLATES IN Q - STEP MAXIMAL ROOTS

In section 2.2, we used Q[0,1] instead of Q because for Q, we have not
obtained any incompleteness there from ZFC. This issue is still open.
We still get a complete analysis of Templates C,D,H using the same
systems as before, but it could be that the complete analysis only
requires (a small fragment of) ZFC.

However, if we use step maximal roots of order invariant relations on
Q^k, we obtain the same results.

THEOREM 2.3.1. If we replace "maximal" by "step maximal" and Q[0,1] by
Q in section 2.2, then all results still hold and all conjectures
remain in force.

2.4. FURTHER TEMPLATES

THEOREM 2.4.1. All of the theorems of sections 2.2 and 2.3 hold if we
replace "order invariant relation" by "order invariant graph", and
"root" by "clique".

THEOREM 2.6.2. All of the theorems of sections 2.2 and 2.3 hold if we
replace "root" by "square" and replace the appropriate Q[0,1]^k by
Q[0,1]^2k, and the appropriate Q^k by Q^2k.

3. SPECIFICS FOR MAXIMALITY

3.1. SECTIONS IN Q[0,1] AND Q

DEFINITION 3.1.1. For tuples x,y, x*y is the concatenation of x and y.
We do not allow the empty tuple. Let S,S' containedin Q^k. The section
of S at x in Q^n is S[x] = {y in Q^k-n: x*y in S}. The lower section
of S at x is S[x]|<max(x). Thus all n-section of S
are emptyset if n >= k. S,S' agree below p in Q if and only if S|<p =
S'|<p.  S^<, S^>, S^<=, S^>=,
S^not= consists of the elements of S that are strictly increasing,
strictly decreasing, increasing (<=), decreasing (>=), distinct,
respectively. Let E containedin Q. E^<k, E^>k, E^<=k, E^>=k consists
of the tuples from E that are of length <k, >k, <=k, >=k,
respectively.

The following statement arises from instances of Template E. We state
it for relations/roots, relations/squares, and graphs/cliques.

PROPOSITION 3.1.1. Every order theoretic relation (relation, graph) on
Q[0,1]^k has a maximal root (square, clique) whose sections at tuples
in {1,1/2,...,1/n}^r> agree below 1/n.

Here is our strongest such statement involving sections.

PROPOSITION 3.1.2. Every order theoretic relation (relation, graph) on
Q[0,1]^k has a maximal root (square, clique) whose sections at any
order equivalent x,y in  {1,1/2,...,1/n}^<=2k agree below min(x*y).

We can also work with consecutive tuples.

DEFINITION 3.1.2. Let p_1 > ... > p_n. x in {p_1,...,p_n}^r> is
consecutive if and only if x is of the form (p_i,p_i+1,...,p_i+r-1).

PROPOSITION 3.1.3. Every order theoretic relation (relation, graph) on
Q[0,1]^k has a maximal root (square, clique) whose sections at
consecutive x,y in {1,1/2,...,1/n}^r> agree below min(x*y).

We now transfer these three propositions to step maximality in Q. It
is now much more natural to use N rather than {1,1/2,...,1/n}.
Strictly speaking, we are no longer under the templates of section 2.

PROPOSITION 3.1.4. Every order theoretic relation (relation, graph) on
Q^k has a step maximal root (square, clique) whose sections at tuples
in N^r< agree below 0.

PROPOSITION 3.1.5. Every order theoretic relation (relation, graph) on
Q^k has a step maximal root (square, clique) whose sections at any
order equivalent x,y in N<=2k agree below min(x*y).

PROPOSITION 3.1.6. Every order theoretic relation (relation, graph) on
Q^k has a step maximal root (square, clique) whose sections at
consecutive x,y in N^r< agree below min(x*y).

THEOREM 3.1.7. Propositions 3.1.1 - 3.1.6, three forms each, are
provably equivalent to Pi01 sentences over WKL_0 via Goedel's
Completeness Theorem.
L
THEOREM 3.1.8. Propositions 3.1.1 - 3.1.6 are provably equivalent to
Con(SRP) over WK_0.

3.2. RELATIONS AND FUNCTIONS IN Q[0,1] AND Q

We present specific relations and functions for use in the templates
of section 3.1.

DEFINITION 3.2.1. Let E containedin Q be finite or of type omega and x
in Q^k. The upper E part of x is {x_i: every x_j >= x_i lies in E}.
The E lifting of x results in lifting the upper E part up one position
in E, provided we don't encounter max(E). If we encounter max(E), then
there is no E lifting of x. x,y are E similar if and only if x,y are
order equivalent and have the same coordinates in the same positions
outside their upper E parts.

Note that E lifting is an order theoretic univalent relation on Q^k,
and E similarity is an order theoretic equivalence relation on Q^k.

THEOREM 3.2.1. If E containedin Q is finite then E lifting is an order
theoretic univalent relation on Q^k, and E similarity is an order
theoretic equivalence relation on Q^k.

PROPOSITION 3.2.2. Let E containedin Q[0,1] be finite. Every order
theoretic relation (relation, graph) on Q[0,1]^k has an E lifting
diagonally invariant maximal root (square, clique).

PROPOSITION 3.2.3. Let E containedin Q[0,1] be finite. Every order
theoretic relation (relation, graph) on Q[0,1]^k has an E lifting
invariant maximal root (square, clique).

PROPOSITION 3.2.4.  Let E containedin Q[0,1] be finite. Every order
theoretic relation (relation, graph) on Q[0,1]^k has an E similar
invariant maximal root (square, clique).

For step maximality in Q, it is natural to use N lifting, and N similarity.

PROPOSITION 3.2.5. Every order theoretic relation (relation, graph) on
Q^k has an N lifting diagonally invariant step maximal root (square,
clique).

PROPOSITION 3.2.6. Every order theoretic relation (relation, graph) on
Q^k has an N lifting invariant step maximal root (square, clique).

PROPOSITION 3.2.7.  Every order theoretic relation (relation, graph)
on Q^k has an N similar invariant step maximal root (square, clique).

THEOREM 3.2.8. Propositions 3.2.2 - 3.2.7, three forms each, are
provably equivalent to Pi01 sentences over WKL_0 via Goedel's
Completeness Theorem.

THEOREM 3.2.9. Propositions 3.2.2 - 3.2.7, three forms each, are
provably equivalent to Con(SRP) over WKL_0.

4. # BASES

DEFINITION 4.1. Let R be a relation on Q^k. x R reduces to y if and
only if x R y and max(x) > max(y). S is a basis for R if and only if S
containedin Q^k, and every x in Q^k\S R reduces to some y in S,
whereas no x in S reduces to any y in S.

THEOREM 4.1. Q^k does not have a basis.

There is a simple way to modify the notion of basis with deep
consequences. In a basis, we use Q^k\S. We want to replace Q^k by a
generally smaller set.

DEFINITION 4.2. Let S containedin Q^k. #(S) is the least set A^k
containing S union {0}^k.

DEFINITION 4.3. Let R be a relation on Q^k. S is a # basis for R if
and only if S containedin Q^k, and every x in #(S)\S R reduces to some
y in S, whereas no x in S R reduces to any y in S.

THEOREM 4.2, {0}^k is a basis for R. All bases for R have an element x
with max(x) <= 0. R has a # basis whose intersection with N^k is an
order invariant subset of N^k.

DEFINITION 4.4. The upper shift of x in Q^k is obtained by adding 1 to
all nonnegative coordinates. The upper shift of S containedin Q^k,
written ush(S), is
the set of all upper shifts of elements of S.

PROPOSITION 4.3. Every order invariant relation on Q^k has a # basis
containing its upper shift.

THEOREM 4.4. Proposition 4.3 is provably equivalent to a Pi01 sentence
over WKL_0 via Goedel's Completeness Theorem.

THEOREM 4.5. Proposition 4.3 is provably equivalent to Con(SRP) over
WKL_0.  This remains true even for a small fixed k.

5. #+ BASES

In #+ bases, tuples all of whose coordinates are positive, have a
preferred status.

DEFINITION 5.1. Let R be a relation on Q^k. S is a # basis for R if
and only if S containedin Q^k, and every x in #(S)^+\S R reduces to
some y in S, whereas no x in S^+ R reduces to any y in S.

DEFINITION 5.2. Let S containedin Q^k. The lower n-sections of S are
the sets of the form {y in Q^k-n: x*y in S and max(y) < max(x)}, x in
Q^n.

PROPOSITION 5.1. Every order invariant relation on Q^k has a #+ basis
whose elements and lower 2-sections include those of its upper shift.

THEOREM 5.2. Proposition 5.1 is provably equivalent to a Pi01 sentence
over WKL_0 via Goedel's Completeness Theorem.

THEOREM 5.3. Proposition 5.1 is provably equivalent to Con(HUGE) over
WKL_0. This remains true even for a small fixed k.

6. n# BASES

THEOREM 6.1. The following is false. Every order invariant relation on
Q^k has a finite # basis containing its upper shift.

There is an obvious fix that still does not work.

THEOREM 6.2. The following is false. Every order invariant relation on
Q^k has a finite # basis containing its <n upper shift.

We need to weaken the notion of # basis, as it calls for every x in
S#\S to be reduced to an element of S. We weaken this requirement in
two alternative ways, which yield the same results:

i. Every x in S#\S is R reduces to something "similar" to an element of S.
ii. Every x in S#\S is "similar" to something R reduces to an element of S.

It is easily seen below that i,ii are equivalent. We will arbitrarily
use i. We actually use a multiple form of i.

DEFINITION 6.1. Let x,y in Q^k. x,y are n order equivalent if and only
if (x,0,...,n) and (y,0,...,n) are order equivalent. Let R be a
relation on Q^k. x in (Q^k)^n R reduces to y in (Q^k)^n if and only if
each x_i R reduces to y_i.

DEFINITION 6.2. Let R be a relation on Q^k. An n# basis is an S
containedin Q^k such that every x in (#(S)\S)^n R reduces to a kn
tuple n order equivalent' to to some y in S^n, whereas no x in S R
reduces to any y in S.

PROPOSITION 6.3. Every order invariant relation on Q^k has a finite n#
basis which contains its upper shift below n.

Proposition 6.3 is explicitly Pi02. Obvious exponential type upper
bounds can be placed on the size of and the numerators and
denominators used in the n# basis. This results in an explicitly Pi01
statement.

THEOREM 6.4. Proposition 6.3 is provably equivalent to Con(SRP) over EFA.

7. n#+ BASES

DEFINITION 7.1. Let R be a relation on Q^k. An n#+ basis is an S
containedin Q^k such that every x in (#(S)\S)^n+ R reduces to a kn
tuple n order equivalent to some y in S^n, whereas no x in S^+ R
reduces to any y in S.

PROPOSITION 7.1. Every order invariant relation on Q^k has an n#+
basis S containing ush(S)|<n with S[(2n+1)/4,0] = ush(S)[n,n]|<n/2.

Proposition 7.1 is explicitly Pi02. Obvious exponential type upper
bounds can be placed on the size of and the numerators and
denominators used in the #+' basis. This results in an explicitly Pi01
statement.

THEOREM 7.2. Proposition 7.1 is provably equivalent to Con(HUGE) over EFA.

************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
This is the 565th 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
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
561: New Pi01/HUGE  11/5/14  3:34PM
562: Perfectly Natural Review #1  11/19/14  7:40PM
563: Perfectly Natural Review #2  11/22/14 4:56PM
564: Perfectly Natural Review #3  11/24/14 1:19AM

Harvey Friedman
```