[FOM] 721: Large Cardinals and Emulations//23
Harvey Friedman
hmflogic at gmail.com
Tue Oct 4 02:35:07 EDT 2016
THIS POSTING IS SELF CONTAINED
continuing from http://www.cs.nyu.edu/pipermail/fom/2016-October/020102.html
>From http://www.cs.nyu.edu/pipermail/fom/2016-October/020102.html we
have the outline
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.
In the interest of space, we get through only the initial part of
2.1.1 which treats drop symmetry in Q[0,1]^k.
1. IINTRODUCTION
core
See http://www.cs.nyu.edu/pipermail/fom/2016-October/020102.html
2. INFINITE EMULATION
core
Throughout section 2, we focus on statements with these shapes.
SHAPE 1. For (finite) subsets of Q[0,1]^k, some maximal emulation
(r-emulation) has certain translation symmetry.
SHAPE 2. For (finite) subsets of Q[0,1]^k, some maximal emulation
(r-emulation) has certain embeddings.
SHAPE 3. For (finite) subsets of Q^k, some step maximal emulation
(r-emulation) has certain translation symmetry.
SHAPE 4. For (finite) subsets of Q^k, some step maximal emulation
(r-emulation) has certain embeddings.
In the Introduction, we discussed statements of Shape 1 only in
dimension 3 and for a rather special kind of translation symmetry
called drop symmetry. In section 2.1.1 we work in any dimension k, and
give a complete characterization of the drop symmetries that can be
demanded of maximal emulations. We also consider translation symmetry
generally, with the main focus on line segment translation symmetry,
box translation symmetry, and order theoretic translation symmetry.
All three of these include drop symmetry as a special case. For line
segment and box translation symmetry, we do not have a complete
characterization, but are able to handle many cases. For order
theoretic line segment and box translation symmetry, we give a
complete characterization.
In section 2.1.2 we discuss Shape 2. Embeddings of subsets of Q[0,1]^k
are taken to be partially defined functions from Q[0,1] into Q[0,1]
that preserve the set (under the diagonal action). If the embedding is
defined on all of Q[0,1], then we call it a total embedding. We
completely characterize those order theoretic functions that can be
demanded to be embeddings for maximal emulations. We don't have a
complete characterization for piecewise linear functions, but are able
to handle many cases.
In section 2.2 we revisit the entire development in section 2.1 using
a stronger notion of maximality called step maximality. The natural
setting for step maximality is Q^k rather than Q[0,1]^k. In fact, we
can use Q^k for section 2., and we would have a weak form of section
2.2, since step maximality implies maximality. However, we do not know
if ZFC is sufficient if we use Q^k for section 2.1. None of the
results in sections 2.1 and 2.2 can be obtained in ZFC, with the
exceptions being background material and necessary (not sufficient)
conditions.
Step maximality is maximality in steps. I.e., each restriction S|<=n,
n in N, is a maximal emulation of E. The results of section 2.1 carry
over to section 2.2, although some additional issues arise when
considering rays and lines and infinite boxes Q^k.
The robust notion of order theoretic subset of Q^k plays an important
role throughout section 2.
DEFINITION 2.1. X containedin Q^k is order theoretic if and only if X
can be defined as {(v_1,...,v_k: phi}, where phi is a finite
propositional combination of inequalities v_i < v_j, v_i < p, p <
v_i, with 1 <= i <= k and p in Q. The p's are called parameters.
Functions are order theoretic if and only if their graphs are order
theoretic.
THEOREM 2.1. Let X containedin Q^k. The following are equivalent.
i. X is order theoretic.
ii. X is definable over (Q,<) in the sense of model theory.
THEOREM 2.2. Let X containedin Q[0,1]^k. The following are equivalent.
i. X is order theoretic.
ii. X is order theoretic using only parameters from [0,1].
iii. X is definable over (Q,<).
iv. X is definable over (Q,<) with parameters from [0,1].
THEOREM 2.3. The order theoretic subsets of Q^k are the finite
disjoint unions of nonempty pairwise disjoint intervals in Q with
endpoints from Q U {-infinity,infinity}.
Also the robust notion of semi linear subset of Q^k plays a significant role.
DEFINITION 2.2. X containedin Q^k is rational piecewise linear if and
only if X can be defined as {(v_1,...,v_k: phi}, where phi is a finite
propositional combination of linear inequalities in variables
v_1,...,v_k with rational coefficients and rational constant
coefficients. Partial f:Q^n into Q^m is rational piecewise linear if
and only if f is a finite disjoint union of partial rational affine
functions g:Q^n into Q^m with rational piecewise linear domain.
THEOREM 2.4. Let X containedin Q^k. The following are equivalent.
i. X is rational piecewise linear.
ii. X is definable over (Q,<,+).
THEOREM 2.5. Let f:Q^n into Q^m be partial. The following are equivalent.
i. f is rational piecewise linear.
ii. The graph of f is rational piece linear.
iii. f is definable over (Q,<,+).
THEOREM 2.5. The rational piecewise linear subsets of Q are the same
as the order theoretic subsets of Q. The rational piecewise linear
partial functions from Q into Q are the partial functions whose domain
is as in Theorem 2.3, and which is rational affine on each interval.
2.1. MAXIMAL EMULATION IN Q[0,1]^k.
2.1.1. TRANSLATION
core
below only has the part through drop symmetry
We begin with the obvious multidimensional extensions of definitions
from the Introduction.
DEFINITION 2.1.1.1. Let A,B be finite subsets of Q[0,1]^k. 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_1,...,a_k in fld(A),
(a_1,...,a_k) in A iff (h(a_1),...,h(a_k)) in B.
DEFINITION 2.1.1.2. S is an emulation (r-emulation) of E containedin
Q[0,1]^k if and
only if S containedin Q[0,1]^k and E,S have the same at most 2 element
(r element)
subsets up to isomorphism. S is a maximal emulation (r-emulation) of E
containedin Q[0,1]^k if and only if S is an emulation (r-emulation) of
E contaiendin
Q[0,1]^k and S is not a proper subset of any emulation (r-emulation) of E
containedin Q[0,1]^k.
Note that the use of Q[0,1]^k in "E containedin Q[0,1]^k" signals
that the ambient space is Q[0,1]^k and thus the emulations must be
subsets of Q[0,1]^k.
For our lead statements, we use the more basic emulation and maximal
emulations, which are the same as 2-emulation and maximal 2-emulation.
THEOREM 2.1.1.1. "S is an emulation of E containedin Q[0,1]^k" is an
equivalence relation on the subsets of Q[0,1]^k. Every E containedin Q[0,1]^k
has an at most 2((2k)^2k) element emulation which is a subset of E.
The 2((2k)^2k) above is very crude.
We investigate statements of the following general shape.
GENERAL SHAPE. For (finite) subsets of Q[0,1]^k, some maximal
emulation has certain symmetry.
By the finiteness claim in Theorem 1.1, the above statement is
equivalent with and without "finite". Henceforth we will always omit "finite".
DEFINITION 2.1.1.3. S containedin Q[0,1]^k has drop symmetry between x,y
in Q[0,1]^k if and only if for all 0 <= p < min(x_k,y_k), (x_1,...,x_k-1,p)
in S iff (y_1,...,y_k-1,p) in S.
The idea here is as follows. We can drop from x within Q[0,1]^k going
through the (x_1,...,x_k-1,p), 0 <= p < x_k. 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]^k going through the (y_1,...,y_k-1,p),
0 <= p < y_k. 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 as we drop. Of course, x,y may not themselves be at the
same level
(k-th coordinate). So the comparison between the drops from x and y
begins right after min(x_k,y_k).
Here is our lead statement.
MED/1. For subsets of Q[0,1]^k, some maximal emulation has drop
symmetry between (1,...,1/k) and (1/2,...,1/k,1/k).
Here MED is read "maximal emulation drop". MED/1 makes sense for k = 1
as the two tuples are (1) and (1).
We now greatly strengthen MED/1.
MED/2. Let V be a finite set of x in Q[0,1]^k such that x_1 > ... >
x_k-1 >= x_k. For subsets of Q[0,1]^k, some maximal emulation has drop
symmetry between any two elements of V.
For yet more generality, we have been able to give a simple necessary
and sufficient
combinatorial condition on a finite set W of pairs from Q[0,1]^k so
that
*) for subsets of Q[0,1]^k, some maximal emulation has drop symmetry
between each pair from W.
DEFINITION 2.1.1.4. Let x,y in Q^k. x,y are order equivalent if and
only if for all 1 <= i,j <= k, x_i < x_j iff y_i < y_j. Let A
containedin Q. x,y are order equivalent over A if and only if for all
p in A, (x,p),(y,p) are order equivalent. Q[(p,q)] is Q intersect the
interval [(p,q)].
MED/3. Let W be a finite set of pairs from Q[0,1]^k. The following are
equivalent.
i. For all (x,y) in W, (x_1,...,x_k-1) and (y_1,...,y_k-1) are order
equivalent over Q[0,min(x_k,y_k)).
ii. For subsets of Q[0,1]^k, some maximal emulation has drop symmetry
between between the terms of every element of W.
THEOREM 2.1.1.3. MED/1, MED/2, MED/3 are implicitly Pi01 via the
Goedel Completeness Theorem.
THEOREM 2.1.1.4. MED/1, MED/2, MED/3 are provable in SRP+ but not in
SRP (assuming SRP is consistent). They are provable in SRP for each
fixed dimension k. They are provably equivalent to Con(SRP) over
WKL_0. There is a fixed k such that MED/1, MED/2, MED/3 is not
provable in ZFC (assuming ZFC is consistent). The ii implies i
direction of MED/3 is provable in RCA_0.
We conjecture that for dimension k = 3, MED/1 is provable in ZFC but
MED/2 and MED/3 are not.
There are some obvious important modifications of emulations and
maximal emulations. We have already defined r-emulations and maximal
r-emulations.
DEFINITION 2.1.1.5. S is a weak r-emulation of E containedin Q[0,1]^k if and
only if S containedin Q[0,1]^k and every at most r element subset of S
is isomorphic to a subset of E. S is a maximal weak r-emulation of E
containedin Q[0,1]^k if and only if S is a weak r-emulation of E
containedin Q[0,1]^k and S is not a proper subset of any weak
r-emulation of E
containedin Q[0,1]^k. Weak emulations and maximal weak emulations are
weak 2-emulations and weak 2-emulations.
THEOERM 2.1.1.5. Every r-emulation and maximal r-emulation is a weak
r-emulation and maximal weak r-emulation.
THEOREM 2.1.1.6. Theorems 2.1.1.3 and 2.1.1.4 hold for MED/1, MED/2,
MED/3 under any of the following modifications.
i. Replace maximal emulation by maximal r-emulation.
ii. Replace maximal emulation by maximal weak emulation.
iii. Replace maximal emulation by maximal weak r-emulation.
***********************************************
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 721st 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
Harvey Friedman
More information about the FOM
mailing list