[FOM] 746: Philosophy of Incompleteness/8
Harvey Friedman
hmflogic at gmail.com
Thu Jan 12 15:54:03 EST 2017
We continue from http://www.cs.nyu.edu/pipermail/fom/2017-January/020244.html
BUT this is also SELF CONTAINED.
Note the retitling of this section.
1. DELIBERATIVE CLEAR PATH TO EMULATION THEORY
continued
My computer system was malfunctioning and it seems to have omitted the
official formal definition of Drop Equivalence (still clear from
context) in http://www.cs.nyu.edu/pipermail/fom/2017-January/020244.html.
So we will go over the main points under this section 1 in a self
contained way, but will not repeat all of the informal discussion fin
http://www.cs.nyu.edu/pipermail/fom/2017-January/020244.html
DEFINITION 1.1. Let (D,<) be a linear ordering. We say that S
containedin D^2 is drop equivalent at (x,z),(y,z) if and only if
i. x not= y.
ii. z is not < least.
iii. For all w < z, (x,w) in S iff (y,w) in S.
Note that we impose i,ii in order to avoid trivialities. x = y and z
being < least would each separately make iii trivial.
THEOREM 1.1. Every S containedin N^2 is drop equivalent at some
(x,z),(y,z). For every S containedin N^2 and z > 0, S is drop
equivalent at some (x,z),(y,z).
Proof: Very familiar application of the pigeonhole principle. QED
For which (D,<) do we have those two properties in Theorem 1.1?
THEOREM 1.2. Let (D,<) be a linear ordering. The following two are equivalent.
i. Every S containedin D^2 is drop equivalent at some (x,z),(y,z).
ii. D has cardinality greater than the power set of some nonempty {x: x < y}.
The cardinalities of such D's are exactly the cardinals >=3.
THEROEM 1.3. Let (D,<) be a linear ordering. The following two are equivalent.
i. For every S containedin D^2 and z not least, S is drop equivalent
at some (x,z),(y,z).
ii. D has cardinality greater than the power set of every nonempty {x: x < y}.
The cardinalities of such D's are exactly 0,1, and the strong limit cardinals.
COROLLARY 1.4. Let J,J' be intervals in Q,R, respectively. The
following are false.
i. Every S containedin J^2 is drop equivalent at some (x,z),(y,z).
ii. Every S containedin J'^2 is drop equivalent at some (x,z),(y,z).
We now focus on the much more powerfully elusive drop equivalence at
(x,y),(y,y). This is much harder to achieve.
THEOREM 1.5. The following are equivalent.
i. There exists (D,<) such that every S containedin D^2 is drop
equivalent at some (x,y),(y,y).
ii. There exists a subtle cardinal.
The cardinalities of such D's are exactly the cardinals >= some subtle
cardinal.
A subtle cardinal is a certain kind of well known large cardinal in
the category of what are called "small large cardinals". These are far
larger than the first strongly inaccessible cardinal, or even the
first strongly Mahlo cardinal (even of any finite order), or even the
first weakly compact cardinal. On the other hand, set theorists are
uniformly confident that ZFC + "there exists a subtle cardinal" is
consistent. From this confidence we have that i,ii are independent of
ZFC. In fact, from this confidence, we have that i,ii are independent
of ZFC + V = L and even ZFC + V = L + "there exists a strongly
inaccessible cardinal", as discussed in the L Conjectures of
http://www.cs.nyu.edu/pipermail/fom/2017-January/020238.html and
earlier postings in this series.
In a later posting, we will prove Theorem 1.5 easily from results in
H. Friedman, Subtle Cardinals and Linear Orderings, Annals of Pure and
Applied Logic, Volume 107, Issues 1–3, 15 January 2001, Pages 1–34.
https://u.osu.edu/friedman.8/files/2014/01/subtlecardinals-1tod0i8.pdf
Of course such (D,<) are unimaginably enormous, way outside the scope
of ZFC in size, in the remote (but not the most remote) reaches of
abstract set theory, and are not like a concrete linear ordering such
as our favorite Q[0,1], the interval [0,1] in the rationals Q.
The whole point of Emulation Theory is to bring statements such as i
way way down to earth to linear orderings like D = Q[0,1].
Now obviously we can't even come close to using D = Q[0,1] for this
purpose because of Corollary 1.4. So what do we have in mind?
PROTOTYPE 1. For subsets of Q[0,1]^2, some MAXIMAL EMULATION is drop
equivalent at some (x,y),(y,y).
Maximal Emulations, yet to be defined, will be allowed to move points
around in order preserving ways. We will be using only the order on
Q[0,1], and NOTHING more. This means that we have a very nice
SIMPLIFICATION here. We can say what x,y are IN ADVANCE. We will use
the friendly numbers 1,1/2. It is by no means automatic that we can
use the endpoint 1 for this purpose, but it turns out that we can with
good effect. So we have the following SIMPLIFIED prototype:
PROTOTYPE 2. For subsets of Q[0,1]^2, some MAXIMAL EMULATION is drop
equivalent at (1,1/2),(1/2,1/2).
The above is the Lead Statement in Emulation Theory for dimension 2! A
Maximal Emulation is an emulation which is not a proper subset of any
emulation.
Of course, I haven't yet told you what an emulation is. Emulation is
given by a fundamental equivalence relation between subsets of
Q[0,1]^2 that only involves the ordering on Q[0,1].
DEFINITION 1.2. x,y in Q^k are order equivalent if and only if their
coordinates have the same relative order. I.e., for all 1 <= i,j <= k,
x_i < x_j iff y_i < y_j. S is a 1-emulation of E containedin Q[0,1]^2
if and only if E,S have the same elements up to order equivalence.
THEOREM 1.6. There are exactly 8 equivalence classes of subsets of
Q[0,1]^2 under 1-emulation.
Proof: The number of equivalence class of elements of Q[0,1]^2 under
order equivalence is 3. So the count is 2^3 = 8. QED
MED/1. For subsets of Q[0,1]^2, some maximal 1-emulation is drop
equivalent at (1,1/2),(1/2,1/2).
MED is read "maximal emulation drop" and /1 indicates that it is the
first in the MED series.
But MED/1 is actually very easy to prove. This is because maximal
1-emulations are so simple. Every maximal 1-emulation (regardless of
what it is 1-emulating) is merely an equivalence class under the
equivalence relation of order equivalence on Q[0,1]^2. And it is an
easy exercise that every such equivalence class is automatically drop
equivalent at (1,1/2),(1/2,1/2), and in fact at any (p > q),(q,q), q >
0.
Also every subset of Q[0,1]^2 has a maximum 1-emulation. So we get
this extremely strong form of MED/1:
MED/2. For subsets of Q[0,1]^2, the maximum 1-emulation is drop
equivalent at every (p > q),(q,q), q > 0.
But that is just 1-emulation. The official definition of Emulation,
also written as 2-emulation, is as follows.
DEFINITION 1.3. S is an emulation of E containedin Q[0,1]^2 if and
only if E,S have the same pairs of elements (pairs of pairs!) up to
order equivalence of 4-tuples. More generally, S is an r-emulation of
E containedin Q[0,1]^2 if and only if E,S have the same r-tuples of
elements up to order equivalence of 2r-tuples.
The idea behind emulation is that emulations have the same pairs (of
pairs) up to order equivalence. Another formulation which is easily
seen to be equivalent but is not as simple to write down is that
emulations have the same little parts (<=2 element subsets) up to
isomorphism (preserving order).
An exact count on the number of equivalence classes of subsets of
Q[0,1]^2 under 1-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.
Exact counts for small k of the number of equivalence classes of
elements of Q[0,1]^k under order equivalence - a much simpler and
prior problem - are listed in
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#76 page 7 (lifted from another source).
LEMMA 1.7. The number of equivalence classes of Q[0,1]^4 under order
equivalence is 75. The number of such [abcd] where ab is
lexicographically at most cd is 39. The number of such [abcd] where
min(a,b) > max(c,d) is 9. The number of such [abcd] where ab is not
entirely strictly above cd and cd is not entirely strictly above ab is
57. The number of such [abcd] where ab is not entirely strictly below
cd and ab is lexicographically at most cd, is 30.
Proof: We divide the 4-tuples into these categories.
Permutations of 1234. 24.
Permutations of 1123. 12.
Permutations of 1223. 12.
Permutations of 1233. 12.
Permutations of 1122. 6.
Permutations of 1112. 4.
Permutations of 1222. 4.
Permutations of 1111. 1.
TOTAL: 75.
For the second claim, of the 75, 3 of them have ab = cd, and of the
remaining 72, 36 of them have ab lexicographically before cd. That
gives a total of 39.
The 4-tuples in the third claim are in the following categories.
Permutations of 1234. 4.
Permutations of 1123. 2.
Permutations of 1223. 0.
Permutations of 1233. 2.
Permutations of 1122. 1.
Permutations of 1112. 0.
Permutations of 1222. 0.
Permutations of 1111. 0.
TOTAL: 9.
For the fourth claim, we have 75 - 9 - 9 = 57. For the fifth claim, of
these 57, 3 of them have ab = cd, and of the remaining 54, 27 of them
have ab lexicographically before cd. That gives a total of 30. QED
THEOREM 1.8. The number of equivalence classes of subsets of Q[0,1]^2
under Emulation is at least 2^30 and at most 2^39.
Proof: For each E containedin Q[0,1]^4, let h(E) be the set of all
[abcd] such that (a,b),(c,d) in E and ab <=lex cd. Then E,E' are
Emulations if and only if h(E) = h(E'). Hence the upper bound is
immediate from the second claim of Lemma 1.7. For the lower bound, let
B be any set of equivalence classes [abcd] where ab is not entirely
below cd and ab <=lex cd. For each [abcd] in B choose a copy
(a,b),(c,d) in Q[0,1]^2 so that for all such distinct
[abcd],[a'b'c'd'], the copy (a,b),(c,d) is entirely strictly above or
entirely strictly below the copy (a',b'),(c',d'). By collecting up all
of the elements of Q[0,1]^2 that are chosen, we see that the different
B's will yield subsets of Q[0,1]^2 that are mutually not 2-emulations.
The lower bound is now immediate from the final claim of Lemma 1.7.
QED
MED/2. For subsets of Q[0,1]^2, some maximal emulation is drop
equivalent at (1,1/2),(1/2,1/2).
MED/3. For subsets of Q[0,1]^2, some maximal r-emuation is drop
equivalent at (1,1/2),(1/2,1/2).
What is the status of MED/2 and MED/3? Are these provable in ZFC? To
be continued with the next posting.
************************************************************************
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 746th 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/2316 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
Harvey Friedman
More information about the FOM
mailing list