[FOM] 722: Large Cardinals and Emulations//24
Harvey Friedman
hmflogic at gmail.com
Thu Oct 6 01:59:38 EDT 2016
THIS POSTING IS SELF CONTINUED
continued from http://www.cs.nyu.edu/pipermail/fom/2016-October/020105.html
We continue with this outline:
EMULATION THEORY
OUTLINE
1. INTRODUCTION.
2. INFINITE EMULATION.
2.1. MAXIMAL EMULATION IN Q[0,1]^k.
2.1.1. TRANSLATION.
2.1.2. EMBEDDING.
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.
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.
1. IINTRODUCTION
core
See http://www.cs.nyu.edu/pipermail/fom/2016-October/020102.html
2. INFINITE EMULATION
core
see http://www.cs.nyu.edu/pipermail/fom/2016-October/020105.html
2.1. MAXIMAL EMULATION IN Q[0,1]^k.
2.1.1. TRANSLATION
core
For the initial part through drop symmetry, see
http://www.cs.nyu.edu/pipermail/fom/2016-October/020105.html. We now
continue.
We now consider more general kinds of symmetry of S containedin
Q[0,1]^k. We will be using r-emulations.
DEFINITION 2.1.1.6. Let S containedin Q[0,1]^k and f:Q[0,1]^k into
Q[0,1]^k be partial. S is f-invariant if and only if for all x in
dom(f), x in S iff fx in S. We say that f is ME usable if and only if
the following holds. For all r and subsets of Q[0,1]^k, some maximal
r-emulation is f-invariant.
Here ME abbreviates "maximal emulation". Note that drop symmetry falls
nicely under f-invariance. For x,y iQ[0,1]^k let alpha(x,y):Q[0,1]^k
into Q[0,1]^k be the partial function that maps each
(x_1,...,x_k-1,p), 0 <= p < min(x_k,y_k), to (y_1,...,y_k-1,p). Note
that alpha(x,y) is order theoretic.
It is far too ambitious to give an appropriate necessary and
sufficient condition for partial f:Q[0,1]^k into Q[0,1^k to be ME
usable. A much more reasonable aim is to give an appropriate necessary
and sufficient condition for an order theoretic partial f:Q[0,1]^k
into Q[9,1]^k to be ME usable. However, even this is considerably
beyond what we can do at present.
There is a straightforward necessary condition for ME usable.
DEFINITION 2.1.1.7. Partial f:Q^k into Q^k is order respecting if and
only if for all x in dom(f), x,fx are order equivalent. f is order
respecting/0 if and only if for all x in dom(f), x,fx are order
equivalent over {0}. fld(f) is the field of f as a subset of Q^2k.
THEOREM 2.1.1.7. (RCA_0) If partial f:Q[0,1]^k into Q[0,1]^k is ME
usable then f is order respecting.
We have a nearly complete necessary and sufficient conditioner ME
usability in the finite case.
THEOREM 2.1.1.8. Let f:Q[0,1]^k into Q[0,1]^k be a finite partial
function. If f is order respecting/0 then f is ME usable. Suppose
fld(f) does not contain {0,1]. The following are equivalent.
i. f is order respecting.
ii. f is ME usable.
The hypothesis on f cannot be removed, even for any fixed dimension k >= 2.
We now consider an important class of partial f:Q[0,1]^k into Q[0,1]^k.
DEFINITION 2.1.1.8. Partial f:Q[0,1]^k into Q[0,1]^k is a translation
if and only if there exists c in Q[0,1] such that for all x in dom(f),
f(x) = x + c.
THEOREM 2.1.1.9. For nonempty translations f:Q[0,1]^k into Q[0,1]^k,
the c is unique.
In light of Theorem 2.1.1.9, we adopt the following convenient terminology.
DEFINITION 2.1.1.9. S containedin Q^k translates from A onto B if and
only if there is a translation f:from A onto B such that S is
f-invariant. A,B is ME translation usable if and only if there is a
translation from A onto B that is ME usable. I.e., for finite subsets
of Q[0,1]^k and r, some maximal r-emuation translates from A onto B.
Difficulties arise in determining the ME translation usable sets A,B.
We focus on two special kinds of sets A,B. First the boxes. Then the
line segments.
DEFINITION 2.1.1.10. A rational box in Q[0,1]^k is a product of k
intervals in Q]0,1], where degenerate intervals are allowed (but not
empty intervals). Two rational boxes are similar if and only if they
have the same non degenerate intervals in the same positions.
MEB/1. Two similar rational boxes in Q[0,1]^k are translation usable
if and only if their unique bijective translation is order respecting.
Here MEB indicates "maximal emulation boxes".
The general case presents some unresolved difficulties. However, we
can handle a special kind of box.
DEFINITION 2.1.1.11. A simple rational box in Q[0,1]^k is a box in
Q[0,1]^k where all non degenerate intervals have the same set of
points.
MEB/2. Two simple rational boxes in Q[0,1]^k are translation usable if
and only if
i. If the union of their intervals contains Q(0,1) then the two boxes
are equal; and
ii. Their unique bijective translation is order respecting.
DEFINITION 2.1.1.11. The rational line segments in Q^k are written
[(x,y)], x,y distinct elements of Q[0,1]^k, with the following
convention. For the least i such that x_i not= y_i, we have x_i < y_i.
[x,y] = {x + p(y-x): p in Q[0,1]}, and [x,y),(x,y],(x,y) are
[x,y]\{y}, [x,y]\{x}, [x,y]\{x,y}, respectively. The non degenerate
intervals of [(x,y)] are the Q(x_i,y_i) U Q(y_i,x_i), x_i not= y_i,
where we adjoin x_i iff the rational line segment is [x,y)], and we
adjoint y_i iff the rational line segment is [(x,y]. Two rational line
segments in Q^k are similar if and only if they have the same non
degenerate intervals in the same coordinate positions.
MEL/1. Two similar rational line segments in Q[0,1]^k are translation
usable if and only if their unique bijective translation is order
respecting.
Here MEL indicates "maximal emulation lines".
MEL/2. Two simple rational line segments in Q[0,1]^k are translation
usable if and only if
i. If the union their intervals contains Q(0,1) then the two line
segments are equal; and
ii. Their unique bijective translation is order respecting.
Note that MED/1 and MED/2 for V of cardinality 2 and MED/3 for W of
cardinality 2 fall nicely under any of MEB/1, MEB/2, MEL/1, MEL/2.
This is because the translations between the drops involved are simple
and the bijective translations are order respecting. Additional
unresolved issues arise when working with multiple boxes and line
segments.
THEOREM 2.1.1.10. MEB/1, MEB/2, MEL/1, MEL/2 are implicitly Pi01 via the
Goedel Completeness Theorem.
THEOREM 2.1.1.11. MEB/1, MEB/2, MEL/1, MEL/2 are provable in SRP+ but
not in SRP (assuming SRP is consistent). They are provable in SRP for
each fixed dimension k. They are provably equivalent to Con(SRP)
over WKL_0. There is a fixed k such that they are not provable in ZFC
(assuming ZFC is consistent). The only if directions in the four
statements are provable in RCA_0.
***********************************************
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 722nd 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
Harvey Friedman
More information about the FOM
mailing list