[FOM] 748: Large Cardinals and Emulations/30
Harvey Friedman
hmflogic at gmail.com
Wed Feb 15 02:19:34 EST 2017
We redo the presentation of Emulation Theory from scratch. This latest
version incorporates a number of expositional improvements, some
additional background material (some underlying combinatorics of
linear orderings), and some seriously improved explicitly Pi01
statements equivalent to Con(SRP).
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.
here
2. DROP EQUIVALENCE IN LINEAR ORDERINGS
3. MAXIMAL EMULATION IN Q[0,1]^k.
3,1, DROP EQUiVALENCE
3.2. TRANSLATION.
3.2. 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
In the Introduction, we start with
INFORMAL EMULATION PRINCIPLE: For any entity of a certain kind, some
maximal emulation exhibits certain symmetry.
Emulation is viewed as an equivalence relation on relevant entities,
which means that the entity and its emulation have "structurally, the
same small parts". A maximal emulation is an emulation that cannot be
enlarged or enriched and still be an emulation. The symmetry asserts
that certain parts are structurally the same.
We then discuss some metaphors. These include seeds growing into a
mature plant, which is a maximal emulation of the seed. A child
growing into an adult emulating a parent, relative, or hero. A thing
growing into the present universe, emulating the thing. All of these
metaphors have merits and demerits, which we expect can be exploited
in order to motivate further developments in Emulation Theory.
In Emulation Theory, we assign clear definite mathematical meanings to
"entity", "emulation", "maximal emulation", and "symmetry".
Our most basic form of Emulation Theory lives in the spaces Q[0,1]^k,
where Q is the set of all rational numbers and Q[0,1] is Q intersect
[0,1]. The entities and their emulations are subsets of the same
Q[0,1]^k.
In this Introduction, we focus on dimension k = 2 and the most basic
kind of symmetry called Drop Equivalence.
We begin our mathematical discussion with Drop Equivalence, as it is a
notion that is well known in certain parts of logic and combinatorics.
However the name is ours. It is normally considered in the context of
the natural numbers and in the ordinals. Here we want to consider it
in the more general context of linear orderings.
DEFINITION 1.1. Let (A,<) be a linear ordering. S containedin A^2 is
drop equivalent at x,y if and only if
i. x,y in A^2.
ii. x_2 = y_2.
iii. For all z < x_2, (x_1,z) in S iff (y_1,z) in S.
There is a nice picture associated with drop equivalence. Draw a
square with sides A. Mark two points x,y of the same height above the
bottom horizontal side. Draw the line segment from x all the way down
and from y all the way down. On the way down from x (y), some of the
points are going to be in S, some out of S. Drop Equivalence requires
that you get the same pattern in/out dropping from x and dropping from
y.
We can think of x,y as raindrops which are falling to the ground from
the same height.
Note that every S containedin A^2 is drop equivalent at some x,y by
simply taking x = y. Another trivial drop equivalence arises where
x_2,y_2 are the left endpoint of A.
DEFINITION 1.2. Let A,S be as in Definition 1.1. S is nontrivially
drop equivalent at x,y if and only if S is drop equivalent at x,y and
i. x not= y.
ii. x_2,y_2 are not the left endpoint of A (which may not exist).
The following is proved in section 2. ii implies i is very easy, and
the other direction requires a little thought.
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 the power set of the nonempty set
of strict predecessors of some element.
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.
None of this remotely challenges ZFC. However, we can look for
nontrivial drop equivalence at some (a,b),(b,b).
The following is proved in section 2.
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 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 some subtle cardinal.
Note that Theorem 2.5i is an abstract set theoretic statement, albeit
a particularly simple one. On the face of it, it is extremely far from
Concrete Mathematical Incompleteness.
But how do we bring Theorem 2.5i down to earth, say to Q[0,1]^2? After
all, Theorem 2.2 tells us that even the much weaker Theorem 2.2i fails
for Q[0,1]^2.
Bringing such abstract set theoretic statements as Theorem 2.2i down
to Q[0,1] (and sometimes Q) is precisely what is accomplished by
Emulation Theory.
The starting definitions of Emulation Theory are given slowly in this
Introduction for two dimensions only, with some rudimentary pictures
and examples. These are
i. N,Z,Q,Q[0,1],Q[0,1]^2.
ii. x,y in Q[0,1]^2 are order equivalent.
iii. S is a 1-emulation of E containedin Q[0,1]^2.
iv. S is an emulation of E containedin Q[0,1]^2.
v. S is an r-emulation of E containedin Q[0,1]^2.
vi. S is a maximal r-emulation of E containedin Q[0,1]^2.
vii. S is drop equivalent at x,y in Q[0,1]^2.
Obviously, we can consolidate iii,iv,v into just v, as emulation is
the same as 2-emulation. We prefer to move very slowly in this
Introduction, and in talks.
As close followers (anybody?) of Emulation Theory know, I recently
made an expositional change in the definition of r-emulation, which
now relies only on ii.
EMULATION DEFINITION. S is an r-emulation of E ccontainedin Q[0,1]^2
if and only if S containedin Q[0,1]^2 and E^r,S^r contain the same 2r
tuples up to order equivalence. Note how immediately friendly
1-emulation is.
Five results only are presented and discussed in this Introduction.
MED/a. For subsets of Q[0,1]^2, some maximal 1-emulation is drop
equivalent at (1,1/2),(1/2,1/2).
MED/b. For subsets of Q[0,1]^2, some maximal emulation is drop
equivalent at (1,1/2),(1/2,1/2).
MED/c. For subsets of Q[0,1]^2, some maximal r-emulation is drop
equivalent at (1,1/2),(1/2,1/2).
MED/d. Let x,y in Q[0,1]^2 and r >= 1. The following are equivalent.
i. For subsets of Q[0,1]^2, some maximal r-emulation is drop equivalent at x,y.
ii. x_2 = y_2 and (if x_1 < x_2 or y_1 < y_2, then x_1 = y_1).
MED/e. Let x_1,...,x_n,y_1,...,y_n in Q[0,1]^2 and r >= 1. The
following are equivalent.
i. For subsets of Q[0,1]^2, some maximal r-emulation is drop
equivalent at each x_i,y_i.
ii. For all i, MED/dii holds for x_i,y_i.
Obviously, we can replace "subsets" throughout with "finite subsets"
resulting in statements provably equivalent over RCA_0.
MED/a-e are implicitly Pi01 via Goedel's Completeness Theorem. I
define implicitly Pi01 and state the key property: that if an
implicitly Pi01 statement is false then it can (theoretically) be
refuted.
All of these results are provable in ZFC. MED/a is easily proved in
RCA_0. MED/b-e are proved just beyond ZFC\P = ZFC without the power
set axiom. E.g., in ZFC\P + POW(N) exists. In fact, WKL_0 + Con(Z_2)
suffices. We do not know whether ZFC\P or even RCA_0 suffices to prove
MED/b-e, but expect that at least for MED/e, we have equivalence with
Con(Z_2) over WKL_0.
We say that In section 2.1, we extend MED/a-e to MED/1-5, which takes
us from dimension 2 to dimension k. MED/1 us again easily proved in
RCA_0, Dimension 3 is a major turning point. We dwell some on the
special importance of dimension 3 for the metaphors, and that drop
equivalence is like looking at raindrops falling to the ground. The
proofs that we have for MED/2-5 for dimension 3 use far more than ZFC.
We think that ZFC should be enough to prove MED/2 for dimension 3, but
think it likely that ZFC does not suffice for MED/3 for dimension 3,
and very likely that ZFC does not suffice for MED/5 for dimension 3.
Formal Systems Used appears as an Appendix and includes of course
RCA_0, SRP+, SRP, ZFC, ZFC\P, and many other systems.
We conclude the Introduction with a brief high level overview of what
it in sections 2-8.
************************************************************************
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 748th 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
Harvey Friedman
More information about the FOM
mailing list