[FOM] 526: More Perfect Pi01

Harvey Friedman hmflogic at gmail.com
Sat Aug 9 12:09:24 EDT 2014

This research was partially supported by the John Templeton Foundation
grant ID #36297. The opinions expressed here are those of the author and do
not necessarily reflect the views of the John Templeton Foundation.

We discuss some new variants that have some advantages and disadvantages
over Proposition 4.3 of

82. Order Invariant Relations and Incompleteness, 7 pages, August 6, 2014.
Extended abstract.

We regard the Pi01 incompleteness there as "perfectly mathematically
natural". We maintain that this informal notion is clear enough to be fully
justified. We will discuss this notion "perfectly mathematically natural"
in a later posting. Even if a statement is perfectly mathematically
natural, there may be preferable variants. More later about that.

1. In and around Proposition 4.3.
2. On Q[0,1].
3. Below 1.


Recall that i,j,k,n,m,r,s,t range over positive integers in the abstract.

PROPOSITION 4.6. Every order invariant graph on Q^k has a maximal clique
whose sections at any (i,...,j),(i+1,...,j+1) agree below i.

PROPOSITION 4.3. Every order invariant graph on Q[0,n]^k has a maximal
clique whose sections at any (i,...,n-1),(i+1,...,n) agree below i.

Obviously Proposition 4.6 is preferable to Proposition 4.3, even if both
are perfectly mathematically natural. As stated in the extended abstract,
we know how to prove Proposition 4.6 from Con(SRP) but we do not yet know
if Proposition 4.6 is provable in ZFC.

Q[0,n] is just an example of a rational interval. Here is a form which
involves all rational intervals (endpoints are required to be extended

PROPOSITION A. Let J be a rational interval containing 0. Every order
invariant graph on J^k has a maximal clique whose sections at any
(i,...,j),(i+1,...,j+1) from J^k agree below i.

Proposition A is equivalent to Con(SRP) over WKL_0 even for finite length
J. In Proposition A, we can use any J except the closed intervals of length
at least 3 whose endpoints are positive integers.

2. ON Q[0,1]

There is an advantage to using exactly one interval.

PROPOSITION B. Every order invariant graph on Q[0,1]^k has a maximal clique
whose sections at any (1,1/2,...,1/i),(1/2,...,1/(i+1)) agree below

PROPOSITION C. Let A be a finite set of strictly increasing tuples from
Q[0,1] of length r. Every order invariant graph on Q[-1,1]^k has a maximal
clique whose sections at the elements of A agree below 0.

3. BELOW 1

PROPOSITION D. Every order invariant graph on Q[0,n]^k has a maximal clique
whose sections at (1,...,n-1),(2,...,n) agree below 1.

PROPOSITION E. Every order invariant graph on Q[0,n]^k has a maximal clique
whose sections at (1,...,n-1),(2,...,n),(1,3,...,n) agree below 1.

We do not know if Proposition D is provable in ZFC. However, we know that
Proposition E is provably equivalent to Con(SRP) over WKL_0.

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 526th 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-449 can be found
in the FOM archives at

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM
453: Rational Graphs and Large Cardinals III  1/20/11  2:33AM
454: Three Milestones in Incompleteness  2/7/11  12:05AM
455: The Quantifier "most"  2/22/11  4:47PM
456: The Quantifiers "majority/minority"  2/23/11  9:51AM
457: Maximal Cliques and Large Cardinals  5/3/11  3:40AM
458: Sequential Constructions for Large Cardinals  5/5/11  10:37AM
459: Greedy CLique Constructions in the Integers  5/8/11  1:18PM
460: Greedy Clique Constructions Simplified  5/8/11  7:39PM
461: Reflections on Vienna Meeting  5/12/11  10:41AM
462: Improvements/Pi01 Independence  5/14/11  11:53AM
463: Pi01 independence/comprehensive  5/21/11  11:31PM
464: Order Invariant Split Theorem  5/30/11  11:43AM
465: Patterns in Order Invariant Graphs  6/4/11  5:51PM
466: RETURN TO 463/Dominators  6/13/11  12:15AM
467: Comment on Minimal Dominators  6/14/11  11:58AM
468: Maximal Cliques/Incompleteness  7/26/11  4:11PM
469: Invariant Maximality/Incompleteness  11/13/11  11:47AM
470: Invariant Maximal Square Theorem  11/17/11  6:58PM
471: Shift Invariant Maximal Squares/Incompleteness  11/23/11  11:37PM
472. Shift Invariant Maximal Squares/Incompleteness  11/29/11  9:15PM
473: Invariant Maximal Powers/Incompleteness 1  12/7/11  5:13AMs
474: Invariant Maximal Squares  01/12/12  9:46AM
475: Invariant Functions and Incompleteness  1/16/12  5:57PM
476: Maximality, CHoice, and Incompleteness  1/23/12  11:52AM
477: TYPO  1/23/12  4:36PM
478: Maximality, Choice, and Incompleteness  2/2/12  5:45AM
479: Explicitly Pi01 Incompleteness  2/12/12  9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness  2/15/12  8:40AM
482: Maximality, Choice, and Incompleteness 2  2/19/12 7:43AM
483: Invariance in Q[0,n]^k  2/19/12  7:34AM
484: Finite Choice and Incompleteness  2/20/12  6:37AM__
485: Large Large Cardinals  2/26/12  5:55AM
486: Naturalness Issues  3/14/12  2:07PM
487: Invariant Maximality/Naturalness  3/21/12  1:43AM
488: Invariant Maximality Program  3/24/12  12:28AM
489: Invariant Maximality Programs  3/24/12  2:31PM
490: Invariant Maximality Program 2  3/24/12  3:19PM
491: Formal Simplicity  3/25/12  11:50PM
492: Invariant Maximality/conjectures  3/31/12  7:31PM
493: Invariant Maximality/conjectures 2  3/31/12  7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv  4/5/12  4:17PM
495: Invariant Finite Choice  4/5/12  4:18PM
496: Invariant Finite Choice/restatement  4/8/12  2:18AM
497: Invariant Maximality Restated  5/2/12 2:49AM
498: Embedded Maximal Cliques 1  9/18/12  12:43AM
499. Embedded Maximal Cliques 2  9/19/12  2:50AM
500: Embedded Maximal Cliques 3  9/20/12  10:15PM
501: Embedded Maximal Cliques 4  9/23/12  2:16AM
502: Embedded Maximal Cliques 5  9/26/12  1:21AM
503: Proper Classes of Graphs  10/13/12  12:17PM
504. Embedded Maximal Cliques 6  10/14/12  12:49PM
505: Function Transfer Theory 10/21/12  2:15AM
506: Finite Embedded Weakly Maximal Cliques  10/23/12  12:53AM
507: Finite Embedded Dominators  11/6/12  6:40AM
508: Unique Undefinable Elements  12/22/12  8:08PM
509: A Divine Consistency Proof for Mathematics  12/26/12  2:15AM
510: Unique Undefinable Elements Again  1/9/13  5:07PM
511: A Supernatural Consistency Proof for Mathematics   1/10/13  9:19PM
512: Countable Elementary Extensions  1/11/13  7:31PM
513: Five Supernatural Consistency Proofs for Mathematics  1/14/13  1:13AM
514: Countable Elementary Extensions/again  1/14/13  2:19AM
515: Eight Supernatural Consistency Proofs For Mathematics  1/19/13  2:40PM
516: Embedded Maximal Cliques/restatement  5/21/13  1:31PM
517: New Concrete Mathematical Incompleteness  8/2/13  9:57PM
518: Polynomial Independence  8/7/13  6:04AM
519: New Invariant Maximality  1/8/14  10:59PM
520: Incompleteness - 4 abstracts  6/23/14  10:15PM
521: Countable Model Theory and Incompleteness  6/27/14  10:51AM
522: Order Invariant Graphs and Incompleteness  7/1/14  6:04PM
523: Order Invariant Relations and Incompleteness  7/2014  1:23AM
524: Testing Consistency of Math  7/23/14  6:49AM
525:  Explicitly Finite Pi01  8/8/14  4:22PM

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20140809/4398893e/attachment.html>

More information about the FOM mailing list