[FOM] 731: Large Cardinals and Emulations//26

[Harvey Friedman]

We continue with the outline below from
http://www.cs.nyu.edu/pipermail/fom/2016-October/020137.html

Notice that we have simplified the outline. This is because

1. Step Maximal Emulation in Q^k really behaves the same as Maximal
Emulation in Q[0,1]^k, except that are some particularly convenient
ways to use the numbers 1,2,3,... in Q^k to give some nice additional
statements. The Step Maximal Emulation in Q^k situation can be
coherently presented in a single section 2.2.

2. The Emulation Towers of Finite Sets situation is also essentially
the same as the Infinite Emulation situation, once there is the
preliminary spadework of setting up Emulation Towers of Finite Sets
properly. In fact, we now give some equivalence theorems that assert
that statements of a certain kind surrounding section 2 are equivalent
to their corresponding statements in section 3, provably in WKL_0.

EMULATION THEORY
OUTLINE

1. INTRODUCTION.
2. INFINITE EMULATION.
   2.1.  MAXIMAL EMULATION IN Q[0,1]^k.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html
      2.1.1. TRANSLATION.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html
      2.1.2. EMBEDDING.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020137.html
   2.2. STEP MAXIMAL EMULATION IN Q^k.
here.
3. EMULATION TOWERS OF FINITE SETS.
here.
4. GREEDY EMULATION OF LINEARLY ORDERED DIGRAPHS.
   4.1. EMULATION.
   4.2. EMULATION/<=.
5. GREEDY EMULATION TOWERS OF SETS OF NONNEGATIVE INTEGERS.
   5.1. INFINITE SETS.
   5.2. FINITE SETS.
6. GREEDY EMULATION TOWERS OF LINEARLY ORDERED DIGRAPHS.
   6.1. OMEGA-GRAPHS.
   6.2. FLODIGS - COUNTS.
   6.3. EMBEDDING.

NOTE: HUGE and beyond is achieved in 4.2, where we give extremely strong
implicitly Pi01. HUGE and beyond is achieved in 6.3 with explicitly
Pi01, but the present form of  6.3 does not meet
current standards. There is hope for simplification.

1. INTRODUCTION

To review, the Intro starts with a narrative based on some metaphors
involving such things as seeds/plants, personal development, the big
bang, etc. These cases of maximal emulation lead to various forms of
beauty, or symmetry. Then the focus turns to rigorous formulations in
3 dimensions only, postponing any discussion of k dimensions to
section 2. I like the following exact terminology. MED is read
"maximal emulation drop".

MED/1. For subsets of Q[0,1]^3, some maximal emulation is drop
equivalent from (1,1/2,1/3) to (1/2,1/3,1/3).

MED/1 is likely is provable in ZFC although the natural proof is not
in ZFC. It is likely, but not claimed, that the more general

MED/2. For subsets of Q[0,1]^3, some maximal r-emulation is drop
equivalent from (1,1/2,1/3) to (1/2,1/3,1/3).

is independent of ZFC. Recall that drop equivalence now requires that
the last coordinates be equal. Already in the Introduction, we will
give a simple necessary and sufficient condition on a finite list of
pairs of triples such that for subsets of Q[0,1]^3, some maximal
r-emulation is drop equivalent from the first of any given pair to the
second. This is even more likely to be independent of ZFC.

NOTE: We changed the actual numbers above a bit. It used to be
(1,2/3,1/3), (2/3,1/3,1/3). I like this slightly better, especially in
k dimensions (see below).

MED/3. Let W be a finite set of pairs from Q[0,1]^3. The following are
equivalent.
i. For all (x,y) in W, x,y are order equivalent below x_3 = y_3.
ii. For subsets of Q[0,1]^3, some maximal emulation is drop equivalent
from the first to the second component of every pair in W.
iii. For subsets of Q[0,1]^3 and r >= 1, some maximal r-emulation is
drop equivalent from the first to the second component of every pair
in W.

with "order equivalent below p" defined in the obvious way.

Also we remark that all of these statements are implicitly Pi01 via
Goedel's Completeness Theorem. They are provable in SRP and even in
WKL_0 + Con(SRP). Also remark that iii implies ii implies i is easily
provable in RCA_0.

2. INFINITE EMULATION

2.1. MAXIMAL EMULATION IN Q[0,1]^k.

2.1.1. TRANSLATION

To review, this starts with a discussion of Drop Equivalence in k
dimensions. These are labeled by MED. The Lead in this section is
this:

MED/4. For subsets of Q[0,1]^k, some maximal emulation is drop
equivalent from (1,1/2,...,1/k) to (1/2,...,1/k,1/k).

MED/5. For subsets of Q[0,1]^k, some maximal r-emulation is drop
equivalent from (1,1/2,...,1/k) to (1/2,...,1/k,1/k).

MED/6. Let W be a finite set of pairs from Q[0,1]^k. The following are
equivalent.
i. For all (x,y) in W, x,y are order equivalent below x_k = y_k.
ii. For subsets of Q[0,1]^k, some maximal emulation is drop equivalent
from the first to the second component of every pair in W.
iii. For subsets of Q[0,1]^k and r >= 1, some maximal r-emulation is
drop equivalent from the first to the second component of every pair
in W.

These are claimed to be equivalent to Con(SRP) over WKL_0.

Then we remark that Drop Equivalence is a special case of Translation
Equivalence both for lines and for boxes. We discuss two additional
series of statements, MEL for lines and MEB for boxes. There are still
some open challenges left. Specifically, we aim to give a necessary
and sufficient condition on a finite list of pairs of lines or boxes,
that can be used. Even for a single pair of lines or boxes, this is
challenging. We can treat some natural major special cases.

For drop equivalence, see
http://www.cs.nyu.edu/pipermail/fom/2016-October/020105.html

For lines and boxes, see
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html

2.1.2. EMBEDDING

We present the MEE series. We use partial h:Q[0,1] into Q[0,1] as the
embeddings.There are still open questions left open here. If the
embeddings move at most finitely many points, then we have complete
control of the situation. This includes the case of order theoretic
embeddings.

See http://www.cs.nyu.edu/pipermail/fom/2016-October/020137.html

2.2. STEP MAXIMAL EMULATION IN Q^k

In Step Maximality, the nonnegative integers play a special role as
"steps". We also conveniently use the nonnegative integers for the
drop symmetry and embedding.

DEFINITION 2.2.1. S is a step maximal emulation(r-emulation) of E
containedin Q^3 if and only if for all n in N, S|<=n is an r-emulation
of E which is not a proper subset of any emulation (r-emulation) of E
that is contained in Q^k|<=n.

Basically, everything in section 2,1 carries over to this section 2.2,
with the same equivalences with Con(SRP). The statements with step
maximality imply the previous statements  with maximality. In fact,
the natural proofs of the latter actually prove the former.

The Step Maximality makes it easier to do reversals in 3 dimensions,
where likely we get independence from ZFC already with this:

SMED/1. For subsets of Q^3, some step maximal r-emulation is drop
equivalent from each x in N^3> to each y in N^3> with the same last
coordinate.

More generally,

SMED/2.  For subsets of Q^k, some step maximal r-emulation is drop
equivalent from each x in N^k> to each y in N^k> with the same last
coordinate.

THEOREM 2.2.1. SMED/2 is provably equivalent to Con(SRP) over WKL_0.

For embeddings, see
http://www.cs.nyu.edu/pipermail/fom/2016-October/020137.html Again it
is much easier to do reversals in 3 dimensions, where likely we get
independence from ZFC already with this:

SMEE/1. For subsets of Q^3, some step maximal r-emulation is, for all
n in N, embedded by the function p if p < n; p+1 if p in Z|>=n.

In k dimensions, we have

SMEE/2. For subsets of Q^k, some step maximal r-emulation is embedded
by the function p if p < 0; p+1 if p in N.

SMEE/3. For subset of Q^k, some step maximal r-emulation is, for all n
in N, embedded by the function p if p < n; p+1 if p in N|>=n.

THEOREM 2.2.2. SMEE/2, SMEE/3 are provably equivalent to Con(SRP) over WKL_0.

We can think of the passage from the maximality in section 2.1 to the
step maximality in this section 2.2 as a preview to the relatively
smooth kind of maximality in section 4. In section 4.2, we reach the
HUGE cardinal hierarchy in strength.

3. EMULATION TOWERS OF FINITE SETS.

Here we rework section 2 with finite sets only, thus obtaining
explicitly finite statements independent of ZFC. Recall that all of
the statements have been implicitly Pi01 in the sense of being
provably equivalent to Pi01 sentences via the Goedel Completeness
Theorem, as they can readily be put into the form "certain sentences
have countable models".But here these statements are Pi02 without
modification. There are obvious upper bounds on the existential
quantifiers, resulting in explicitly Pi01 statements. We can also use
the well known elimination of quantifiers for (Q,<) to convert the
Pi02 forms to Pi01.

These finite forms come out naturally as explicitly Pi02 sentences.
However, upper bounds can easily be placed on the existential
quantifiers so that the statements naturally become Pi01. These bounds
can either be can be obtained through the well known quantifier
elimination for (Q,<), or directly.

We view these finite forms as finite approximations to the original
infinite versions of section 2. We use the notion of the height of a
rational number to support finite approximations. This is also a
preferred vehicle in number theory. where heights are extensively
used.

DEFINITION 3.1. The height hgt(p) of a rational p is the least n such
that p can be written as a ratio of two integers of magnitudes at most
n. hgt(x), x in Q^k, is the maximum of the heights of its coordinates.
hgt(A), A containedin Q^k, is the maximum of the heights of its
elements, where we use infinity if A is infinite.

DEFINITION 3.2. Let E containedin Q[0,1]^k. S is a height maximal
r-emulation of E if and only if S is an r-emulation of E which is not
a proper subset of any r-emulation of E of height at most that of E.

HMED/1. For finite subsets of Q[0,1]^k, some finite height maximal
r-emulation extends to some finite height maximal r-emulation which is
drop equivalent from (1,1/2,...,1/k) to (1/2,...,1/k,1/k).

DEFINITION 3.3. A height maximal r-emulation tower is a sequence of
finite subsets of Q[0,1]^k of finite or infinite length, where each
A_i+1 is a height maximal r-emulation of A_i that contains A_i.

HMED/2. For finite subsets of Q[0,1]^k, some finite height maximal
r-emulation starts a height maximal r-emulation tower of length t
whose terms are drop equivalent from (1,1/2,...,1/k) to
(1/2,...,1/k,1k).

Note that HMED/1 and HMED/2 are explicitly Pi02. We can give Pi01
forms as follows.

HMED/3. For finite E containedin Q[0,1]^k, some finite height maximal
r-emulation extends to some finite height maximal r-emulationof height
at most (right(E))!! which is drop equivalent from (1,1/2,...,1/k) to
(1/2,...,1/k,1/k).

HMED/4. For finite E containedin Q[0,1]^k, some finite height maximal
r-emulation starts a height maximal r-emulation tower of length t
whose terms are of height at most (rthft(E))!! and drop equivalent
from (1,1/2,...,1/k) to (1/2,...,1/k,1k).

THEOREM 3.1. HMED/1-4 are provably equivalent to Con(SRP) over WKL_0.

There is a general equivalence principle between maximal r-emulations
and hgt maximal r-emulation towers. This covers the above as a special
case.

THEOREM 3.2. The following is provable in WKL_0. Let
F_1,...,F_p:(Q]0,1]^k)^m into Q[0,1]^k. The following are equivalent.
i. For finite subsets of Q[0,1]^k, some finite height maximal
r-emulation extends to some finite height maximal r-emulation S with
each F_i[S^m] containedin S.
ii. For finite subsets of Q[0,1]^k, some finite height maximal
r-emulation starts a finite height maximal r-emulation tower of length
t whose terms S have each F_i[S^m] containedin S.
iii. For finite E containedin Q[0,1]^k, some finite height maximal
r-emulation extends to some finite height maximal r-emulation S, of
height at most hft(rhgt(E))!!, with each F_i[S^m] containedin S.
iv. For finite E containedin Q[0,1]^k, some finite height maximal
r-emulation starts a finite height maximal r-emulation tower of length
t, whose terms S have height at most (rthgt(E))!!, with each F_i[S^m]
containedin S.

This also covers the embedding statements for height maximality.

HMEE/2. For subsets of Q^k, some finite height maximal r-emulation
extends to some finite height maximal r-emulation, embedded by the
function p if p < 0; p+1 if p in N.

HMEE/3. For subset of Q^k, some finite height maximal r-emulation
starts a height maximal r-emulation tower of length t whose terms are,
for all n in N, embedded by the function p if p < n; p+1 if p in
N|>=n.

Bounds can also be placed on these explicitly Pi02 statements to put
them in equivalent explicitly Pi01 form.

THEOREM 3.3. HMEE/1, HHEE/2 are provably equivalent to Con(SRP) over WKL_0.

The step maximality ideals woks with finite height maximality if it is
restricted properly.

DEFINITION  3.4.  Let E containedin Q[0,1]^k. S is a finite height
step maximal r-emulation of E if and only if for all i = 0,...,hgt(E),
S|<=i is a finite r-emulation of E which is not a proper subset of any
finite r-emulation of E contained in Q^k|<=i of height at most that of
E.

We proceed analogously as above.

***********************************************
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 7231st 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
710: Large Cardinals and Continuations/20  9/14/16  1:27AM
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
710: Large Cardinals and Continuations/20  9/14/16  1:27AM
711: Large Cardinals and Continuations/21  9/18/16 10:42AM
712: PA Incompleteness/1  9/2316  1:20AM
713: Foundations of Geometry/1  9/24/16  2:09PM
714: Foundations of Geometry/2  9/25/16  10:26PM
715: Foundations of Geometry/3  9/27/16  1:08AM
716: Foundations of Geometry/4  9/27/16  10:25PM
717: Foundations of Geometry/5  9/30/16  12:16AM
718: Foundations of Geometry/6  101/16  12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7  10/2/16  1:59PM
721: Large Cardinals and Emulations//23  10/4/16  2:35AM
722: Large Cardinals and Emulations/24  10/616  1:59AM
723: Philosophical Geometry/8  10/816  1:47AM
724: Philosophical Geometry/9  10/10/16  9:36AM
725: Philosophical Geometry/10  10/14/16  10:16PM
726: Philosophical Geometry/11  Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25  10/20/16  1:37PM
728: Philosophical Geometry/12  10/24/16  3:35PM
729: Consistency of Mathematics/1  10/25/16  1:25PM
730: Consistency of Mathematics/2  11/17/16  9:50PM

Harvey Friedman