[FOM] 749: Large Cardinals and Emulations/31
Harvey Friedman
hmflogic at gmail.com
Wed Feb 15 02:19:50 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
here
3. MAXIMAL EMULATION IN Q[0,1]^k
here
3,1, DROP EQUiVALENCE
3.2. TRANSLATION.
http://www.cs.nyu.edu/pipermail/fom/2016-October/020107.html
3.3. 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.
1. INTRODUCTION
See 748: Large Cardinals and Emulations/30
2. DROP EQUIVALENCE IN LINEAR ORDERINGS
We begin by proving the two results from this section cited in the Introduction.
LEMMA 2.1. Let kappa be an infinite cardinal and let A_alpha, alpha <
kappa, be subsets of kappa of cardinality kappa. There exists B_alpha
containedin A_alpha, alpha < kappa, of cardinality kappa, where the
B's are pairwise disjoint.
Proof: Build the B's by a transfinite induction of length kappa, where
at any stage the B's are respective subsets of the A's that are
pairwise disjoint. At any stage we add a single new element to a
single B. QED
THEOREM 2.2. Let (A,<) be a linear ordering. The following are equivalent.
i. Every S containedin A^2 is nontrivially drop equivalent at some x,y.
ii. A has cardinality greater than some POW({y: y < x}) where x is not
the left endpoint.
In particular, any well ordering with at least three elements obeys
i,ii, but Q,Q[0,1],R,[0,1] do not. However, Q+R,Q[0,1]+R do obey i,ii.
Proof: Assume ii. Let S containedin A^2. Let POW({y: y < x}) be as
given. By cardinality, let u not= v be such that {y < x: R(u,y)} = {y
< x: R(v,y)}. Then S is drop equivalent at (u,x),(v,x).
Assume ii is false.
case 1. A has at most 2 elements. Obviously i,ii are false.
case 2. A has at least 3 elements and the two least elements of A
exist. Obviously i,ii are true.
case 3. Otherwise. Let kappa be the least cardinality of the initial
segments of A with at least two elements. Then kappa is an infinite
cardinal. Let <x have cardinality kappa. By Lemma 2.1, let A_y
containedin <y, y < x, y not the left endpoint, be pairwise disjoint
and of cardinality kappa. For each y < x, we can obviously arrange
that S is not nontrivially drop equivalent at any (u,y),(v,y), by just
considering second coordinates from A_y. By the disjointness, we can
obviously arrange that S is not nontrivially drop equivalent at any
(u,y),(v,y), y < x. Hence S is not nontrivially drop equivalent at any
(u,y),(v,y).
QED
For Theorem 2.? we use
[1] H. Friedman, Subtle Cardinals and Linear Orderings,
https://u.osu.edu/friedman.8/files/2014/01/subtlecardinals-1tod0i8.pdf,
http://www.sciencedirect.com/science/article/pii/S0168007200000191
We use the following definition from [1].
DEFINITION 2.1. (A,<) is a 2-critical linear ordering if and only if
i. (A,<) has no endpoints.
ii. For all f:A^2 into A with every f(x,y) < min(x,y), there exists a
< b < c such that f(a,b) = f(b,c).
LEMMA 2.3. Let (A,<) have no endpoints, where every S containedin A^2
is nontrivially drop equivalent at some (a,b),(b,b). Then (A,<) is
2-critical.
Proof: Let (A,<) be as given. Let f:A^2 into A where each f(x,y) <
min(x,y). Define S(x,y) if and only if there exists x < z < y such
that f(z,y) = x. Let S be nontrivially drop equivalent at (a,b),(b,b).
Then a > b.
Let f(b,a) = c < a,b.Then S(c,a). Hence S(c,b). Let f(z,b) = c, z < b.
We have f(z,b) = f(b,a) = c, z < b < a. QED
LEMMA 2.4. Let (A,<) be such that every S containedin A^2 is
nontrivially drop equivalent at some (a,b),(b,b). Then (A,<) wth the
left endpoint removed is 2-critical.
Proof: Note that if we remove the left endpoint from (A,<) then A
retains the hypothesized property. Apply Lemma 2.2. QED
THEOREM 2.5. The following are equivalent.
i. There exists (A,<) such that every S containedin A^2 is
nontrivially drop equivalent at some (a,b),(b,b).
ii. There exists a subtle ordinal (cardinal).
In particular, i is not provable in ZFC (assuming ZFC is consistent).
And i is not refutable in ZFC (assuming ZFC + "there exists a subtle
cardinal" is consistent).
Furthermore, the cardinalities of the (A,<) with i are exactly the
cardinalities greater than or equaled to the least subtle cardinal.
Proof: Assume i. By Lemma 2.4, there is a 2-critical linear ordering.
By [1], there is a subtle cardinal. Now let lambda be a subtle
cardinal. Then obviously (lambda,<) has the property in i.
If i is provable in ZFC then ZFC proves the existence of a subtle
cardinal, and therefore ZFC proves Con(ZFC). By Goedel's second
incompleteness theorem, ZFC is inconsistent.
If i is refutable in ZFC then by the equivalence, ZFC proves that
there is no subtle cardinal.
Let kappa be the cardinality of an (A,<) with i. Then kappa is the
cardinality of a 2-critical linear ordering. By [1], there is a subtle
cardinal <= kappa. Let kappa >= lambda, where lambda is a subtle
cardinal. Then since (lambda,<) has i, so does (kappa,<). QED
We now give a higher dimensional form of Theorem 2.5.
DEFINITION 2.2. Let (A,<) be a linear ordering. S containedin A^k is
nontrivially drop equivalent at (a_1,...,a_n),(b_1,...,b_n) if and
only if a_n = b_n is not the left endpoint of (A,<), (a_1,...,a_n)
not= (b_1,...,b_n), and for all c < a_n, (a_1,...,a_n-1,c) in S iff
(b_1,...,b_n-1,c) in S.
THEOREM 2.6. The following are equivalent.
i. There exists (A,<) such that for all k >= 1, every S containedin
A^k is nontrivially drop equivalent at some (a_1 > ... > a_k),(a_2 >
... > a_k,a_k).
ii. SRP+. I.e., for all k, there exists a k-SRP ordinal (cardinal).
Proof: Use [1] as above. QED
Emulation Theory brings Theorem 2.6i down to the Q[0,1]^k using Emulations.
3. MAXIMAL EMULATION IN Q[0,1]^k
DEFINITION 3.1. Q,Z,N is the set of all rationals, integers,
nonnegative integers, respectively. We use variables n,m,r,s,t over
positive integers. Q[0,1] = Q intersect [0,1]. x,y in Q^k are order
equivalent if and only if for all 1 <= i,j <=k, x_i < x_j iff y_i <
y_j.
THEOREM 3.1. Order equivalence on Q^k is an equivalence relation with
finitely many equivalence classes.
Proof: The equivalence class of x in Q^k is completely determined by
{(i,j): x_i < x_j}., a subset of {1,...,k}^2. QED
Exact counts for small k of the number of equivalence classes of
elements of Q[0,1]^k under order equivalence are listed in
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#76 page 7 (lifted from another source).
DEFINITION 3.2. S is an r-emulation of E containedin Q[0,1]^k if and
only if S containedin Q[0,1]^k and E^r,S^r have the same kr tuples up
to order equivalence. S is a maximal r-emulation of E containedin
Q[0,1]^k if and only if S is an r-emulation of E containedin Q[0,1]^k
which is not a proper subset of any r-emulation of E containedin
Q[0,1]^k.
THEOREM 3.2. r-emulation forms an equivalence relation on the subsets
of Q[0,1]^k with finitely many equivalence classes. Every subset of
Q[0,1]^k has a finite r-emulation.
Proof: The equivalence class of S containedin Q[0,1]^k under
r-emulation depends only on the set of equivalence classes that
contain the various r-tuples of elements of S. Hence the number of
equivalence classes under emulation is at most the base 2 exponential
of the number of equivalence classes under order equivalence of
elements of Q^kr. QED
An exact count on the number of equivalence classes of subsets of
Q[0,1]^2 under 2-emulation is not straightforward. Here we will only
give a rough estimate, although we believe that an exact count is
definitely achievable as a nice piece of elementary finite
combinatorics.
THEOREM 3.3. The number of equivalence classes of subsets of Q[0,1]^2
under 2-emulation is at least 2^30 and at most 2^39.
THEOREM 3.4. Every subset of Q[0,1]^k has an elementary recursive
maximal r-emulation.
Proof: Let E containedin Q[0,1]^k. Use a suitably computable one-one
enumeration of the elements of Q[0,1]^k. Start with any finite E'
containedin E that emulates E. Now extend E' incrementally with each
tuple in the enumeration in the usual greedy way. I.e., use a tuple if
and only if it's insertion will still be an emulation of E. QED
In sections 3.1-3.3, we will be putting requirements on maximal
emulations, and these requirements will generally preclude that the
maximal r-emulations be recursive.
************************************************************************
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 749th 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
Harvey Friedman
More information about the FOM
mailing list