[FOM] 710: Large Cardinals and Continuations/20

Wed Sep 14 01:27:34 EDT 2016

THIS POSTING IS SELF CONTAINED

Continuation Theory has a rather clear metaphorical content with seeds
to plants, conception to adulthood, big bang, etcetera. And more can
be done to strengthen the metaphors.

But mathematically, the Continuation setup can be easily simplified
mathematically at the cost of weakening the metaphors. The purpose of
this posting is to present a simplified mathematical theory, with the
same results, We call this Emulation Theory. Emulation Theory is not
intended to replace Continuation Theory, but to complement it.

In Emulation Theory, we work with emulations and maximal emulations
instead of continuations and maximal continuations. Emulations are the
same as continuations except that we remove the requirement that the
emulation be a superset.

Emulation theory has the clear advantage over continuation theory,
mathematically, whenever I am simply taking one continuation/emulation
of one set or graph. This includes all of section 2 and all of the
satisfactory statements that correspond to HUGE and beyond.

Emulation theory does have an awkward feature when we work with chains
as in all of the explicitly Pi01 forms. Namely, the first emulation is
not required to be a superset, but the further ones in the chain are
required to be supersets - i.e., continuations and not just
emulations. This awkwardness, and also the weakening of the plan/see,
conception/maturity, big bang, etc., metaphors, were the main reasons
why I have avoided emulations.

However, in defense of emulations, it really is true that for (almost
all of) the implicitly Pi01 statements, they are mathematically
simpler. But also there is an altered metaphor which is in fact still
quite good. And that is why I use the word "emulation".

So given any subset E of Q[-1,1]^k, we don't have to incorporate E
literally. We can simply emulate E, without copying (any of) E. Well,
a plant does not really emulate a seed. It grows out of a seed, and
hence Continuation.

However, you may have a favorite example of something or another, and
you may wish to emulate it in your own way. Maybe you want to improve
on it. Maybe you want to emulate it but have more symmetry. In
particular, you may want to emulate it as much as possible
(maximality).

So I have decided that it is important to have Continuation Theory and
Emulation Theory side by side, with a careful explanation in the
Introduction as to the very close relationship between Continuation
and Emulation.

So I will now restate much of
http://www.cs.nyu.edu/pipermail/fom/2016-September/020070.html with
emulations, and we can see how things simplify - with the same
outcomes.

First the old outline, but now modified to take emulation into
account. Note that emulations are not used at all in sections 3,4,6
because of the awkwardness discussed above.

CONTINUATION THEORY
OUTLINE

1. INTRODUCTION.
2. INFINITE CONTINUATION/EMULATION.
   2.1.  MAXIMAL CONTINUATION/EMULATION IN Q[-1,1]^k.
      2.1.1. TRANSLATION.
      2.1.2. EMBEDDING.
   2.2. STEP MAXIMAL CONTINUATION/EMULATION 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/EMULATION 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

Incorporates http://www.cs.nyu.edu/pipermail/fom/2016-September/020070.html
But we will restart the numbering in this posting only. In the more
final versions, the emulation and continuation definitions will be
enmeshed, as well as the theorems to some extent. Below MET
abbreviates Maximal Emulation Theory.

DEFINITION 1.1. Q[-1,1] is the set of rational numbers in the closed
interval [-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 an emulation of
E in Q[-1,1]^3 if and only if S containedin Q[-1,1]^3
and 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 emulation of E in Q[-1,1]^3 if and
only if S is an emulation of E in Q[-1,1]^3 and E is not a proper
subset of any emulation of E in Q[-1,1]^3.

MET3/1 IDEA. For subsets of Q[-1,1]^3, some maximal
emulation in Q[-1,1]^3 exhibits some specific translation symmetry.

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.

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

It is clear that MET3/1 with and without finite are equivalent.

Our proof of MET3/1 goes well beyond the usual ZFC axioms for
mathematics. But we think it likely that ZFC suffices. The k
dimensional form of MET3/1 is the MET/1 of section 2.1.1. We know that
for MET/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-emulation
of E in Q[-1,1]^3 if and only if S containedin Q[-1,1]^3
and 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
emulation of E in Q[-1,1]^3 if and only if S is an r-emulation
of E in Q[-1,1]^3 and E is not a proper subset of any r-emulation
of E in Q[-1,1]^3.

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

Our proof of MET3/1 readily adapts to MET3/2. We judge an even chance
that MET3/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 related 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) < x_3 implies x_1 = y_1.
v. min(x_2,y_2) < 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,x_3).

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

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

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

MET3/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,1]^3, some maximal emulation 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,1]^3, some maximal
r-emulation 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 related.

Our proof of MET3/1 adapts to MET3/3 and goes well beyond ZFC. We
judge it likely that ZFC is not sufficient to prove MET3/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 710th 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
709: Large Cardinals and Continuations/19  9/13/16 4:17AM

Harvey Friedman