[FOM] 751: Large Cardinals and Emulations/33
Harvey Friedman
hmflogic at gmail.com
Fri Feb 17 00:52:37 EST 2017
Continued from http://www.cs.nyu.edu/pipermail/fom/2017-February/020301.html
The numbering in the TOC below has now been fixed.
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.
here/starting over
3.3. TRANSLATION.
here/to be continued
3.4. EMBEDDING.
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.
NOTE: HUGE cardinals appear in sections 7 and 8.5.
3.2. USABILITY
NOTE: This replaces the section 3.2 in
http://www.cs.nyu.edu/pipermail/fom/2017-February/020301.html with
considerably more material.
Drop Equivalence is a special kind of Invariance, defined as follows. .
DEFINITION 3.2.1. f::A into B if and only if f is a function
whose domain is a subset of A and range is a subset of B. S
containedin Q[0,1]^k is f-invariant if and only if for all x in
dom(f), x in S iff f(x) in S.
DEFINITION 3.2.2. Let x,y in Q[0,1]^k, x_k = y_k. DROP(x) =
{(x_1,...,x_k-1,z): 0 <= z < x_k-1}. DROP(x,y) is the bijection
f:DROP(x) into DROP(y) given by f((x_1,...,x_k-1,z)) =
(y_1,...,y_k-1,z}.
THEOREM 3.2.1. S containedin Q[0,1]^k is drop equivalent at x,y in
Q[0,1]^k if and only if x_k = y_k and S is DROP(x,y)-invariant.
DEFINITION 3.2.3. Let f::Q[0,1]^k into Q[0,1]^k. f is ME usable if and
only if the following holds. For all r >= 1 and subsets of Q[0,1]^k,
some r-emulation is f-invariant.
Determining the ME usable f seems far too difficult. But we have made
considerable progress for special f. To begin with, we can restate
MED/1,2 as follows.
MED/1 restated. DROP((1,1/2,...,1/k),(1/2,...,1/k,1/k)) is ME usable.
MED/2 restated. Let x,y in Q[0,1]^k. The following are equivalent.
i. DROP(x,y) is ME usable.
ii. x_k = y_k and (x_1,...,x_k-1),(y_1,...,y_k-1) are order equivalent
and (for all 1 <= i <= k) (if x_i < x_k or y_i < y_k, then x_i = y_i).
MED/2 is slightly sharper than MED/2 restated as it asserts the
equivalence for each fixed r >= 1. Clearly we have MED/2 implies MED'2
restated implies MED/1 restated implies MED/1, and we have already
seen with Theorem 3.1.2 that MED/1 implies MED/2. So all four
statements and also MED/3 are equivalent - provably equivalent to
Con(SRP) over WKL_0
We now give a basic necessary condition for ME usability.
DEFINITION 3.2.4. f::Q[0,1]^k into Q[0,1]^k is order respecting if and
only if for all x in dom(f), x,f(x) are order equivalent. Let u in
Q]0,1]^m. f is order respecting/u if and only if for all x in dom(f),
(x,u),(f(x),u) are order equivalent.
THEOREM 3.2.1. Let f::Q[0,1]^k into Q[0,1]^k be ME usable. Then f is
order respecting.
Proof: Suppose f::Q[0,1]^k into Q[0,1]^k be ME usable but not order
respecting, and let x,f(x) be not order equivalent. Let E = {y in
Q[0,1}^k: x,y are order equivalent}. E has exactly one maximal
r-emulation, which is E. But x in E and f(x) notin E. QED
Even the determination of the finite usable f::Q[0,1]^k into Q[0,1]^k
is challenging. We have not made a complete determination, but have
much partial information. All of these results are proved in RCA_0.
THEOREM 3.2.2. Let finite f::Q[0,1]^k into Q[0,1]^k be order
respecting/0 or order respecting/1. Then f is ME usable.
Proof: By symmetry, we can assume that f::Q[0,1]^k into Q[0,1]^k is
finite and order respecting/0 Let fld(f) be 0 = b_1 < ... < b_t, where
we can assume that 0 in fld(f). Inductively construct sets S_n
containedin Q[0,n]^k where each S_i = S_i+1 intersect Q[0,i]^k is a
maximal r-emulation of E containedin Q[0,i]^k. By Ramsey's theorem,
let a_1 < ... < a_t be positive integers that form a set of
indiscernibles with respect to S = U_i S_i relative to 0. Form
(Q[0,a_t-1],0,a_1,...,a_t,i) and take an order isomorphic copy
(Q[0,1],0,b_1,...,b_t) where b_1 < ... < b_t enumerates fld(f). QED
THEOREM 3.2.3. Finite f::Q[0,1)^k into Q[0,1)^k is EM usable if and
only if it is order respecting. Finite f::Q(0,1]^k into Q(0,1]^k is EM
usable if and only if it is order respecting.
Proof: For either claim, suppose f is order respecting. then f is
order respecting/0 or order respecting/1, and therefore ME usable. For
either claim, let f be EM usable. Then f is order respecting. QED
THEROEM 3.2.4. The cardinality 1 function f(0) = 1 is not order
respecting/0, not order respecting/1, but EM usable.
Proof: Let E containedin Q[0,1] and r >= 1. If E has <r elements then
the maximal emulations of E are the subsets of Q[0,1] of the same
cardinality as E. If E has >=r elements then the maximal emulation of
E is Q[0,1]. In either case, there is a maximal emulation of E that is
f-invariant. QED
THEOREM 3.2.5. The cardinality 1 function f(0,0) = (1,1) is order
respecting But not EM usable.
Proof: Let E = {(0,0),(1/3,1/3),(1/2,1)} and r = 2. The 2-emulations
consist of two or more (a,a) together with a single (b,c) with every a
< b < c. Then the maximal 2-emulations consist of a single (b,c), 0 <
b < c, together with all (a,a), a < b < c. This cannot be f-invariant
since it contains (0,0) but not (1,1). QED
The above merely scratches the surface of the problem of determining
EM usability for finite f.
CONJECTURE. There is a decision procedure for determining whether a
given finite f::Q[0,1]^k into Q[0,1]^k is EM usable, which provably
works in ACA (or maybe RCA_0). This is the case also if we fix r in EM
usability (i.e., use only r-emulations).
3.3. TRANSLATION
We now consider an important class of f::Q[0,1]^k into Q[0,1]^k called
translations.
DEFINITION 2.1.1.8. 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 3.3.1. For nonempty translations f::Q[0,1]^k into Q[0,1]^k,
the c is unique. For A,B containedin Q[0,1]^k, there is at most one
translation from A onto B.
Proof: Let f::Q[0,1]^k into Q[0,1]^k be a nonempty translation.
Suppose for all x in dom(f), f(x) = x + d. Then f(x) = x + c-d is a
bijection from dom(f) onto dom(f). Since dom(f) is nonempty, c-d = 0,
and so c = d. Now suppose there is a translation from A onto B. If A
is empty then obviously this translation is unique (the empty
translation). If A is nonempty then by the above, this translation is
unique. QED
In light of Theorem 3.3.1, we adopt the following convenient terminology.
DEFINITION 3.3.1. Let A,B containedin Q[0,1]^k. S containedin Q[0,1]^k
translates from A onto B if and
only if there is a translation f::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.
We can restate MED/1,2 as follows.
MED/1 restated. DROP((1,1/2,...,1/k)),DROP((1/2,...,1/k,1/k)) is ME
translation usable.
MED/2 restated. Let x,y in Q[0,1]^k. The following are equivalent.
i. DROP(x),DROP(y) is ME translation usable.
ii. x_k = y_k and (x_1,...,x_k-1),(y_1,...,y_k-1) are order equivalent
and (for all 1 <= i <= k) (if x_i < x_k or y_i < y_k, then x_i = y_i).
Difficulties arise in determining the ME translation usable sets A,B.
We have not even determined this for finite A,B.
TO BE CONTINUED.
************************************************************************
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 751st 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
Harvey Friedman
More information about the FOM
mailing list