[FOM] 727: Large Cardinals and Emulations//25
Harvey Friedman
hmflogic at gmail.com
Thu Oct 20 13:37:02 EDT 2016
We continue with the outline below from
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html There we
wrote
"In the interest of space, we get through only the initial part of
2.1.1 which treats drop symmetry in Q[0,1]^k."
That was inadvertently copied from the earlier
http://www.cs.nyu.edu/pipermail/fom/2016-October/020105.html In fact,
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html starts
after drop symmetry and completes section 2.1.1 on Translation.
Before continuing, here is a small expositional point. Recall that I
defined drop symmetry for S containedin Q[0,1]^k as follows.
S has drop symmetry between x,y in Q[0,1]^k if and only if for all 0
<= p < min(x_k,y_k), (x_1,...,x_k-1,p) in S iff (y_1,...,y_k-1,p) in
S.
I prefer to only use s,y with the same last coordinate. So the new
definition reads
S has drop symmetry between x,y in Q[0,1]^k if and only if x_k = y_k
and for all 0 <= p < x_k, (x_1,...,x_k-1,p) in S iff (y_1,...,y_k-1,p)
in S.
This is of course purely expositional.
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. here
2.2. STEP MAXIMAL EMULATION IN Q^k.
2.2.1. TRANSLATION.
2.2.2. EMBEDDING.
3. EMULATION TOWERS OF FINITE SETS.
3.1. HEIGHT MAXIMALITY IN Q[0,1]^k.
3.1.1. TRANSLATION.
3.1.2. EMBEDDING.
3.2. HEIGHT STEP MAXIMALITY IN Q^k.
3.2.1. TRANSLATION.
3.2.2. EMBEDDING
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.
2.1.2. EMBEDDING
DEFINITION 2.1.2.1. f::Q[0,1] into Q[0,1[ if and only if f is a
partial function from Q[0,1] into Q[0,1]. f embeds S containedin
Q[0,1]^k (f is an embedding of S containedin Q[0,1]^k) if and only if
f::Q[0,1] into Q[0,1] is one-one, and for all p_1,...,p_k in dom(f),
(p_1,...,p_k) in S iff (f(p_1),...,f(p_k)) in S.
DEFINITION 2.1.2.2. f is embed usable if and only if f::Q[0,1] into
Q[0,1] is one-one and the following holds for all k,r >= 1. For
subsets of Q[0,1]^k, some maximal r-emulation is f embedded.
THEOREM 2.1.2.1. Let f::Q[0,1] into Q[0,1] be embed usable. Then f is
strictly increasing, and there is no k >= 1 such that f^k(0) = 1 or
f^k(1) = 0.
Proof: Let f be embed usable. For the first claim, we only need
1-emulations in dimension 2. Suppose p < q and f(p) >=
f(q). Note that {(0,1/2)} containedin Q[0,1]^2 has the unique maximal
1-emulation Q[0,1]^2<, which contains (p,q) but not (f(p),f(q)).
Therefore it is not f embedded. Hence f is not embed usable.
For the second claim, we use 2-emulations in dimension 2. By symmetry,
let f^k(0) = 1, k >= 1. Let E = {(0,0),(1/2,1/2),(1/2,1)}. The
2-emulations are the sets E' such that
i. There are at least two (x,x) in E'.
ii. There is exactly one (x,y) in E', x not= y.
iii. For this (x,y), we have x < y and x is max(fld(E)).
Therefore every maximal emulation contains (0,0) and omits (1,1).
Hence no maximal emulation is f embedded. QED
THEOREM 2.1.2.2. A finite f::Q[0,1] into Q[0,1] is embed usable if and
only if it is strictly increasing and there is no k >= 1 such that
f^k(0) = 1 or f^k(1) = 0.
DEFINITION 2.1.2.3. f::Q[0,1] into Q[0,1] is essentially finite if and
only if f moves only finitely many points. I.e., {p in dom(f): f(p)
not= p} is finite.
THEOREM 2.1.2.3. Every order theoretic f::Q[0,1] into Q[0,1] is
essentially finite. Every essentially finite f::Q[0,1] into Q[0,1] has
an order theoretic extension. Every strictly increasing essentially
finite f::Q[0,1] into Q[0,1] has a strictly increasing order theoretic
extension.
MAXIMAL EMULATION EMBEDDING/1. MEE/1. An essentially finite f::Q[0,1]
into Q[0,1] is embed usable if and only if f is strictly increasing
and there is no k >= 1 such that f^k(0) = 1 or f^k(1) = 0.
MAXIMAL EMULATION EMBEDDING/2. MEE/2. An order theoretic f::Q[0,1]
into Q[0,1] is embed usable if and only if f is strictly increasing
and there is no k >= 1 such that f^k(0) = 1 or f^k(1) = 0.
THEOREM 2.1.2.4. MEE/1 and MEE/2 are provably equivalent over RCA_0.
MEE/1 and MEE/2 is proved by necessarily going well beyond ZFC. This
is also the case for very special cases of MEE/2:
MAXIMAL EMULATION EMBEDDING/3. MEE/3. For subsets of Q[0,1]^k, some
maximal emulation (r-emulation) is embedded by the partial function
sending 1,1/2,...,1//k respectively to 1/2,...,1/(k+1) and each 0 <= p
< 1/(k+1) to itself.
THEOREM 2.1.2.5. MEE/1-3 are implicitly Pi01 via Goedel's Completeness Theorem.
THEOREM 2.1.2.6. MEE/1-3 are provably equivalent to Con(SRP) over WKL_0.
We now move a little bit beyond the essentially finite and the order
theoretic functions. Unless indicated otherwise, intervals shall mean
intervals in Q[0,1] with endpoints from Q[0,1]. Degenerate intervals
are integrals with at most one element.
DEFINITION 2.1.2.4. f is a piecewise translation if and only if
f::Q[0,1] into Q[0,1] and f is the disjoint union of finitely many
functions defined on intervals of the form +c, c in Q, on these
respective intervals.
We seek to completely determine which piecewise translations are embed
usable. We are far from achieving this, even for relatively simple
piecewise translations.
We had addressed embed usability of piecewise translations in
http://www.cs.nyu.edu/pipermail/fom/2016-July/019966.html in the
Continuation Theory context. Apparently I didn't appreciate some of
the subtleties involved with embed usability of piecewise
translations, and so I have to weaken much of the part of section 2.2
there on this topic. In particular, Maximal Continuation Embedding
(gap) needs more hypotheses.
THEOREM 2.1.2.7. If f, f^-1 are strictly increasing continuous
piecewise linear translations with at least one fixed point, then they
are embed usable.
MEE/4. If, f, f^-1 are strictly increasing piecewise linear
translations with at least one fixed point, which are continuous
except possibly at endpoints of intervals on which they are the
identity, then they are embed usable.
We now give some criteria for not being embed usable, which apply to any f. .
DEFINITION 2.1.2.5. Let f::Q[0,1] into Q[0,1]. p is altered by f if
and only if f(p) not= p or some f(q) = p not= q.
THEOREM 2.1.2.8. Let f::Q[0,1] into Q[0,1]. If f(p) = p < 1, and every
q > p is altered, then f is not embed usable. If f(p) = p > 0, and
every q < p is altered, then f is not embed usable.
Proof: By symmetry, it suffices to let f be as in the first claim. Let
f(p) = p < 1 and every q > p is altered. We use emulations in two
dimensions. Let E containedin Q[0,1]^2 be a partial function from
Q[0,1] into Q[0,1], with for all x in dom(E), E(x) > x, where every
(a,b,c,d) with a < b and c < d and a not= b is order equivalent to
some element of E^2. Let S be a maximal emulation of E. Then S:Q[0,1)
into Q[0,1] and each S(x) > x. In particular, S(p) > p, and so S(p) is
altered by f.
First assume f(S(p)) not= S(p). Then f sends (p,S(p)) to (p,f(S(p)))
which violates that S is a function. Now assume S(p) = f(r), r not=
S(p). Then f sends (p,r) to (p,S(p)), again contradicting that S is a
function. QED
THEOREM 2.1.2.9. Let f::Q[0,1] into Q[0,1]. If there exist two
distinct fixed points where every point in between is altered, then f
is not embed usable.
Proof: Let f(p) = p < f(q) = q and f alters all p < r < q. We use
emulations in two dimensions. Let E containedin Q[0,1]^3 be a partial
function from Q[0,1]^2< into Q[0,1], with for all (x,y) in dom(E), x <
E(x,y) < y, where every (a,b,c,d,e,f) with a < c < b and d < f < e and
(a,b) not= (d,e) is order equivalent to some element of E^2. Let S be
a maximal emulation of E. Then S:Q[0,1]^2< into Q[0,1] and each x <
S(x,y) < y. In particular, p < S(p,q) < q, and so S(p,q) is altered by
f.
First assume f(S(p,q)) not= S(p,q). Then f sends (p,q,S(p,q)) to
(p,q,f(S(p,q))) which violates that S is a function. Now assume S(p,q)
= f(r), r not= S(p,q). Then f sends (p,q,r) to (p,q,S(p,q)), again
contradicting that S is a function. QED
MEE/5. Some bijection f:[0,1] into [0,1] with fixed point set {p: p^2
< 2} is embed usable.
THEOREM 2.1.2.10. MEE/4 is provably equivalent to Con(SRP) over WKL_0.
We have not yet worked out the status of MEE/4, and expect it to be of
significantly greater strength than ZFC, but not as strong as SRP.
***********************************************
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 727th 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
Harvey Friedman
More information about the FOM
mailing list