[FOM] 758: Large Cardinals and Emulations/38
Harvey Friedman
hmflogic at gmail.com
Mon Apr 10 01:11:29 EDT 2017
We continue with the organized presentation of Emulation Theory.
EMULATION THEORY
Below will organize, as FOM postings, the contents of a ms. to be
placed on my website, and to appear in some form in a planned volume
in honor of Putnam. This ms. will contain proofs other than reversals.
Reversals will appear in a much expanded ms. later as a high priority,
and will form the book CONCRETE MATHEMATICAL INCOMPLETENESS, when
combined with the BOOLEAN RELATION THEORY ms. currently on my website.
1. INTRODUCTION.
http://www.cs.nyu.edu/pipermail/fom/2017-February/020299.html
2. DROP EQUIVALENCE IN LINEAR ORDERINGS.
http://www.cs.nyu.edu/pipermail/fom/2017-February/020300.html
3. MAXIMAL EMULATION IN Q[0,1]^k
http://www.cs.nyu.edu/pipermail/fom/2017-February/020300.html
3,1, DROP EQUiVALENCE.
http://www.cs.nyu.edu/pipermail/fom/2017-February/020301.html
3.2. USABILITY.
http://www.cs.nyu.edu/pipermail/fom/2017-March/020393.html
3.3. EMBED USABILITY.
http://www.cs.nyu.edu/pipermail/fom/2017-March/020394.html
http://www.cs.nyu.edu/pipermail/fom/2017-March/020411.html
http://www.cs.nyu.edu/pipermail/fom/2017-March/020414.html
continued here
3.4. TRANSLATION USABILITY.
4. STEP MAXIMAL EMULATION IN Q^k.
5. SUBMAXIMAL EMULATION IN Q^k.
6. GREEDY EMULATION IN Q^k.
7. UP GREEDY EMULATION IN Q^k.
8. FINITE EMULATION.
8.1. WEAKLY MAXIMAL EMULATION IN Q^[0,1]^k
8.2. WEAKLY STEP MAXIMAL EMULATION IN Q^k.
8.3. WEAKLY SUBMAXIMAL EMULATION IN Q^k.
8.4. WEAKLY GREEDY EMULATION IN Q^k
8.5. WEAKLY UP GREEDY EMULATION IN Q^k.
3.3. EMBED USABILITY
continued from http://www.cs.nyu.edu/pipermail/fom/2017-March/020394.html
http://www.cs.nyu.edu/pipermail/fom/2017-March/020411.html
http://www.cs.nyu.edu/pipermail/fom/2017-March/020414.html
DEFINITION 3.3.8. f::Q[0,1] into Q[0,1] is (closed) rational piecewise
linear if and only if it is the finite union of rational affine
functions on (closed) rational intervals.
MEE/7. A closed rational piecewise linear f::Q[0,1] into Q]0,1] is ME
embed usable fi and only if it is strictly increasing, and
i. There is no 0 < p,q < 1 such that f maps 0 to p and q to 1.
ii. There is no 0 < p,q < 1 such that f maps p to 0 and 1 to q.
MEE/7 is provable in ACA'. The idea is to adapt the previous proof of
this same statement where f is finite. Let f be the closed rational
piecewise linear function and f' be its appropriate finite restriction
from which it is "generated". Recall that we went to an infinite
iterative version of a maximal r-emulation S* of a given E containedin
Q[0,1]^k which is f'*-embedded, where f'* lifts f' to the infinite
iterative setting, and then apply Ramsey's theorem to cut this down to
the appropriate endpoints, S**. Here we assume that we are working
within a nonstandard setting so that the finite f'* can be extended to
an automorphism f'*# of the maximal r-emulation. This automorphism
must look like an extension of f. So when we push (Q[a,b]*,<,f'*#,S*)
back down to Q[0,1], we can arrive at (Q[0,1],<,f,S).
It has been rather difficult to make substantial progress on the ME
embed usability of rational piecewise linear functions.
MAXIMAL EMULATION EMBEDDING/8. MEE/8. The following rational piecewise
linear function is ME embed usable. f(p) = p if 0 <= p < 1/2; p/2 +
1/4 if 1/2 < p <= 1.
Note that this simple rational piecewise linear function becomes
simpler if we move from Q[0,1] to Q[-1,1].
MAXIMAL EMULATION EMBEDDING/9. MEE/9. Using Q[-1,1], the following
rational piecewise linear function is ME embed usable. f(p) = p if -1
<= p < 0; p/2 if 0 < p <= 1.
Obviously MEE/8 and MEE/9 are provably equivalent over RCA_0.
Proof of MEE/9: It is more convenient to use the inverse function g(p)
= p if -1 <= p < 0; 2p if 0 < p <= 1.
In WKL_0 + Con(MAH). Let T = ZFC + V = L + {c_i: i in
Z} is a medium strong set of indiscernibles. Here medium strong means
ordinal indiscernibles with respect to all formulas with parameters
below any indiscernible below the indiscernibles being used, and also
that ordinals define by indiscernibles are smaller than the next
higher indiscernible .T is consistent because Con(MAH), Let M be a
model of T and let M' be the submodel of elements definable with
parameters c_i, i in Z. M' is an elementary submodel of M.
D is the usual On x Q[-1,1], and <D is the usual lexicographic
ordering on D = On x Q[-1,1) all in the sense of M'. <# is the usual
lexicographic ordering on On x Q[-1,1)', where Q[-1,1)' is any
recursive ordering of Q[-1,1) of order type omega, starting with -1,
all in the sense of M'. Then <# is a well ordering on D in the sense
of M'. We also, as usual, use <#^k which first orders by max of the
k-coordinates according to <#, and then lexicographically on the k
coordinates by <#.
We build our usual r-maximal emulation S* containedin D^k of a given E
containedin Q[-1,1] which is greedy with respect to <#^k. Then S* is
definable over M' without parameters. After some preparation, we will
be cutting back to the common initial segment of <D and <# with right
endpoint (kappa_0,-1).
By an L-term we mean a definition over M of an ordinal with parameters
from the c_i, i in Z. Thus M' was defined as the values of the
L-terms. The meaning of an L-term is the same whether we interpret it
over M or over M'. By indiscernibility, every ordinal of M' is less
than some kappa_i, i in Z.
We claim that in the sense of M', alpha < kappa_i+1 if and only if
alpha is defined by an L-term which, if we lower all subscripts on the
parameters by 1, results in a beta < kappa_i. To see this, first
assume alpha = t(c_i1,...,c_in). < kappa_i+1. By indiscernibility,
beta = t(c_i1-1,...,c_in-1) < kappa_i, and so alpha is defined by an
L-tem which, if we lower by 1, we get below kappa_i. Now suppose alpha
= t(c_i1,...,c_in). has t(c_i1-1,...,c_in-1) < kappa_i. Then by
indiscernibility, t(c_i1,...,c_in) < kappa_i+1.
We now define j:On into On. Here j is external and On is internet to
M'. Let alpha = t(kappa_i1,...,kappa_in). Take j(alpha) =
t(kappa_i1+1,...,kappa_in+1). By indiscernibility, j is well defined
and j is strictly increasing. Clearly j maps each interval [0,kappa_i)
strictly increasing onto [0,kappa_i+1) by the previous paragraph.
Let W be the initial segment of On of ordinals below every kappa_n, n
in Z. Then W is left closed right open, and any statement with
parameters from the kappa's and parameters from W remains unchanged
when we add 1 to the subscripts. This is because the indiscernibles
are medium strong.
We now return to S* containedin D^k. Let D*' be the common initial
segment of <D and <# with right endpoint (kappa_0,-1). Then S*
intersect D*'^k is still a maximal r-emulation of E containedin
Q[-1,1]^k.
Let j* be the same as j except that on W, j* is the identity. It is
now clear that S* is both j and j'-embedded. Now form (D*,<D*.S*,j')
and take a countable substructure (D',<D',S',j') so that we have a
countable dense linear ordering with the same endpoints, and S' is
still an r-maximal emulation of E contanedin Q[-1,1]^k. Then isomorph
down to some (Q[-1,1]\{0},<,S^,f). We have to remove 0 since W has no
largest element. Now we can simply arbitrarily extend the r-maximal
emulation S^ containedin (Q[-1,1]\{0})^k of E containedin Q[-1,1]^k to
an r-maximal emulation S containedin Q]-1,1]^k of E containedin
Q[-1,1]^k which remains f-embedded. This is because 0 is not in
fld(f). Actually, we only have r-maximality with respect to
(Q[-1,1]\{0})^k. But then we just extend arbitrarily to Q]-1,1]^k. QED
We expect that MEE/8 and MEE/9 are provably equivalent to Con(MAH) over WKL_0.
Note that this f:Q[-1,1] into Q[-1,1] are not everywhere defined. The
domain is Q[-1,1]\{0}. However, by using any isomorphism from
(Q[0,1],<) onto (Q[-1,1]\{0}, we can convert f to some g:Q[0,1] into
Q[0,1], although it will not be piecewise linear. Nevertheless,
conceptually it is very simple, as its isomorphism type is easily
described. This suggests a theory of ME embed usability, where the f's
are described combinatorially in terms of their isomorphism types.
Actually it seems that this method of establishing MEE/8,9 should
extend to the following very strong statement that involves a very
large class of functions.
MEE/10. A bicontinuous f::Q[0,1] into Q[0,1] is ME embed usable if and
only if it is strictly increasing, and
i. There is no 0 < p,q < 1 such that f maps 0 to p and q to 1.
ii. There is no 0 < p,q < 1 such that f maps p to 0 and 1 to q.
Note that there is no assumption that f is even piecewise linear. We
expect that MEE/10 is provably equivalent to Con(MAH) over WKL_0. If
time and space permits, we expect to prove MEE/10 from Con(MAH) in the
ms.
************************************************************************
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 758th 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/23/16 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
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
740: Philosophy of Incompleteness/2 1/7/16 8:33AM
741: Philosophy of Incompleteness/3 1/7/16 1:18PM
742: Philosophy of Incompleteness/4 1/8/16 3:45AM
743: Philosophy of Incompleteness/5 1/9/16 2:32PM
744: Philosophy of Incompleteness/6 1/10/16 1/10/16 12:15AM
745: Philosophy of Incompleteness/7 1/11/16 12:40AM
746: Philosophy of Incompleteness/8 1/12/17 3:54PM
747: PA Incompleteness/2 2/3/17 12:07PM
748: Large Cardinals and Emulations/30 2/15/17 2:19AM
749: Large Cardinals and Emulations/31 2/15/17 2:19AM
750: Large Cardinals and Emulations/32 2/15/17 2:20AM
751: Large Cardinals and Emulations/33 2/17/17 12:52AM
752: Emulation Theory for Pure Math/1 3/14/17 12:57AM
753: Emulation Theory for Math Logic 3/10/17 2:17AM
754: Large Cardinals and Emulations/34 12 00:34:34 EST 2017
755: Large Cardinals and Emulations/35 3/12/17 12:33AM
756: Large Cardinals and Emulations/36 3/24/17 8:03AM
757: Large Cardinals and Emulations/37 3/27/17 2:39AM
Harvey Friedman
More information about the FOM
mailing list