[FOM] 709: Large Cardinals and Continuations/19

Tue Sep 13 04:17:17 EDT 2016

THIS POSTING IS SELF CONTAINED

We present new expositional ideas that fit naturally into the
Introduction section of the outline below from
http://www.cs.nyu.edu/pipermail/fom/2016-August/020050.html

This modified expositional approach in the Introduction restricts the
discussion to three dimensions only, where it is particularly easy to
visualize, and where the metaphorical interpretations are of course
most direct in light of the fact that we live in 3 dimensional space.
The obvious lifting to k dimensions is made in the body starting with
section 2.1.1.

In the Lead Statement from the Introduction, catalogued as MCT3/1
(dimension 3, version 1), we use the two points (0,1/2,0), (1/2,1,0)
on the xy plane. This immediately raises the question of which pairs
of points can be used, and more generally, which finite sets of pairs
of points can be used. This turns out to have a transparent exact
answer. In the 3 dimensions of the Introduction, we think that this
cannot be proved in ZFC, although we are not in a position to claim
this before getting immersed in all of the details in the claims we
have made thus far. In section 2.1.1, this 3 dimensional development
is transferred routinely to k dimensions, and there we know that the
Lead statement, MCT1, and the necessary and sufficient condition
statement, MCT3, is in fact equivalent to Con(SRP). Hence ZFC does not
suffice.

To keep ourselves oriented, here is the outline from
http://www.cs.nyu.edu/pipermail/fom/2016-August/020050.html

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. CONTINUATION OF SETS OF NATURAL NUMBERS
   4.1. INFINITE SETS.
   4.2. FINITE SETS.
5. GREEDY k-CONTINUATION OF LINEARLY ORDERED DIRECTED GRAPHS.
6. FULL k-CONTINUATION  OF LINEARLY ORDERED DIRECTED GRAPHS.
   6.1. OMEGA-GRAPHS.
   6.2. FLODIGS - COUNTS.
   6.3. EMBEDDING.

NOTE: HUGE and beyond is present in 5, where we give extremely strong
implicitly Pi01.
HUGE and beyond is present in 6.3, where we give extremely strong
explicitly Pi01. However, the present form of  6.3 does not meet
current standards. But there is hope for simplification.

1. INTRODUCTION

The Introduction will essentially start with

section 1, Informal Symmetric Maximal Continuation, in
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html

We are still playing around with names like "Symmetric Maximal
Continuation", "Maximal Continuation Translation", etcetera. Here is
the way we are thinking now about names: there is a thread of
statements where the symmetry is translation symmetry. These
statements will be referred to as "Maximal Continuation Translation" =
MCT, and catalogued with suffixes. But then there is a thread of
statements that use embeddings and not translations. These will be
referred to as "Maximal Continuation Embedding" = MCE, and again
catalogued with suffixes. There is nothing involving graphs that uses
translations. They all use embeddings. So the graph statements will be
referred to as "Maximal Graph Continuation" = MGC, and catalogued with
suffixes.

We now continue the Introduction as follows:

We now present a precise mathematical treatment of this informal
discussion. We confine our discussion to 3 dimensions where the ideas
are most readily accessible. This entire development in 3 dimensions
is revisited in section 2.1.1 in k dimensions.

DEFINITION 1.1. Q[-1,1] is the set of rational numbers in the closed
interval [-1,1].  Q[-1,0) is the set of negative rational numbers in
Q[-1,1].

We work in the space Q[-1,1]^3, which is a cube with sides of length
2, but with rational (coordinates of) points only. The subspace
Q[-1,0)^3 of negative points in Q[-1,1]^3 will also play an important
role.

DEFINITION 1.2. Let A,B be finite subsets of Q[-1,1]^3. A,B are
isomorphic if and only if for the unique increasing bijection h from
the coordinates of elements of A onto the coordinates of elements of
B, we have

     for all x,y,z in the domain of h, (x,y,z) is in A if and only if
(hx,hy,hz) is in B.

EXAMPLE. {(-1,1,1/2), (-1/3,-1/2.0), (-1/4,1/2,-1/2)} and
{(-1,7/8,1/2), (-1/4,-1/3.1/8), (-1/5,1/2,-1/3)} are isomorphic by
h(-1) = -1, h(-1/2) = -1/3, h(-1/3) = -1/4, h(-1/4) = -1/5, h(0) =
1/8, h(1/2) = 1/2, h(1) = 7/8, where h is undefined elsewhere.

For finite A,B to be isomorphic, it is clearly necessary but not
sufficient that they have the same number of elements. The sets of
triples of a given finite size are divided into finitely many
equivalence classes up to isomorphism. Isomorphism asserts that A,B
look the same from a relative order (<) of coordinates point of view.

DEFINITION 1.3. Let E be a subset of Q[-1,1]^3. S is a continuation of
E in Q[-1,1]^3 if and only if E containedin S containedin Q[-1,1]^3
and E,S have the same at most 2 element subsets up to isomorphism.
I.e., every at most two element subset of S is isomorphic to some
(necessarily at most two element) subset of E.

DEFINITION 1.4. S is a maximal continuation of E in Q[-1,1]^3 if and
only if S is a continuation of E in Q[-1,1]^3 and E is not a proper
subset of any continuation of E in Q[-1,1]^3.

MCT3/1 IDEA. For finite subsets of Q[-1,0)^3, some maximal
continuation in Q[-1,1]^3 exhibits some specific translation symmetry.

The given finite subset of Q[-1,0)^3 is the seed (toward a corner
below ground), and the resulting maximal continuation is the plant
(generally below, on, and above ground). Every little pattern in the
plant is already in the seed (think DNA), and the plant has grown to
full maturity, without having any room to go further within Q[-1,1]^3
(maximality).

DEFINITION 1.5. Let S be a subset of Q[-1,1]^3. We say that S
translates between the drops of (x,y,z) and (u,v,w) if and only if z =
w and for all 0 <= p < z, (x,y,p) is in S if and only if (z,w,p) is in
S.

Here "drop" can be looked at as follows The drop of (x,y,z) in
Q[-1,1]^3 is the line segment from (x,y,z) down to (x,y,-1), where we
include the endpoint (x,y,-1) but exclude the endpoint (x,y,z). We
consider the drop of (x,y,-1) to be empty. If z = w then there is a
unique translation between the drops of (x,y,z) and (u,v,w), by
sending (x,y,p) to (u,v,p), -1 <= p < z. We require that membership in
S remains unchanged when we move according to this translation.

MCT3/1. For finite subsets of Q[-1,0)^3, some maximal continuation in
Q[-1,1]^3 translates between the drops of (0,1/2,0) and (1/2,1,0).

Our proof of MCT3/1 goes well beyond the usual ZFC axioms for
mathematics. But we think it likely that ZFC suffices. The k
dimensional form of MCT3/1 is the MCT/1 of section 2.1.1. We know that
for MCT/1 it is necessary and sufficient to go well beyond ZFC. But
here we continue to stay in 3 dimensions.

Note that in the definition of continuation, we used only isomorphisms
between at most 2 element sets. This is naturally generalized to at
most r element sets in the most straightforwardly way so that
continuations are simply 2-continuations:

DEFINITION 1.6. Let E be a subset of Q[-1,1]^3. S is an r-continuation
of E in Q[-1,1]^3 if and only if E containedin S containedin Q[-1,1]^3
and E,S have the same at most r element subsets up to isomorphism.
I.e., every at most r element subset of S is isomorphic to some
(necessarily at most r element) subset of E. S is an r-maximal
continuation of E in Q[-1,1]^3 if and only if S is an r-continuation
of E in Q[-1,1]^3 and E is not a proper subset of any r-continuation
of E in Q[-1,1]^3.

MCT3/2. For finite subsets of Q[-1,0)^3, some maximal r-continuation
in Q[-1,1]^3 translates between the drops of (0,1/2,0) and (1/2,1,0).

Our proof of MCT3/1 readily adapts to MCT3/2. We judge an even chance
that MCT3/2 can be proved in ZFC.

We now get away from picking two particuar points (0,1/2,0), (1/2,1,0)
to drop from. Of course, we can't just use any pair of points from
Q[-1,1]^3. For instance, by Definition 1.5, we require that the two
points have the same third coordinate. But stronger requirements must
be met. In fact, by very explicit constructions and arguments that can
be seen to work in very weak fragments of ZFC (in fact, in RCA_0, (our
base theory for Reverse Mathematics).

DEFINITION 1.7. x,y in Q[-1,1]^3 are drop similar if and only if
i. x_3 = y_3.
ii. x_1 < x_2 iff y_1 < y_2.
iii. x_2 < x_1 iff y_2 < y_1.
iv. min(x_1,y_1) < max(0,x_3) implies x_1 = y_1.
v. min(x_2,y_2) < max(0,x_3) implies x_2 = y_2.

In section 2.1 we put Definition 1.7 into context by defining order
equivalence of tuples and order equivalence of tuples over a set. Then
conditions ii-v are equivalent to: (x_1,x_2) and (y_1,y_2) are order
equivalent over Q[-1,max(0,x_3))..

By elementary arguments in RCA_0, we see that drop similarity is necessary:

THEOREM 1.1. Let r >= 2 and x,y in Q[-1,1]^3. Suppose that MCT3/2
holds using x,y. Then x,y are drop similar.

Theorem 1.1 is best possible in the following strong multiple sense.

MCT3/3. Let x[1],...,x[n],[y[1],...,y[n] in Q[-1,1]^3. The following
are equivalent.
i. For finite subsets of Q[-1,0)^3, some maximal continuation in
Q[-1,1]^3 translates, for all i, between the drops of x[i] and y[i].
ii. For r >= 1 and finite subsets of Q[-1,0)^3, some maximal
r-continuation in Q[-1,1]^3 translates, for all i, between the drops
of x[i] and y[i].
iii. For all i, x[i] and y[i] are drop similar.

Our proof of MCT3/1 adapts to MCT3/3 and goes well beyond ZFC. We
judge it likely that ZFC is not sufficient to prove MCT3/3.

Drop translation is a special case of line (segment) translation and
box translation, as drops are both line segments and boxes, and the
correspondence we are using between drops is a translation in the
usual sense. This is taken up in section 2.1.1. However, some
unresolved issues arise in this more general context.

Harvey Friedman

***********************************************
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 709th 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
704: Large Cardinals and Continuations/17  8/31/16  12:55AM
705: Large Cardinals and Continuations/18  8/31/16  11:47PM
706: Second Incompleteness/1  7/5/16  2:03AM
707: Second Incompleteness/2  9/8/16  3:37PM
708: Second Incompleteness/3  9/11/16  10:33PM

Harvey Friedman