[FOM] 572: Philosophy of Incompleteness 3

[Harvey Friedman]

I placed a new version of the Perfectly Natural extended abstract on my website:

[1]  https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
87. Perfectly Mathematically Natural Concrete Incompleteness  - order
theoretic relations. January 10, 2015, 24 pages. Extended abstract.
Supersedes December 14, 2014 version.

There are some new items here - especially new finite forms. In this
message, I want to review highlights from [1].

As you can see from posting #571, I have been struggling with S# for S
contained in Q^k. After much experiment, I have settled on what I had
previously. S# is the least E^k containing S union {0}^k. The
rationale for this does suggest some further developments that have
not yet been pursued.

The rationale goes like this. Q^k obviously has some very natural
subspaces. In particular, the E^k containedin Q^k. However, E may be
empty, and as in much of math, we don't usually like empty subspaces.
So we look at the subsapces E^k of Q^k that also contain the origin
(0,...,0). Then S# is simply the least subspace containing S.

This suggests that I have a space endowed with good subspaces, and
then go for an independent statement in that context. I won't pursue
that here.

Now note that the title of [1] includes "order theoretic relations".
So this means that [1] does not use addition. The use of addition
allows effective use of one dimensional sets. I already presented one
dimensional uses of addition in postings #569 and #570. I expect to
restart the discussion of (N,+) soon.

Now for the highlighting from [1].

There are two main Perfectly Naturals. The first has been constant for
quite a while, and has a very delicious target which I have a chance
of getting - or getting close to - already discussed in posting #571.
The second has changed, to set equation format, with the update
discussed in [1]. Also, I use the new second Perfectly Natural in
order to give new FInite Forms, presented in [1]. Let's take a look.

PROPOSITION 4.2.1. Every order invariant relation on Q[0,1]^k has a
maximal root whose projections at length r subsequences of
(1,1/2,...,1/n) agree below 1/n.

PROPOSITION 4.2.1. (target) Every order invariant relation on Q[0,1]^4
has a maximal root whose projections at length 3 subsequences of
(1,1/2,1/3,1/4) agree below 1/4.

As simple as this looks, most people not interested in f.o.m. will
generally regard it as best ignored as an isolated curiosity.This
includes a large majority of the math community, and may also include
most of the math logic community, having long ago abandoned primary
interest in f.o.m.

For these and other reasons, it is important to create a Strategic
Template which puts these statements into Perfectly Natural general
contexts. Of course, there is nothing to stop or even slow down people
not interested in f.o.m. to reflexively assert that the Strategic
Templates themselves are isolated curiosities! In fact, one can
reflexively say that anything that is not already been around and
certified as important by enough important people, for a critical
period of time, is an isolated curiosity! How I respond to this
situation is not the subject of this message, but should be clear
sometime during 2015.

TEMPLATE A. 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.

Note that every instance of Template A is provably equivalent to a
Pi01 sentence over WKL_0, via Goedel's Completeness Theorem.

Note that if we fix k,r,n in Proposition 4.2.1, then we obtain an
instance of Template A. We know that these instances include those
forming a cofinal path in logical strength through SRP.

However, we do not have the expected result that every instance of
Template A is provable or refutable in SRP. In fact, we conjecture in
[1] that every instance of Template A is provable in SRP or refutable
in RCA_0.

These conjectures, when established, show the effectiveness of large
cardinals in handling all problems of a certain Perfectly Natural kind
- not just isolated curiosities. This effectiveness cannot be obtained
just using ZFC, as we have shown.

We have been able to obtain partial results on these conjectures, say
by looking at specific kinds of P. A somewhat different kind of
related result is as follows.

TEMPLATE B. Let P be an order theoretic equivalence relation on
Q[0,1]^k. For all order theoretic equivalence relations P’ embeddable
in P, every order invariant relation on Q[0,1]^k has a P,P’ invariant
maximal root.

Here we have shown that every instance of Template B is provable from
SRP or refutable in RCA_0. ZFC is not sufficient.

We now come to the second of our Perfectly Naturals in [1].

PROPOSITION 5.2. Every order invariant R containedin Q^2k has an S =
S#\R<[S] containing its upper shift.

The above is also provably equivalent to Con(SRP) over WKL_0.

PROPOSITION 5.2. (target) Every order invariant R containedin Q^8 has
an S = S#\R<[S] containing its upper shift.

(Secretly, I will try this for 8 replaced by 6, but don't tell
anybody. And, more secretly, ...).

We expect that Proposition 5.2 is also provably equivalent to Con(SRP)
over WKL_0.

With a bit more effort, one can a priori see that Proposition 5.2 (and
the target) is provably equivalent to a Pi01 sentence over WKL_0 via
Goedel's Completeness Theorem.

In [1], we didn't pursue the Templating that we did with Proposition
4.2.1. But I will say something about Templating here in a certain
direction that does not appear in [1]. I should upgrade [1] at some
point to include this discussion of AA,BB,CC,?? below.

Note that Proposition 5.2 asserts that every order invariant R
containedin Q^2k has an S containedin Q^k such that something holds of
S,S#,ush(S),R<[S]. We would like to reflect also that R[S] is
apparently not going to get us to Incompleteness.

TEMPLATE AA. Let phi be a Boolean relation between four subsets of
Q^k. Every order invariant R contaiendin Q^2k has an S containedin Q^k
such that phi holds of S,S#,ush(S),R[S].

TEMPLATE BB. Let phi be a Boolean relation between four subsets of
Q^k. Every order invariant R contaiendin Q^2k has an S containedin Q^k
such that phi holds of S,S#,ush(S),R<[S].

TEMPLATE CC. Let phi be a Boolean relation between five subsets of
Q^k. Every order invariant R contaiendin Q^2k has an S containedin Q^k
such that phi holds of S,S#,ush(S),R[S],R<[S].

We conjecture that

i. Every instance of AA is provable in ZFC or refutable in RCA_0.
ii. Every instance of BB is provable in SRP or refutable in RCA_0.
iii. Every instance of CC is provable in SRP or refutable in RCA_0.

We have already seen that ii,iii are false with ZFC.

In my opinion, these Templates are tractable, and i-iii are reasonable targets.

Beyond i-iii, we can take such Templating much further. S#, ush(S),
R[S], R<[S] are certainly special cases of more general order
theoretic constructions - with ush(S) using +1, which is of course
just beyond order theoretic. I can see a vast subject of successively
more powerful templatings leading to something of this shape:

TEMPLATE ??. Every order invariant R containedin Q^2k has an S
containedin Q^k such that a given Boolean relation holds of a bunch of
subsets of Q^k reasonably obtained from R and S.

with the idea that every instance of Template ?? can be proved or
refuted using certain large cardinal hypotheses. Yet more radical is
to template "order invariant". That should be approached with great
care.

I can still hear complaints of "isolated curiosities" all the way till
an ultimate form of Template ?? is analyzed.

In [1], I took Proposition 5.2 much further, bringing in the projections:

PROPOSITION 5.2. Every order invariant R containedin Q^2k has an S =
S#\R<[S] containing its upper shift.

PROPOSITION 5.3. Every order invariant R containedin Q^2k has an S
=_>= S#\R<[S] whose elements and 2-projections include those of its
upper shift.

Here "=" is modified to "= sub >=" to mean that the two sides have the
same elements that are decreasing (>=). Proposition 5.3 is again
provably equivalent to a Pi01 sentence over WKL_0 via Goedel's
Completeness Theorem. Proposition 5.3 is provably equivalent to
Con(HUGE) over WKL_0. Very far ranging templating can also be tried
here, although I regard it as grossly premature. What seems reasonable
is to greatly limit the templating to the upper shift. This should be
very doable.

I then ventured into Finite Forms in [1]. The idea here is that,
although the above sentences are Pi01 via Goedel's Completeness
Theorem, they are not themselves explicitly Pi01 or even explicitly
arithmetical.

One point that I neglected to say in [1] is that all of the above
sentences are equivalent to the result of requiring that S be
arithmetical. Or that S be recursive in 0'. Thus we obtain
Arithmetical Incompleteness but relying on basic recursion theoretic
notions. This point got lost in the shuffle, and I certainly have made
this same point many times in much earlier versions along the 47+ year
journey.

Let's repeat Proposition 5.2 up against the Finite Form in [1].

PROPOSITION 5.2. Every order invariant R containedin Q^2k has an S =
S#\R<[S] containing its upper shift.

PROPOSIITON 6.1. Every order invariant R containedin Q^2k has n finite
sets S_i = S_i#\R<[S_i+1], each containing all S_j union ush(S_j), j <
i.

The comma replacing the period very nicely parses Proposition 6.1 for
readability.

For some inexplicable reason, I used "A" instead of "S" in Proposition
6.1, which will be corrected in a later version.

You can clearly see the close relationship between 5.2 and 6.1. I
think that if we set n = 4, then, quantifying over all k, we get
equivalence with Con(SRP). This is something I neglected to mention in
[1].

PROPOSITION 5.3. Every order invariant R containedin Q^2k has an S
=_>= S#\R<[S] whose elements and 2-projections include those of its
upper shift.

PROPOSITION 6.2. Every order invariant R containedin Q^2k has 2n
finite sets S_i =_>= S_i#\R<[S_i+1], each containing all S_j union
ush(S_j), j < i, where Si[0,n+(1/2)] = ush(Si)[n,n].

The above is the explicitly Pi01 form for Con(HUGE). Again, one can
fix n = 4, but one will not climb all the way up through HUGE. Roughly
4-huge. Is 6.2 Perfectly Natural? No, but it should improve.

************************************************************
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 572nd 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

Harvey Friedman