[FOM] 563: Perfectly Natural Review #2

Sat Nov 22 16:56:22 EST 2014

THIS POSTING IS A CONTINUATION OF THE SELF CONTAINED #562:
http://www.cs.nyu.edu/pipermail/fom/2014-November/018406.html

>From #562:

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

There has been some advances beyond #562, and so we will start from 3.

1. Same as in 562: Perfectly Natural Review 1
http://www.cs.nyu.edu/pipermail/fom/2014-November/018406.html
'2. Same as in 562: Perfectly Natural Review 1
http://www.cs.nyu.edu/pipermail/fom/2014-November/018406.html
3. H-bases in Q^k.
4. H-bases in Q^k - HUGE.
5. p,H-bases in Q^k.

3. H-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 a basis for R if and only if
every element of Q^k is either in S or reduces to an element of S, but
not both.

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

Here is a Perfectly Natural way to recover from Theorem 3.1. Instead
of making the requirement for every element of Q^k, we only impose the
requirement for the tuples "built out of the elements of S".

DEFINITION 3.3. Let R be a relation on Q^k and H:Q^2k into Q^k. An
H-basis for R is a nonempty S containedin Q^k such that every element
of H[S^2] is either in S or reduces to an element of S, but not both.

NOTE: The definition of H-basis given in
http://www.cs.nyu.edu/pipermail/fom/2014-November/018406.html is
stronger. There we required that every element of H[S^2]\S is
reducible to an element of S, and no element of S reduces to an
element of S. The two definitions are the same in case S containedin
H[S^2]. However, in section 4, we use H:Q^2k into Q^k>= in an
essential way.

We still have the following difficulty.

THEOREM 3.2. Let H:Q^2 into Q be given by H(p,q) = p if p > q; p-1
otherwise. Then R = Q^2 has no H-basis.

Proof: Let S be an H-basis, p in S. Then p+1 in H[S^2]. p+1 in S iff
p+1 does not reduce to an element of S.

case 1. p-1 in S. Then p in H[S^2]. Since p reduces to p-1, we have a
contradiction.
case 2. p-1 notin S. Clearly p-1 in H[S^2]. Then p-1 reduces to an
element of S, say q in S. Then p in H[S^2]. Since p reduces to q, we
have a contradiction.

QED

Here is a Perfectly Natural recovery.

THEOREM 3.3. Let H:Q^2k into Q^k be order theoretic. Every relation on
Q^k has a finite H-basis.

Recall that order theoretic means definable by a propositional
combination of inequalities involving <, constants from Q, and
variables. Functions are order theoretic if and only if their graphs
are order theoretic. Order invariant is order theoretic without
constants.

In the case of general H:Q^2k into Q^k, the H-bases turn out to be
more important for us than the finite H-bases.

We  now present three Perfectly Natural Templates like Templates
A,B,C. Because of the power of reductions, we do not have to use the
bidirectional notion of invariance. Of course, for equivalence
relations, one direction is equivalent to both directions.

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

TEMPLATE K. Let E be an order theoretic equivalence relation on
Q^k. For all order theoretic H:Q^2k into Q^k, every order
invariant relation on Q^k has an H-basis containing its E image.

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

It is tempting to consider Templates J,K,L, replacing "H-basis" with
"finite H-basis". This results in recursive unsolvability phenomena,
and no apparent CMI.

THEOREM 3.4. Each instance of Templates J,K,L is provably equivalent
to a Pi01 sentence via Goedel's Completeness Theorem.

Here we know much more than we do than we know about Templates A,B,C.
We can completely
analyze Templates J,k,L, but only using large cardinals.

THEOREM 3.5. Every instance of Templates J,K is either provable in
SRP or refutable in RCA_0. Every instance of Template L is either
provable in WKL_0 + Con(SRP) or refutable in RCA_0. We cannot replace
SRP by any fixed SRP[k], assuming SRP is consistent.

With H-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.

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

THEOREM 3.7. Proposition 3.6 is provably equivalent to Con(SRP) over WKL_0.

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

We also have the following multiple form.

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

THEOREM 3.8. Every instance of Templates M,N are either provable in
WKL_0 + Con(SRP) or refutable in RCA_0. We cannot replace SRP by any
fixed SRP[k] assuming SRP is consistent.

4. H-BASES IN Q^k - HUGE

We start with a rather trivial variant of Proposition 3.6 which we
repeat for the reader's convenience.

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

Recall that Q^k>= is the set of all decreasing (>=) elements of Q^k.

PROPOSITION 4.1. For all order theoretic H:Q^2k into Q^k>=, every
order invariant relation on Q^k has an H-basis whose elements include
those of its upper shift.

DEFINITION 4.1. Let S containedin Q^k. The p-sections of S are of the
form {x: (u,x) in S}, for some u in Q^p. Note that the 0-sections of S
are just S, and the p-sections of S are just emptyset for p >= k. The
sections of S are the aggregate of the p-sections.

PROPOSITION 4.2. For all order theoretic H:Q^2k into Q^k>=, every
order invariant relation on Q^k has an H-basis whose elements and
2-sections include those of its upper shift.

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

Some finesse is needed to prove Theorem 4.3 because of the use of +1.

THEOREM 4.4. Proposition 4.1 is provably equivalent to Con(SRP) over
WKL_0. Proposition 4.2 is provably equivalent to Con(HUGE) over WKL_0.

Here HUGE is the huge cardinal hierarchy.

5. p,H-BASES IN Q^k

p,H-bases represent Perfectly Natural finite approximations to H-bases.

DEFINITION 5.1. Let H:Q^2k into Q^k and R a binary relation on Q^k. A
p,H-basis for R consists of nonempty finite sets A_1 containedin ...
containedin A_p containedin Q^k such that for all i < p and x in
H[A_i^2], x in A_i+1 or x reduces to an element of A_i+1, but not
both.

The above represents the obvious Perfectly Natural way of setting up
finite approximations to H-bases. The next Proposition represents the
obvious Perfectly Natural way of giving a finite approximate form to
Proposition 3.6.

PROPOSITION 5.1. For all order theoretic H:Q^2k into Q^k, every order
invariant relation on Q^k has a p,H-basis, where the upper shift of
each term is contained in all succeeding terms.

Note that Proposition 5.1 is explicitly Pi02. However, there is an
obvious iterated exponential bound on the cardinality of and the
numerators and denominators needed for the finite H-basis. This
results in an explicitly Pi01 sentence.

THEOREM 5.2. Proposition 5.1 is provably equivalent to 1-Con(SRP) 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 563rd 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:34PM
562: Perfectly Natural Review #1  11/19/14  7:40PM

Harvey Friedman