[FOM] 585: Finite Continuation Theory 4
Harvey Friedman
hmflogic at gmail.com
Mon Jun 29 23:05:42 EDT 2015
Not so fast!! There is a problem with the last version,
http://www.cs.nyu.edu/pipermail/fom/2015-June/018798.html, which I
correct here.
SO LET'S START OVER. Continuation Theory came about by my reflecting
on the new statement in
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#87:
PROPOSITION 1. Every order invariant subset of Q^2k has a maximal
nonnegative root with S_1...n|>n = S_0...n-1|>n.
Here we are fixing the first n arguments to be 1,...,n, and to be
0,...,n-1, and taking the parts > n (i.e., where all coordinates are
>n). Proposition 1 is independent of ZFC. In fact, provably equivalent
to Con(SRP) over WKL_0.
I came up with
PROPOSITION 2. Every finite subset of Q|>n has a maximal nonnegative
continuation with S_1...n|>n = S_0...n-1|>n.
with the same metamathematical properties. Now rather than expanding
the context of continuation theory into richer mathematical contexts
(this is only being postponed), we have been looking at FINITE
Continuation Theory.
The advantage of Proposition 2 over Proposition 1 is that order
equivalence, used of course to define order invariant subsets of Q^2k,
is in Proposition 2 applied directly, without passing through the
unnecessary order invariant sets. This is a big simplification for
those not used to order invariant sets. However, I have found that
people used to order invariant sets - and these are very very basic
cases of nice sets such as piecewise linear sets - might even prefer
order invariant sets to continuations. Continuations are explained in
http://www.cs.nyu.edu/pipermail/fom/2015-June/018789.html and
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#87
I also came up with the outright equivalent of the set equation conclusion:
with S_1...n|>n = S_0...n-1|>n
with the embedding condition:
self embedded by +1 on {0,...,n-1}; identity on Q|>n.
HOWEVER, some people that were uncomfortable with the set equation,
when looking at the embedding condition, decided that the set equation
is rather simple after all, and preferred the set equation to the
embedding condition! Incidentally, in
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#87 you will see that any strictly increasing embedding that moves
only finitely many points will work in Proposition 1, and also in
Proposition 2 if all the points moved are <= n.
So it is by no means straightforward to squeeze the maximum acceptance
of such Propositions out of the very diverse mathematical community.
Here is my current plan:
1. The paper https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#87 will be retitled as:
Mathematically Natural Concrete Incompleteness: order invariant sets.
2. In that paper, there will be mention of Continuation Theory only in
the form of Proposition 2 above, with a reference to a second paper
which fully develops the Continuation Theory approach, with the title
Mathematically Natural Concrete Incompleteness: continuations.
3. Continuation Theory now seems to be leading to my most well
motivated explicitly Pi01 sentences. However, there do remain some
high quality explicitly Pi01 sentences in the "order invariant set"
approach than need to be retained.
FINITE CONTINUATION THEORY
DEFINITION 1. A k-system is an (A,<,R), where (A,<) is a finite linear
ordering and R containedin A^k. A continuation of (A,<,R) is an
(A',<',R'), where
i. (A',<',R') is a k-system, A containedin A', < containedin <', R
containedin R'.
ii. Every k-tuple from R' is order equivalent to some k-tuple from R.
Note that in ii we are using order equivalence between k^2-tuples via
concatenation of both k-tuples of k-tuples.
PROPOSITION 1. Every k-system (A,<,R) has a k-continuation (A',<',R')
with max(A) <' c_0 <' ... <' c_n = max(A') such that
i. (Weak Maximality). If every (x,c_0,...,c_n) order equivalent to a
given (y,c_0,...,c_n) in A^k+n+1 has (A,<,R) k-continued by (A',<',R'
union {x}), then y is in R'.
ii. (Symmetry). For max(x) < ' c_0, (x,c_1,...,c_n) is in R' if an
only if (x,c_0,...,c_n-1) is in R'.
Note that in i we are also using order equivalence between k^2-tuples
via concatenation of both length k lists of k-tuples.
Proposition 1 is explicitly Pi02. There is an a priori double
exponential upper bound on the size of the continuation relative to k
and |A|, yielding an explicitly Pi01 form.
THEOREM 2. Propositions 1 is provably equivalent to Con(SRP) over WKL_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 585th 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
563: Perfectly Natural Review #2 11/22/14 4:56PM
564: Perfectly Natural Review #3 11/24/14 1:19AM
565: Perfectly Natural Review #4 12/25/14 6:29PM
566: Bridge/Chess/Ultrafinitism 12/25/14 10:46AM
567: Counting Equivalence Classes 1/2/15 10:38AM
568: Counting Equivalence Classes #2 1/5/15 5:06AM
569: Finite Integer Sums and Incompleteness 1/515 8:04PM
570: Philosophy of Incompleteness 1 1/8/15 2:58AM
571: Philosophy of Incompleteness 2 1/8/15 11:30AM
572: Philosophy of Incompleteness 3 1/12/15 6:29PM
573: Philosophy of Incompleteness 4 1/17/15 1:44PM
574: Characterization Theory 1 1/17/15 1:44AM
575: Finite Games and Incompleteness 1/23/15 10:42AM
576: Game Correction/Simplicity Theory 1/27/15 10:39 AM
577: New Pi01 Incompleteness 3/7/15 2:54PM
578: Provably Falsifiable Propositions 3/7/15 2:54PM
579: Impossible Counting 5/26/15 8:58PM
580: Goedel's Second Revisited 5/29/15 5:52 AM
581: Impossible Counting/more 6/2/15 5:55AM
582: Link+Continuation Theory 1 6/21/15 5:38PM
583: Continuation Theory 2 6/23/15 12:01PM
584: Finite Continuation Theory 3 6/26/15 7:51PM
Harvey Friedman
More information about the FOM
mailing list