[FOM] 750: Large Cardinals and Emulations/32
Harvey Friedman
hmflogic at gmail.com
Wed Feb 15 02:20:39 EST 2017
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.
748: Large Cardinals and Emulations/30
2. DROP EQUIVALENCE IN LINEAR ORDERINGS.
749: Large Cardinals and Emulations/31
3. MAXIMAL EMULATION IN Q[0,1]^k
749: Large Cardinals and Emulations/31
3,1, DROP EQUiVALENCE.
here
3.2. USABILITY.
here
3.3. TRANSLATION.
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.
7.1. WEAKLY MAXIMAL EMULATION IN Q^[0,1]^k
7.2. WEAKLY STEP MAXIMAL EMULATION IN Q^k.
7.3. WEAKLY SUBMAXIMAL EMULATION IN Q^k.
7.4. WEAKLY GREEDY EMULATION IN Q^k
7.5. WEAKLY UP GREEDY EMULATION IN Q^k.
NOTE: HUGE cardinals appear in sections 6 and 7.5.
3.1. DROP EQUIVALENCE
Below MED is read "maximal emulation drop".
MED/1. For subsets of Q[0,1]^k, some maximal r-emulation is drop
equivalent at (1,1/2,...,1/k),(1/2,...,1/k,1/k).
MED/2. Let x,y in Q[0,1]^k and r >= 1. The following are equivalent.
i. For subsets of Q[0,1]^k, some maximal r-emulation is drop equivalent at x,y.
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/3. Let x[1],...,x[n],y[1],...,y[n] in Q[0,1]^k and r >= 1. The
following are equivalent.
i. For subsets of Q[0,1]^k, some maximal r-emulation is drop
equivalent at each x[j],y[j].
ii. Each x[j],y[j] obeys MED/2i.
MED/3 implies MED/2 implies MED/1 is immediate.
THEOREM 3.1.1. MED/1-3 is implicitly Pi01 (over WKL_0) via Goedel's
Completeness Theorem. This is also the case if we fix k or r or both.
Proof: For each k,r,n, the statements assert that an effectively
generated finite set of sentences has a countable model. By Goedel,
this is equivalent to consistency, which is Pi01. QED
THEOREM 3.1.2. i implies ii in MED/2,3 are provable in RCA_0.
Proof: This ms. will contain this straightforward proof. QED
THEOREM 3.1.2. For general k,r,n, MED/1-3 are provably equivalent to
Con(SRP) over WKL_0. This is also the case for general k and fixed r
>= 2 and n = 1. For fixed k and general r,n, MED/1-3 are provable in
SRP. For r = 1 and general k,n, MED/1-3 are provable in RCA_0. For r =
2 and general k,n, MED/1-3 are provable in WKL_0 + Con(Z_2).
Proof: This ms. will contain a proof of the statements from WKL_0 +
Con(SRP) and for fixed k, from SRP. However, reversals will appear
later. QED
CONJECTURES. MED/1,2 for k = 2 and general r are provable in ZFC\P.
MED1,2 for k = 3 and r = 2 are provable in ZFC. MED/3 for k = 2 and
general n,r is provably equivalent to Con(Z_2) over WKL_0. MED/3 for k
= 3 and general r,n is provably equivalent to Con(SUB) over WKL_0.
It would be very interesting to see when independence from ZFC starts
here. We think this should be with MED/1 for k = 3 and r small like r
= 8.
3.2. USABILITY
Drop Equivalence is a very special vivid kind of Invariance.
DEFINITION 3.2.1. f::A into B if and only if f is a partial 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.
Note that S containedin Q[0,1]^k is drop equivalent at x,y in Q[0,1]^k
if and only if S if f-invariant, where f is the bijection
f:{(x_1,...,x_k-1,z): 0 < z < x_k} into {(y_1,...,y_k-1,z: 0 < z <
y_k} given by f((x_1,...,x_k-1,z) = (y_1,...,y_k-1,z}.
Note that we have used Drop Equivalence for MED/1. For which f can be
similarly use f-invariance?
DEFINITION 3.2.2. 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. First we give a necessary
condition.
DEFINITION 3.2.3. f::Q[0,1]^k into Q[0,1]^k is order respecting if and
only if for all x in dom(f), x and f(x) 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 seriously engaged with this fundamental
challenge. We recommend that one first fully understand the case where
dom(f) has only one element.
************************************************************************
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 750th 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
749: Large Cardinals and Emulations/31
Harvey Friedman
More information about the FOM
mailing list