[FOM] 702: Large Cardinals and Continuations/15

Mon Aug 22 21:22:47 EDT 2016

1. EXPOSITIONAL CHANGES IN
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html
2. THREE DIMENSIONS?
3. HEIGHT MAXIMAL CONTINUATIONS
4. CONTINUATION OF INFINITE GRAPHS - NEW
5. CONTINUATION OF FINITE GRAPHS - NEW

1. EXPOSITIONAL CHANGES IN
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html

I have just committed to publishing an Introduction to Continuation
Theory. Due to page limit and time restrictions, this paper will only
cover the material in the link above, but with some expositional
improvements. It will have a complete proof of the lead proposition
and some further statements, from Con(SRP). Reversals will come next
year, and of course this is far more elaborate.

The lead statement in the link asserts that for finite subsets of
Q[-1,0)^k+1, some maximal continuation in Q[-1,1]^k+1 translates from
one particular line segment onto another particular line segment. I
wrote the lines as

Q[-1,0) x {(0,1/k,...,(k-1)/k)}
Q[-1,0) x (1/k,2/k,...,k/k)}.

I want to adjust notation here. There will be no content change - just
purely notational.

The entirely compelling nature of the lead statement is made clearer
by using FOUR POINTS and not two Cartesian products with singleton
vectors. I shied away from this before because it definitely increases
the physical length of the statement. But this physical length really
consists of the most natural kind of geometric information, stated
with the most natural kind of English. Furthermore, it immediately
conveys in vivd terms the absolutely fundamental character of the
statement.

What do I mean by FOUR POINTS? Let a,b,c,d in Q]-1,1\^k. We talk of
the open line segment from x to y, and the open line segment from z,w.
Note that I moved to open line segments instead of half open line
segments. This is of course more symmetric, but also if I am going to
be using English to describe line segments, I definitely want the open
line segments I don't want half open line segments where I have to
explain what that is and which of the two possible half open line
segments are being used. (The reversal will now need some fairly minor
refinements).

NEW LEAD STATEMENT

For finite subsets of Q[-1,0)^k+1, some maximal continuation in
Q[-1,1]^k+1 translates from the open line segment between
(0/k,...,(k-1)/k,0) and (0//k,...,(k-1)/k,-1), onto the open line
segment between (1/k,...,k/k,0) and (1/k,...,k/k,-1).

The above statement is trivially equivalent to the present Lead
Statement that has remained unchanged for quite a while.

We can "see" these two open line segments as follows. Start with
Q[-1,1]^k, obtained by fixing the last coordinate to be 0. This is
very familiar in 3 dimensions with k = 2. In 3 dimensions, it would be
what is normally called the xy plane.

Given any x in Q[-1,1]^k, we can see the open line segment obtained by
dropping straight down from x for distance 1. In the Lead Statement,
we are dropping down from (0/k,...,(k-1)/k) and (1/k,...,k/k) for
distance 1. Which two k-tuples can we use for this? Exactly those in
Q[-1,1]^k that are order equivalent over Q[-1,0). That this is
necessary is provable in RCA_0. That this is sufficient is equivalent
to Con(SRP) over WKL_0/

TEMPLATE. Let x,y,z,w in Q[-1,1]^k. For finite subsets of Q[-1,0)^k,
some maximal continuation in Q[-1,1]^k translates from OLS(x,y) onto
OLS(z,w).

Here OLS is read "open line segment".

tWe seek to determine the quadruples x,y,z,w for which the Template
holds. A complete determination is still open, but i have a lot of
information on this, a fairly long story.

There is a natural category of x,y,z,w for which we do have a complete
determination. This is the case where the unique translation from
OLS(x,y) onto OLS(z,w) is order theoretic.This case includes the
x,y,z,w in the Lead Statement.

It is also important to consider multiple forms.

TEMPLATE. Let x_1,...,x_n,y_1,...,y_n,z_1,...,z_n,w_1,...,w_n in
Q[-1,1]^k. For finite subsets of Q[-1,0)^k, some maximal continuation
in Q[-1,1]^k translates, for each i, from OLS(x_i,y_i) onto
OLS(z_i,w_i).

This is of course much more delicate, but we do have some results here as well.

In addition to lines, we work with boxes, which are products of
rational intervals (possibly degenerate). Again, the order theoretic
case is completely determined.

For both the line and box cases, there are some results for the non
order theoretic cases. Note that all boxes are order theoretic, yet
only certain lines are order theoretic.

Another important development is EMBEDDINGS. These take the form of
partial h:Q[-1,1] into Q[-1,1].

TEMPLATE. Let partial h:Q[-1,1] into Q[-1,1] be order theoretic. For
finite subsets of Q[-1,0)^k, some maximal continuation in Q[-1,1]^k is
h embedded.

We also have a complete determination here. As in the case of line
segment and box translation, multiple partial embeddings present
additional unmet challenges. The same for piecewise linear and
Presburger embeddings .Presburger here means definable in (Q,<,Z,+).

Of course, all of these determination theorems, and all of the
sufficiency theorems, are equivalent to Con(SRP), and all of the
necessity theorems are proved in RCA_0.

2. THREE DIMENSIONS?

The reversal situation is too delicate for me to make a definite claim
about three dimensions. I need to be immersed in writing reversals
before I can see three dimensions clearly reversed. But I anticipate
being able to do this (and struggle hard if needed) - at least if I am
allowed k-continuations and not just continuations = 2-continuations.
Maybe something like 3-continuations will be enough.

Three dimensions has some major advantages. The metaphors with
seeds-to-plants, conception to maturity, and the big bang, etc., are
more compelling since we live in 3 dimensional space. Furthermore, the
two open line segments in question are obtained by dropping one unit
from (0,1/2) and (1/2,1) in the xy plane - very vivid.

3. HEIGHT MAXIMAL CONTINUATIONS

We weakened the notion of maximal continuation to accommodate that
finite subsets of Q[-1,1]^k can have finite maximal continuations in
Q[-1,1]^k. We used heights of rational vectors for this purpose.

We call this "height maximal continuations". For getting independence
from ZFC, we need only two successive height maximal continuations,
where only one of these is required to translate between our favorite
open line segments.

This is a simple and direct way of getting explicitly Pi02 and (with
obvious bounds) explicitly Pi01 statements independent of ZFC.

Is seems reasonable that this too should work in 3 dimensions, except
that we need to consider k successive height maximal continuations.
Alternately, 2 successive height maximal k-continuations.

4. CONTINUATION OF INFINITE GRAPHS - NEW

A natlog is a graph whose vertices are linearly ordered of order type
that of the natural numbers. I.e., (V,<,E), where (V,<) is a linearly
ordered set of vertices order isomorphic to (N,<), and E is an
irreflexive symmetric subset of E^2. A flog is a finite graph whose
vertices are linearly ordered. I.e., (V,<,E), where (V,<) is a
linearly ordered finite set of vertices and E is an irreflexive
symmetric subset of E^2.

We say that (V',<',E') is a k-continuation of natlog (V,<,E) if and only if

i. (V',<',E') is a natlog.
ii. V containedin V'.
iii. < containedin <'.
iv. E containedin E'.
v. (V,<,E) and (V',<',E') have the same sub flogs with at most k
vertices up to flog isomorphism.

These sub flogs are not necessarily induced sub flogs.

We say that (V',<',E') is a full k-continuation of natlog (V,<,E) if and only if

i. (V',<',E') is a k-continuation of (V,<,E).
ii. It is not possible to adjoin an x in V^2\E to E' and still have a
k-continuation.

We say that (V',<',E') is a greedy k-continuation of natlog (V,<,E) if
and only if

i. (V',<',E') is a k-continuation of (V,<,E).
ii. It is not possible to adjoin an x in V^2\E to E', and remove all
vertices in V'\V strictly above max(x), and still have a
k-continuation.

THEOREM 4.1. Every natlog starts an infinite sequence of greedy k-continuations.

The above is obvious, as we make one greedy k-continuation keeping the
same vertices, and just repeat it indefinitely.

PROPOSITION 4.2. Every natlog G starts two successive greedy
k-continuations G',G'', where strictly between any vertex in G' and
any strictly higher vertex in G, lies a vertex in G''.

PROPOSITION 4.3. Every natlog G starts n successive greedy
k-continuations, G_1,...,G_n, where for all i < n, strictly between
any vertex in G_i and any strictly higher vertex in G, lies a vertex
in G_i+1.

PROPOSITION 4.4. Every natlog G starts infinitely many successive
greedy k-continuations G_1,G_2,..., where for all i < n, strictly
between any vertex in G_i and any strictly higher vertex in G, lies a
vertex in G_i+1.

THEOREM. 4.5. Propositions 4.2-4.4 are each provably equivalent to
Con(SMAH) over ACA.

Can we use full k-continuations instead of greedy k-continuations here
for Theorem 4.5? Maybe, but I can't tell for sure until I get immersed
in the details of the proof of Theorem 4.5.

5. CONTINUATION OF FINITE GRAPHS - NEW

We say that (V',<',E') is a k-continuation of flog  (V,<,E) if and only if

i. (V',<',E') is a flog.
ii. V containedin V'.
iii. < containedin <'.
iv. E containedin E'.
v. (V,<,E) and (V',<',E') have the same sub flogs with at most k
vertices up to flog isomorphism.

We say that (V',<',E') is a full k-continuation of natlog (V,<,E) if and only if

i. (V',<',E') is a k-continuation of (V,<,E).
ii. It is not possible to adjoin an x in V^2\E to E' and still have a
k-continuation.

We say that (V',<',E') is a greedy k-continuation of natlog (V,<,E) if
and only if

i. (V',<',E') is a k-continuation of (V,<,E).
ii. It is not possible to adjoin an x in V^2\E to E', and remove all
vertices in V'\V strictly above max(x), and still have a
k-continuation.

PROPOSITION 5.1. Every flog G starts two successive greedy
k-continuations G',G'', where for all i, strictly between any vertex
in G' strictly below the i-th vertex in G, lies at least 1 and at most
(8ik)! vertices in G''.

PROPOSITION 5.2. Every flog G starts n successive greedy
k-continuations ,G_1,...,G_n, where for all i, and j < n, strictly
between any vertex in G_j strictly below the i-th vertex in G, lies at
least 1 and at most (8ijk)! vertices in G_j+1.

It is clear that Propositions 5.1 and 5.2 are explicitly Pi02.
Moreover, it is obvious that we require that G,G_1,...,G_n all have
the same highest vertex. This puts Propositions 5.1 and 5.2 in
explicitly Pi01 form.

THEOREM. 5.3. Propositions 5.1, 5.2 are each provably equivalent to
Con(SMAH) over ACA.

Can we use full k-continuations instead of greedy k-continuations here
for Theorem 5.3? Maybe, but I can't tell for sure until I get immersed
in the details of the proof of Theorem 4.3.

***********************************************
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 702nd 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-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

700: Large Cardinals and Continuations/14  8/1/16  11:01AM
701: Extending Functions/1  8/10/16  10:02AM

Harvey Friedman