[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