[FOM] 562: Perfectly Natural Review #1

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED

There has been a lot of progress on CMI = Concrete Mathematical
Incompleteness, which has been for some months within the territory of
Perfectly Natural Concrete Mathematical Incompleteness.

This is Part #1 of an abridged account of the entire picture as of
now, and will not have the level of motivation and detail that the
extended abstract will have on my website when it appears there.

1. Maximal Roots in Q[0,1]^k - Templates
2. Maximal Roots in Q[0,1]^k - Specifics
3. G-bases in Q^k
4. p,G-bases in Q^k

1. MAXIMAL ROOTS IN Q]0,1]^k - TEMPLATES

We work with maximal roots in order invariant relations on Q[0,1]^k.
The fuller version will also have entirely parallel developments using
maximal squares and maximal cliques. A root of a binary relation on a
set is a set such that any two elements lie in the relation. A maximal
root is a root that is not a subset of any other root. Here relations
are always binary.

We begin with Perfectly Natural motivating Templates. For a specific
independent statement, see Proposition 2.1.

TEMPLATE A. Let F:Q[0,1]^k into Q[0,1]^k be order theoretic. Every
order invariant relation on Q[0,1]^k has an F invariant maximal root.

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

TEMPLATE C. Let f:Q[0,1] into Q[0,1] be order theoretic. Every order
invariant relation on Q[0,1]^k has an f invariant maximal root.

Here Q[0,1] = Q intersect [0,1]. Order theoretic is the same as order
invariant with constants (parameters). I.e., definable as a
propositional combination of inequalities using only < and constants
from Q. Let S containedin Q[0,1]. S is F invariant if and only if for
all x in Q[0,1]^k, x in S iff Fx in S.S is E invariant if and only if
for all E equivalent x,y, x in S iff y in S. S is f invariant if and
only if for all x in Q[0,1]^k, x in S iff fx in S, where fx =
(f(x_1),...,f(x_k)) in S.

It is obvious that Templates A-C are Perfectly Natural motivators. For
some, this may be yet more compelling when formulated analogously with
maximal squares or with maximal cliques.

See Theorem 1.6 for the implicit concreteness of these Templates.

Although we have not yet been able to completely analyze these
Templates, we present the following Perfectly Natural partial results.

a. A Perfectly Natural sufficient condition for Templates A,C. The
claim of sufficiency for A can be proved from large cardinals but not
in ZFC.
b. A Perfectly Natural sufficient condition for Template B. The claim
of sufficiency for B can be proved from large cardinals but not in
ZFC.
c. The same Perfectly Natural sufficient conditions for the obvious
multiple forms of Templates A,B,C, where we are given finite sequences
of F's, E's, and f's. These claims of sufficiency can be proved from
large cardinals but not in ZFC.
d. a Perfectly Natural formulation of Templates A,B,C for isomorphism
types of F's, E's, and f's. Here we can give a complete analysis of
the resulting Templates. The correctness of the analysis can be proved
from large cardinals but not in ZFC.

We begin with a).

DEFINITION 1.1. Let F:Q[0,1]^k into Q[0,1]^k. F is upward if and only
if for all x in Q[0,1]^k, any coordinate moved by F is greater than
any coordinate not moved by F. F is order preserving if and only if
for all x in Q[0,1]^k, x and F(x)) are order equivalent.

PROPOSITION 1.1. If Template A holds then F is order preserving.
Template A holds if F is additionally upward and order preserving, If
F is upward, then Template A holds for F if and only if F is order
preserving.

PROPOSITION 1.2. Template C holds if f is additionally upward.

We now come to b).

DEFINITION 1.2. Let E be an equivalence relation on Q[0,1]^k. E is
upward if and only if finitely many rationals are moved somewhere by
E, and every x_i smaller than all x_j moved somewhere by E is not
moved by E from x.

PROPOSITION 1.3. If Template B holds then E is order preserving.
Template B holds if E is additionally upward and order preserving. If
E is additionally upward, then Template A holds for F if and only if F
is order preserving.

Now for c).

TEMPLATE D. Let F_1,...,F_r:Q[0,1]^k into Q[0,1]^k be order theoretic.
Every order invariant relation on Q[0,1]^k has an F_1,...,F_r
invariant maximal root.

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

TEMPLATE F. Let f_1,...,f_r:Q[0,1] into Q[0,1] be order theoretic.
Every order invariant relation on Q[0,1]^k has an f_1,...,f_r
invariant maximal root.

PROPOSITION 1.4. Template D holds if the F's are additionally upward,
and order preserving, If the F's are upward, then Template D holds for
the F's if and only if the F's are order preserving.

PROPOSITION 1.5. Template E holds if the E's are additionally upward,
and order preserving, If the E's are upward, then Template E holds for
the E's if and only if the E's are order preserving.

PROPOSITION 1.6. Template F holds if the f's are additionally upward.

Now for d).

DEFINITION 1.3. A,B containedin Q[0,1]^k are isomorphic if and only if
(Q[0,1],<,A) and (Q[0,1],<,B) are isomorphic in the sense of model
theory. Functions f:Q[0,1]^k into Q[0,1]^k are isomorphic if and only
if their graphs are isomorphic subsets of Q[0,1]^k. Relations on
Q[0,1]^k are isomorphic if and only if they are isomorphic subsets of
Q[0,1]^2k. .

THEOREM 1.7. (RCA_0). If f,g:Q[0,1]^k into Q[0,1]^k are isomorphic
then f is order theoretic if and only if g is order theoretic. There
is an effective criteria for determining whether two given order
theoretic subsets of Q[0,1]^k are isomorphic.

TEMPLATE G. Let F:Q[0,1]^k into Q[0,1]^k be order theoretic. For all
F_1,...,F_r isomorphic to F, every order invariant relation on
Q[0,1]^k has an F_1,...,F_r invariant maximal root.

TEMPLATE H. Let E be an order theoretic equivalence relation on
Q[0,1]^k. For all E_1,...,E_r  isomorphic to E, every order invariant
relation on Q[0,1]^k has an E_1,...,E_r invariant maximal root.

TEMPLATE I. Let f:Q[0,1] into Q[0,1] be order theoretic. For all
f_1,...,f_r isomorphic to f, every invariant relation on Q[0,1]^k has
an f_1,...,f_r invariant maximal root, under the coordinate action.

THEOREM 1.8. Every instance of Templates A-I, and Propositions 1.1-1.4
are provably equivalent to Pi01 sentences over WKL_0, via Goedel's
Completeness Theorem.

THEOREM 1.9. Propositions 1.1 and 1.3-1.6 are provably equivalent to
Con(SRP) over WKL_0. Proposition 1.2 is provable in WKL_0 + Con(SRP).

THEOREM 1.10. Every instance of Templates G,H are provable in SRP or
refutable in RCA_0. Every instance of Template I is provable in WKL_0
+ Con(SRP) or refutable in RCA_0.

THEOREM 1.11. For each k there is an instance of Templates A,B,D,E,G,H
that is provable in SRP but not in SRP[k]. So these Templates cannot
be completely analyzed within any SRP[k]. There is an instance of
Templates F,I that is provable in WKL_0 + Con(SRP) but not in SRP. So
these Templates cannot be completely analyzed in SRP.

Here SRP is the stationary Ramsey property hierarchy. This is the same
as the subtle cardinal hierarchy and the ineffable cardinal hierarchy.

There are more ambitious templates, involving rational piecewise
linear functions, again with the important case of one-dimensional
maps acting coordinatewise. There are a lot of open issues here
amenable to attack.

2. MAXIMAL ROOTS IN Q[0,1]^k - SPECIFICS

Here we give some Perfectly Natural cases of some of the Templates in
section 1, which are provable using large cardinals but not in ZFC
(assuming ZFC is consistent).

Arguably the simplest example of this kind involves sections.

DEFINITION 2.1. Let A,B containedin Q^k. The section of A at x is {y
in Q^k-r: (x,y) in A}. Note that if r >= k then the section of A at x
is the emptyset. A,B agree below p in Q if and only if for all x in
Q^k with max(x) < p, x in A iff x in B. Let E containedin Q. E^r> is
the set of all r tuples from E that are strictly decreasing. E^r>=,
E^r<, E^r<= are defined analogously.

PROPOSITION 2.1. Every order invariant relation on Q[0,1]^k has a
maximal root whose sections at elements of {1,1/2,...,1/n}^r> agree
below 1/n.

There are a number of successive strenghenings of Proposition 2.1
involving sections. The following is the strongest one that we
consider.

DEFINITION 2.2.  Let E containedin Q. E^<=k is the set of all
sequences from E of lengths 1,...,k.  For x,y in Q^k, x*y is x
concatenated with y. min(x) is the least coordinate of x.

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

DEFINITION 2.3. Let E be a finite subset of Q[0,1]. The E-lift of x in
Q[0,1]^k is obtained by replacing each x_i in E that is greater than
all x_j notin E by the next greatest element of E; x if this does not
exist.

PROPOSITION 2.3. Let E be a finite subset of Q[0,1]. Every order
invariant relation on Q[0,1]^k has an E-lift invariant maximal root.

DEFINITION 2.4. Let E be a finite subset of Q[0,1]. x,y in Q[0,1]^k
are E-related (are E-relatives) if and only if
i. x,y are order equivalent.
ii. the coordinates of x,y that are not in E are identical in
identical positions, and smaller than the coordinates of x,y that are
in E.

PROPOSITION 2.4. Let E be a finite subset of Q[0,1]. Every order
invariant relation on Q[0,1]^k has an E-related invariant maximal
root.

THEOREM 2.5. Propositions 2.1 - 2.4 are provably equivalent to Pi01
sentences over WKL_0 via Goedel's Completeness Theorem.

THEOREM 2.6. Propositions 2.1 - 2.4 are provably equivalent to
Con(SRP) over WKL_0.

3. G-BASES IN Q^k

DEFINITION 3.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 R free if and only if S
containedin Q^k and no element of S R reduces to any element of S. S
is an R basis if and only if S is R free and every element of Q^k\S R
reduces to some element of S.

THEOREM 3.1. R = Q^2 has no basis.

Here is a Perfectly Natural way to recover from Theorem 3.1. Instead
of requiring that every element of Q^k\S reduces to some element of S,
we require only that all tuples "built out of the elements of S"
reduce to some element of S.

DEFINITION 3.2. Let R be a relation on Q^k and G:Q^k into Q^k. A
G-basis for R is an R free S such that every element of G[S]\S reduces
to an element of S. More generally, let H:Q^kr into Q^k. An H-basis
for R is a nonempty R free S such that every element of H[S^r]\S
reduces to an element of S.

THEOREM 3.2. Let H:Q^kr into Q^k be order theoretic. Every order
invariant relation on Q^k has an H-basis.

TEMPLATE J. Let F:Q^k into Q^k be order theoretic. For all order
theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
G-basis containing its F image.

TEMPLATE K. Let E be an order theoretic equivalence relation on
Q[0,1]^k. For all order theoretic G:Q^k into Q^k, every order
invariant relation on Q^k has a G-basis containing its E image.

TEMPLATE L. Let f:Q[0,1] into Q[0,1] be order theoretic. For all order
theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
G-basis containing its f image.

We also have the variants with stronger conclusions.

TEMPLATE M. Let F:Q^k into Q^k be order theoretic. For all order
theoretic H:Q^kr into Q^k, every order invariant relation on Q^k has
an H-basis containing its F image.

TEMPLATE N. Let E be an order theoretic equivalence relation on
Q[0,1]^k. For all order theoretic H:Q^kr into Q^k, every order
invariant relation on Q^k has an H-basis containing its E image.

TEMPLATE O. Let f:Q[0,1] into Q[0,1] be order theoretic. For all order
theoretic H:Q^kr into Q^k, every order invariant relation on Q^k has
an H-basis containing its f image.

Here we know much more than we do in section 1.  We can completely
analyze Templates J-O, but only using large cardinals.

THEOREM 3.3. Every instance of Templates J,K,M,N is either provable in
SRP or refutable in RCA_0. Every instance of Templates L,O are either
provable in WKL_0 + Con(SRP) or refutable in RCA_0. Assuming Con(SRP),
Templates J,M are equivalent; K,N are equivalent; L,O are equivalent.
In the first two claims, we cannot replace SRP by any fixed SRP[k].

With relative bases we can go well beyond order theoretic invariance
in Perfectly Natural ways. This allows us to give a particularly
simple example of CMI.

DEFINITION 3.3. The upper shift of x in Q^k is the result of adding 1
to all nonnegative coordinates of x. The upper shift of S containedin
Q^k is the set of upper shifts of the elements of S. A finite sequence
of sets in various Q^k contains its upper shift if and only if each
term contains its upper shift.

PROPOSITION 3.4. For all order theoretic G:Q^k into Q^k, every order
invariant relation on Q^k has a G-basis containing its upper shift.

PROPOSITION 3.5. For all order theoretic H:Q^kr into Q^k, every order
invariant relation on Q^k has an H-basis containing its upper shift.

THEOREM 3.5. Propositions 3.4 and 3.5 are provably equivalent to
Con(SRP) over WKL_0.

TEMPLATE P. Let f:Q into Q be rational piecewise linear. For all order
theoretic G:Q^k into Q^k, every order invariant relation on Q^k has a
G-basis containing its f image.

We also have the following multiple form.

TEMPLATE Q. Let f_1,...,f_r:Q into Q be rational piecewise linear. For
all order theoretic HG:Q^kr into Q^k, every order invariant relation
on Q^k has an H-basis containing its f_1,...,f_r images.

THEOREM 3.6. Every instance of Templates P,Q is either provable in
WKL_0 + Con(SRP) or refutable in RCA_0.

4. p,G-BASES IN Q^k

The p,G-bases of R, p >= 2, form a Perfectly Natural way of
approximating the G-bases of R. pG-bases can be finite for any R,
whereas this is not the case for G-bases.

DEFINITION 4.1. Let R be a relation on Q^k, G:Q^k into Q^k, and p >=
2. A p,G-basis for R consists of nonempty sets A_1 containedin ...
containedin A_p containedin Q^k, where A_p is R free and every element
of G[A_i], i < p, reduces to an element of A_i+1.

PROPOSITION 4.1. Let G:Q^k into Q^k be order theoretic. Every order
invariant relation on Q^k has a finite 3,G-basis A containedin B
containedin C, where C contains the upper shift of B.

PROPOSITION 4.2. Let H:Q^kr into Q^k be order theoretic. Every order
invariant relation on Q^k has a finite p,H-basis A_1 containedin ...
containedin A_p, where each A_i+1 contains the upper shift of A_i.

PROPOSITION 4.3. Let H:Q^kr into Q^k be order theoretic. Every order
invariant relation on Q^k has a p,H-basis A_1 containedin ...
containedin A_p, where each A_i contains its upper shift.

Propositions 4.1 and 4.2 are explicitly Pi02. There is an obvious
iterated exponential bounds on the cardinalities involved, and also
the numerators and denominators involved so that they become
explicitly Pi01. With Proposition 4.3, the sets generally have to be
infinite, but they can have a combinatorial structure also leading to
explicitly Pi01 forms.

THEOREM 4.4. Propositions 4.1 and 4.2  are provably equivalent to
Con(SRP) over EFA. Proposition 4.3 is provably equivalent to Con(SRP)
over RCA_0.

************************************************************
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 562nd 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
561: New Pi01/HUGE  11/5/14  3:34 PM

Harvey Friedman