[FOM] 704: Large Cardinals and Continuations/17

[Harvey Friedman]

As promised in http://www.cs.nyu.edu/pipermail/fom/2016-August/020041.html
we give the key definitions that are used in that long outline of
current Continuation Theory. We started this in  in
http://www.cs.nyu.edu/pipermail/fom/2016-August/020041.html, but now
we will start over with a new streamlined Outline.

We will do section 1-3 in this posting, and reserve sections 4,5 in
the next posting - do keep the lengths of these postings manageable.

We have cut down our Outline considerably. We remove the stuff we
presented about graphs there, and instead add two new sections 4.5
about graphs. (The earlier stuff about graphs may resurface later).
All of the full and greedy continuation ideas are put into this new
graph material.

All statements are equivalent to Con(SRP), with the exception of some
in section 4 and some in section 5.3, where they are equivalent to
Con(HUGE) and even stronger - between I3 and I2. In particular,
between j:V(kappa) into V(kappa) and j:V(kappa + 1) into V(kappa + 1).

We remind the reader of the heavily featured Lead and Lead Template:

LEAD. For finite subsets of Q[-1,0)^k+1, some maximal continuation in
Q[-1,1]^k+1 translates between the open line segments obtained by
dropping 1 from the points (0,1,...,k-1)/k, (1,2,...,k)/k positioned
in the hyperplane x_k+1 = 0.

LEAD TEMPLATE. Let L and L' be line segments in Q[-1,1]^k.
For finite subsets of Q[-1,0)^k, some maximal continuation in
Q[-1,1]^k translates between L and L'.

A line segment in Q[-1,1]^k consists of rational points only and has
endpoints from Q[-1,1]^k.

EXPOSITIONAL STRATEGY: I plan to first present the Lead in three
dimensions only, so the Lead statement involves just dropping 1 from
the familiar two points (0,1/2), (1/2,1) positioned in the familiar xy
plane. Of course, we emphasize that we do not know if this statement
in 3 dimensions is provable in ZFC.

STRONG POSSIBILITY. I doubt if the Lead in three dimensions is
independent of ZFC. However, if we use a stronger form of
continuation, where continuation in the Lead is like 2-continuation,
and instead use k-continuation, or perhaps even 3-continuation or
4-continuation, then there is a reasonable chance I will find that we
do have independence from ZFC in dimension 3. However, I need to be
immersed in the details of the reversals before claiming this.

We don't have a complete analysis yet of the Lead Template. The main
category where we do have a complete analysis is where there is an
order theoretic bijection between the two given line segments in
Q[-1,1]^k. ln the Lead, the two line segments obviously have an order
theoretic bijection, and even an order theoretic translation.

>From the point of view of vivid metaphors, as in
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html, section 1,
we need only consider section 2.1.1. Thus for the reader focused
entirely on vivid metaphors, they only need to look at section 1,
preliminary material before section 2.1.1, and an intial portion of
section 2.1.1. They can forget about the rest.

Recall that explicitly Pi01 statements are provably equivalent to
(unnatural) explicitly Pi01 statements, and also explicitly Pi01
statements are provably falsifiable. I.e., we know that if they are
false then they are provably false in a weak fragment of ZFC.

CONTINUATION THEORY
OUTLINE

1. INTRODUCTION.
2. INFINITE CONTINUATION OF FINITE SETS.
   2.1.  MAXIMAL CONTINUATION IN Q[-1,1]^k.
      2.1.1. TRANSLATION.
      2.1.2. EMBEDDING.
   2.2. STEP MAXIMAL CONTINUATION IN Q^k.
      2.2.1. TRANSLATION.
      2.2.2. EMBEDDING.
3. FINITE CONTINUATION OF FINITE SETS.
   3.1.  FINITE HEIGHT MAXIMAL CONTINUATION IN Q[-1,1]^k.
      3.1.1. TRANSLATION.
      3.1.2. EMBEDDING.
   3.2. FINITE HEIGHT STEP MAXIMAL CONTINUATION IN Q^k.
      3.2.1. TRANSLATION.
      3.2.2. EMBEDDING
4. GREEDY k-CONTINUATION OF LINEARLY ORDERED DIRECTED GRAPHS.
5. FULL k-CONTINUATION  OF LINEARLY ORDERED DIRECTED GRAPHS.
   5.1. OMEGA-GRAPHS.
   5.2. FLODIGS - COUNTS.
   5.3. EMBEDDING.

In the Introduction, we provide enough definitions to state there, the
Lead and Lead Template. All other definitions are given in the body as
needed - with the sole exception of order theoretic, which plays such
a fundamental role.

DEFINITION 1.1. Q,Z,N are the set of rationals, integers, and
nonnegative integers, respectively. Unless indicated otherwise,
a,b,c,d,p,q, with or without subscripts, range over rational numbers,
n,m,r,s,t, with or without subscripts, range over positive integers.
Q[(,p,q)] is the interval of rationals with left endpoint p and right
endpoint q, with any of the four endpoint situations. For S
containedin Q^k and c in Q^k, S + c = {x+c: x in S}.

DEFINITION 1.2. Let A containedin Q^k. The field of A, fld(A), is the
set of all coordinates of elements of A. h is an isomorphism between
A,B containedin Q^k if and only if h is an increasing bijection from
fld(A) onto fld(B) such that for all p_1,...,p_k in fld(A),
(p_1,...,p_k) in A iff (h(p_1),...,h(p_k)) in B. A,B containedin Q^k
are isomorphic if and only if there is an isomorphism between A,B.

DEFINITION 1.3. S is a continuation of A in B containedin Q^k if and
only if A containedin S containedin B, and A,S have the same subsets
of cardinality at most 2 up to isomorphism.

DEFINITION 1.4. S is a maximal continuation of A in B containedin Q^k
if and only if S is a continuation of A in B which is not a proper
subset of any continuation of A in B.

DEFINITION 1.5. S containedin Q^k translates between A,B containedin
Q^k if and only if there exists c in Q^k such that (S intersect A) + c
= (S intersect B).

DEFINITION 1.6. Let x,y in Q^k. The open line segment between x,y is
{x + p(y-x): 0 < p < 1}. The closed line segment between x,y is {x +
p(y-x): 0 <= p <= 1}. The left closed (right open) line segment
between x,y is {x + p(y-x): 0 <= p < 1}. The right closed (left open)
line segment between x,y is {x + p(y-x): 0 < p <= 1}.

DEFINITION 1.7. A containedin Q^k is order theoretic if and only if A
= {x in Q^k: phi}, where phi is a propositional combination of
inequalities x_i < x_j, x_i < p, p < x_j, where 1 <= i,j <= k and p in
Q.

The next main definition comes in section 2 (before section 2.1).

DEFINITION 2.1. h embeds S containedin Q^k if and only if h is an
increasing function with dom(h) U rng(h) containedin Q, and for all
p_1,...,p_k in dom(h), (p_1,...,p_k) in S iff (h(p_1),...,h(p_k)) in
S. h totally embeds S containedin Q^k if and only if h embeds S and
fld(S) containedin dom(h). h critically (totally) embeds S containedin
Q^k if and only if h (totally) embeds S and there is a least p such
that h(p) not= p.

The next main definition comes in section 2.2 (before section 2.2.1).

DEFINITION 2.2.1. For E containedin Q^k, S|<=p = {x in S: max(x) <=
p}. S is a step maximal continuation of A containedin Q^k if and only
if for all n, S|<=n is a maximal continuation of A within Q^k|<=n.

The next main definitions come in section 3 (before section 3.1).

DEFINITION 3.1. The height of x in Q^k, written hgt(x), is the least n
such that x can be written with all numerators and denominators of
magnitude at most n. For finite A containedin Q^k, hgt(A) is the
maximum of the hgt(x), x in A.

DEFINITION 3.2. S is a height maximal continuation of A in B
containedin Q^k if and only if S is a finite continuation of A in B,
where there is no continuation S U. {x} of A in B with hgt(x) <=
hgt(A).

DEFINITION 3.3. S is a height step maximal continuation of A in B
containedin Q^k if and only if for all n <= max(fld(A)), S|<=n is a
height maximal continuation of A within Q^k|<=n.

DEFINITION 4.1. A digraph is a pair G = (V,E), where V is the nonempty
set of vertices, and E containedin V^2 is the set of edges. A flodig
(clodig) is a triple (V,<,E), where (V,E) is a graph, and < is a
strict linear ordering on finite (countable) V. The sets {w in V: v E
w and v > w} are the lower neighborhoods.

DEFINITION 4.2. Let G = (V,<,E) be a clodig and A,B containedin E^2.
fld(A) is the set of coordinates of elements of A. h is an isomorphism
from A onto B if and only if h is an increasing bijection from fld(A)
onto fld(B), where for all v,w in fld(A), v E w iff hv E hw.

DEFINITION 4.3. Let G = (V,<,E) be a clodig. G' is a greedy
k-continuation of G if and only if G' is a clodig (V',<',E'), where V
containedin V', < containedin <', E containedin E', and for all x in
V'^2<, x in E if and only if every at most k element subset of
E'|<max(x) U {x} U E is isomorphic to some subset of E.

Note that we have been using digraphs rather than graphs, and also
given special status in Definition 4.3 to edges (v,w) with v < w. We
need this for obtaining the really strong embedding properties, that
correspond to the HUGE cardinal hierarchy and beyond. Note that graphs
can be viewed as edge symmetric digraphs with no loops.

DEFINITION 4.4. Let G = (V,<,E) be a clodig. h embeds G if and only if
h:V into V is increasing (<), where for all v,w in dom(h), v E w iff
hv E hw. h nontrivially embeds G if and only if h embeds G and h is
not the identity on V.

DEFINITION 5.1. Let G = (V,<,E) be a clodig. G' is a full
k-continuation of G if and only if G' is a clodig (V',<',E'), where V
containedin V', < containedin <', E containedin E', and for all x in
V'^2<, x in E if and only if every at most k element subset of
E'|<max(x) U {x} U E is isomorphic to some subset of E.

DEFINITION 5.2. An omega-graph is a clodig where (V,<) is of order type omega.

Sections 5.1 and 5.2 follow the omega-graph material in
http://www.cs.nyu.edu/pipermail/fom/2016-August/020041.html, section
3,4, corresponding to MAHLO, using Definition 5.1.

In section 4, we have

PROPOSITION. Every flodig has a full k-continuation with an embedding
with a least vertex moved.

which is equivalent to Con(SRP) over WKL_0. Also

PROPOSITION. Every flodig has a full k-continuation with a nontrivial
embedding mapping each {v: v < w} onto a lower neighborhood.

which is equivalent to Con(HUGE) over WKL_0.

Right now, I don't think that section 5.3 meets current standards for
Concrete Incompleteness, which have risen very much this year.

The next step is to move from these FOM postings on Continuation
Theory to the paper discussed at the beginning of
http://www.cs.nyu.edu/pipermail/fom/2016-August/020031.html. When it
is put on my website I will post the link.

***********************************************
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 704th 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
702: Large Cardinals and Continuations/15  8/22/16  9:22PM
703: Large Cardinals and Continuations/16  8/26/16  12:03AM

Harvey Friedman