[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