[FOM] 719: Large Cardinals and Emulations//22
Harvey Friedman
hmflogic at gmail.com
Sun Oct 2 13:59:57 EDT 2016
THIS POSTING IS SELF CONTAINED
EMULATIONS??? NO, NOT A TYPO!!! I have hereby changed Continuation
Theory to Emulation Theory.
INFORMAL BACKGROUND. Mathematically, the statements with emulations
are now seriously simpler than the statements with continuations. This
has become steadily clearer to me over the last few months, that I can
no longer resist taking the plunge. Also the arguments for not taking
the plunge have weakened.
Recall that a continuation of E is a superset S of E where every
little pattern in S is already present in E.
I previously defined an emulation of E as an S where every little
pattern in S is already present in E. (All of this is taking place in
the subsets of a fixed ambient space).
As you can see in the formal presentation below, I now define an
emulation of E as an S with the same little patterns. Note that "S is
an emulation of E" is an equivalence relation.
This is a slightly new definition of emulation. The old emulation is
now called a WEAK EMULATION. In a weak emulation we only have that
every little pattern in S is already present in E. In all of the
results for emulations, we can replace 'emulation" by "weak emulation"
and get a weaker result since every emulation is automatically a weak
emulation. All of the unprovability results claimed are also claimed
if we use "weak emulation" in place of "emulation".
EMULATIONS still have compelling metaphorical content. E.g., seeds
grow into plants, where the seeds and the plants have the same title
patterns (think DNA). So we no longer think of the plant as literally
*containing* the seed. Also zygote to adult - again think DNA. And in
some cosmological theories, the present universe has the same little
patterns now as there were during the big bang.
There is also the idea that you may be emulating only certain aspects
of the given object. E.g., informally, a blue emulation is an object
that has the same little blue patterns. Obviously there is a greater
flexibility in constructing such limited emulations. We use what
amounts to limited emulations when we achieve HUGE in section 4.2 with
Emulation/<=. However, this is a rather specialized use of limited
emulation, suggesting a wider compelling "limited emulation theory"
that goes to HUGE and beyond.
We now give the new simplified outline of the theory. The previous
outline was discussed in
http://www.cs.nyu.edu/pipermail/fom/2016-September/020074.html
In this posting, we will focus on the core part of the Introduction.
In the subsequent postings, we will discuss the core parts of sections
2-6.
There are some new expositional strategies starting with the
Introduction. Most notably, the use of DROP SYMMETRY. Drop Symmetry is
a special form of both Line Symmetry and Box Symmetry, and both Line
and Box Symmetry are special forms of Translation Symmetry. The formal
presentation of the other three is not given in the Introduction, but
appears in section 2.1.1.
Drop Symmetry is particularly vivid in three dimensions, and also has
the following virtue. In Emulation Theory, there is a simple necessary
and sufficient condition on a finite set of pairs of points in order
that for sets in Q[0,1]^k, some maximal emulation has drop symmetry
between all of the pairs.
EMULATION THEORY
OUTLINE
1. INTRODUCTION.
2. INFINITE EMULATION.
2.1. MAXIMAL EMULATION IN Q[0,1]^k.
2.1.1. TRANSLATION.
2.1.2. EMBEDDING.
2.2. STEP MAXIMAL EMULATION IN Q^k.
2.2.1. TRANSLATION.
2.2.2. EMBEDDING.
3. EMULATION TOWERS OF FINITE SETS.
3.1. HEIGHT MAXIMALITY IN Q[0,1]^k.
3.1.1. TRANSLATION.
3.1.2. EMBEDDING.
3.2. HEIGHT STEP MAXIMALITY IN Q^k.
3.2.1. TRANSLATION.
3.2.2. EMBEDDING
4. GREEDY EMULATION OF LINEARLY ORDERED DIGRAPHS.
4.1. EMULATION.
4.2. EMULATION/<=.
5. GREEDY EMULATION TOWERS OF SETS OF NONNEGATIVE INTEGERS.
5.1. INFINITE SETS.
5.2. FINITE SETS.
6. GREEDY EMULATION TOWERS OF LINEARLY ORDERED DIGRAPHS.
6.1. OMEGA-GRAPHS.
6.2. FLODIGS - COUNTS.
6.3. EMBEDDING.
NOTE: HUGE and beyond is achieved in 4.2, where we give extremely strong
implicitly Pi01. HUGE and beyond is achieved in 6.3 with explicitly
Pi01, but the present form of 6.3 does not meet
current standards. There is hope for simplification.
1. IINTRODUCTION
core
DEFINITION 1.1. Q,N,Z+ are the set of all rationals, nonnegative
integers, and positive integers, respectively. We use a,b,c,d,e,p,q
with or without subscripts for rationals unless otherwise indicated.
We use n,m,r,s,t with or without subscripts for positive integers,
unless otherwise indicated Q[0,1] is the set of all rationals from 0
to 1 inclusive.
We now focus on the space Q[0,1]^3.
DEFINITION 1.2. Let A,B be finite subsets of Q[0,1]^3. The field of A,
fld(A), is the set of all coordinates of elements of A. A,B are
isomorphic if and only if the unique strictly increasing bijection
h:fld(A) into fld(B) maps A onto B. I.e., for all a,b,c in fld(A),
(a,b,c) in A iff (ha,hb,hc) in B.
DEFINITION 1.3. S is an emulation of E containedin Q[0,1]^3 if and
only if S containedin Q[0,1]^3 and E,S have the same at most 2 element
subsets up to isomorphism. I.e., every at most 2 element subset of E
is isomorphic to a subset of S and every at most 2 element subset of S
is isomorphic to a subset of E. S is a maximal emulation of E
containedin Q[0,1]^3 if and only if S is an emulation of E contaiendin
Q[0,1]^3 and S is not a proper subset of any emulation of E
containedin Q[0,1]^3.
Note that the use of tQ[0,1]^3 in "E containedin Q[0,1]^3" signals
that the ambient space is Q[0,1]^3 and thus the emulations must be
subsets of Q[0,1]^3.
THEOREM 1.1. "S is an emulation of E containedin Q[0,1]^3" is an
equivalence relation on the subsets of Q[0,1]^3. Every E containedin
Q[0,1]^3 has a finite emulation. In fact, every E containedin Q[0,1]^3
has an emulation which is an at most 2(6^6) element subset of E.
The bound 2(6^6) is very crude.
We investigate results of the following general shape.
GENERAL SHAPE. For (finite) subsets of Q[0,1]^3, some maximal
emulation has certain symmetry.
By the finiteness claim in Theorem 1.1, the above statement is
equivalent with and without "finite".
There is a particular kind of symmetry, particularly vivid in 3
dimensions, called Drop Symmetry.
DEFINITION 1.4. S containedin Q[0,1]^3 has drop symmetry between x,y
in Q[0,1]^3 if and only if for all 0 <= p < min(x_3,y_3), (x_1,x_2,p)
in S iff (y_1,y_2,p) in S.
The idea here is as follows. We can drop from x within Q[0,1]^3 going
through the (x_1,x_2,p), 0 <= p < x_3. As we drop, some of these
points are going to lie in S and some are not.
We can also drop from y within Q[0,1]^3 going through the (y_1,y_2,p),
0 <= p < y_3. We can compare membership in S as we descend level by
level.
Drop symmetry between x,y asserts that membership in S is the same
level by level. Of course, x,y may not themselves be at the same level
(third coordinate). So the comparison between the drops from x and y
begins right after min(x_3,y_3).
PROPOSITION 1.1. For (finite) subsets of Q[0,1]^3, some maximal
emulation has drop symmetry between (1,1/2,1/3) and (1/2,1/3,1/3).
Our proof of Proposition 1.1 goes well beyond ZFC but within SRP (see
Appendix). We think it likely that Proposition 1.1 can be proved in
ZFC. However, there are a number of sharper forms of Proposition 1.1
for which the likelihood of provability in ZFC greatly decreases. The
sharper forms in k dimensions are discussed starting in section 2.1.1,
where we claim that ZFC is insufficient. The situation in 3 dimensions
is not so clear at this point.
Note that in the definition of emulation we used only at most 2
element subsets. This obviously generalizes.
DEFINITION 1.5. S is an r-emulation of E containedin Q[0,1]^3 if and
only if S containedin Q[0,1]^3 and E,S have the same at most r element
subsets up to isomorphism. S is a maximal r-emulation of E containedin
Q[0,1]^3 if and only if S is an r-emulation of E contaiendin Q[0,1]^3
and S is not a proper subset of any r-emulation of E containedin
Q[0,1]^3.
Note that emulations and maximal emulation are the same as
2-emulations and maximal 2-emulations.
PROPOSITION 1.2. For (finite) subsets of Q[0,1]^3, some maximal
r-emulation has drop symmetry between (1,1/2,1/3) and (1/2,1/3,1/3).
At this point, we judge about an even chance that this sharpening is
provable in ZFC.
We now greatly strengthen Proposition 1.2.
PROPOSITION 1.3. Let V be a finite set of x in Q[0,1]^3 such that x_1
> x_2 >= x_3. For (finite) subsets of Q[0,1]^3, some maximal
r-emulation has drop symmetry between any two elements of V.
We have a proof of Proposition 1.3 in SRP, and we believe that ZFC is
not sufficient.
We have been able to give a simple necessary and sufficient
combinatorial condition on a finite set W of pairs from Q[0,1]^3 so
that
*) for (finite) subsets of Q[0,1]^3, some maximal r-emulation has drop
symmetry between each pair from W
using SRP. We discuss this in section 2.1.1 where we give the
necessary and sufficient condition for all dimensions k. The necessary
part presents no logical issues as it is proved in RCA_0.
There is a weaker form of emulation that is also natural.
DEFINITION 1.6. S is a weak r-emulation of E containedin Q[0,1]^3 if
and only if S containedin Q[0,1]^3 and every at most r element subset
of S is isomorphic to a subset of E.. S is a maximal r-emulation of E
containedin Q[0,1]^3 if and only if S is an r-emulation of E
contaiendin Q[0,1]^3 and S is not a proper subset of any r-emulation
of E containedin Q[0,1]^3. S is a (maximal) weak emulation of E if and
only if S is a (maximal) weak 2-emulation of E.
THEOREM 1.4. Every (maximal) r-emulation of E containedin Q[0,1]^k is
a (maximal) weak r-emulation of E containedin Q[0,1]^k. Propositions
1.1 - 1.3 imply their formulations with "weak".
We believe that the logical statuses of Propositions 1.1 - 1.3 remain
unchanged with "weak". We know that this is the case for the higher
dimensional forms in section 2.1.1.
***********************************************
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 719th 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
Harvey Friedman
More information about the FOM
mailing list