[FOM] 698: Large Cardinals and Continuations/13
Harvey Friedman
hmflogic at gmail.com
Wed Jul 20 13:28:26 EDT 2016
THIS POSTING IS SELF CONTAINED
In http://www.cs.nyu.edu/pipermail/fom/2016-June/019945.html we
presented a polished abstract and claimed simple necessary and
sufficient conditions for the SRP statements involving translated
lines, translated boxes, and embeddings. It turns out that upon
examination, there are some "abnormal" cases that I will only be able
to confidently handle (refute) while being immersed in the reversals
of the main cases. S
So there remain some technical problems which are probably doable in
the longer run. But the theory has been developing in very
conceptually clear ways.
Below you will see a more polished and hopefully debugged abstract,
with a few proofs, covering only the first two major sections. I will
continue these postings to cover the whole landscape piece by piece,
with new results and ideas. One major goal which appears to be
succeeding is this:
*to make the explicitly finite SRP forms and the HUGE cardinal forms
and the explicitly finite HUGE cardinal forms very well motivated, so
that there is a completely clear intuitive development, fully
motivated by general intellectual principles, all the way through*
Before this, I want to step back and compile some milestones. That is,
assuming that I will be making good on all of the major claims later
in this calendar year.
LATE STAGE MILESTONES
Characterizing the statements that can only be proved by going well
beyond the usual ZFC axioms for mathematics. Characterizing them
*independently* of the fact that they have this exotic logical
property (being only proved by necessarily using far more than the
usual ZFC axioms for mathematics).
*earlier milestones starting in 1967
*arguably mathematically natural
*mathematically natural
*mathematically interesting
mathematically fundamental
mathematically revolutionary
scientifically interesting
scientifically fundamental
scientifically revolutionary
intellectually interesting
intellectually fundamental
intellectually revolutionary
This calendar year it has gone from "mathematically natural" to
"mathematically interesting". This continues to be confirmed by the
core mathematics community. We believe that it is clearly
"mathematically fundamental", but I haven't yet approached the core
mathematics community with this phrase. Moreover, it seems like the
basic ingredients are coming into place that should propel this deep
into this list, even if I don't live to see it confirmed.
SOME BREAKING NEWS
Here we consider only translations and embeddings that are either
order theoretic, or at least piecewise translations. But if we venture
into the wider arena of the piecewise linear and the piecewise
polynomial, a lot of new phenomena seem to arise.
It appears that I can use the permutation on Q[-1,1]
p if -1 <= p < 0; p^2 if 0 <= p <= 1.
and the total embedding from Q[-1,1] into Q[-1,1]
p if -1 <= p < 0; p/2 if 0 <= p <= 1.
opening up a new chapter in this development. The natural proofs of
both of these use almost all of Z = Zermelo set theory, but it is not
so clear if they are provable in some n-th order arithmetic.
I expect to take up the sections in
http://www.cs.nyu.edu/pipermail/fom/2016-June/019945.html one by one
to refine them, presumably for the last time, before getting buried
into the reversals. I am in close contact with a helpful math icon,
who clearly views this as having gone from "perfectly natural" to
"perfectly interesting". I was doubtful even in 1/16 that I would get
to "perfectly interesting", a critical milestone.
SYMMETRIC MAXIMAL CONTINUATION
draft
by
Harvey M. Friedman
July 11, 2016
ABSTRACT. For finite subsets of Q[-1,0)^1+k, some maximal continuation
in Q[-1,1]^1+k translates from the line Q[-1,0) x {(0/k,...,(k-1)/k}
onto the line Q[-1,0) x {(1/k,...,k/k)}. Here Q is the set of all
rational numbers, a continuation is a superset with the same <=2
element subsets, up to order isomorphism, and the inclusion maximal
continuation has translation symmetry from the first line onto the
second line as indicated. This result is proved by necessarily going
far beyond the usual ZFC axioms for mathematics. Many more general
results are presented. Most of the results are proved to be equivalent
to the consistency of ZFC augmented with certain large cardinal
hypotheses, either the SRP or the HUGE cardinal hierarchies.
1. Informal Symmetric Maximal Continuation.
2. Maximal Continuation in Q[-1,1]^k.
2.1. Order Theoretic Sets.
2,2, Maximal Continuation Embedding.
2.3 Maximal Continuation Invariance.
2.4. Maximal Continuation Translation.
to be revised:
3. Rich Continuation in Q[-1,1]^k.
4. # Continuation in Q^k.
5. ## Continuation in Q^k.
6. Rich Continuation in N.
8. Future Research
9. Logical Notions.
1. INFORMAL SYMMETRIC MAXIMAL CONTINUATION
The assertion at the beginning of the Abstract is our lead statement
that we prove by necessarily going well beyond the usual ZFC axioms
for mathematics. All of the definitions used in this assertion appear
in Definitions 2.1 - 2.3 at the beginning of section 2. The novel
notion that drives this entire development is that of continuation.
The thrust of the paper is to put this lead statement into the much
wider context of Symmetric Maximal Continuation.
Here we present an informal discussion of Symmetric Maximal
Continuation. This informal idea is far more general than the formal
developments presented here, and suggest much future research.
We imagine a large region R with a large subregion E. All structures
are required to live within R. We start with a little structure that
lives in E. This little structure then enlarges or grows within R. We
want the little structure to grow as much as possible, as long as it
still lives within R.
There is a very important condition that we place on the growth of the
little structure. We require that there be no new tiny patterns as it
grows. Another way of saying this is that as the little structure
grows, we must have the same tiny parts up to equivalence of tiny
parts. I.e., every tiny part of the enlarged structure must be
equivalent to some tiny part of the little structure.
If an enlargement of the given little structure meets this tiny
pattern condition then it is called a continuation of the little
structure.
A maximal continuation of the little structure is a continuation of
the little structure that has no further continuation of the little
structure (all within R). Note that a maximal continuation of the
little structure is the same as a continuation of the little structure
that has no further continuation of this continuation of the little
structure (all within R).
By general mathematical considerations, we know that every little
structure residing in E has such a maximal continuation residing in R.
Symmetry is a highly desirable thing to have, and occurs so much in
nature. Accordingly, it is desirable for the little structure to grow
into a maximal continuation within R which exhibits some symmetry.
We can look at symmetry in this way. We identify one subregion of R
that naturally transforms to a second subregion of R. We have symmetry
with respect to these subregions just in case this natural
transformation transforms the part of the maximal continuation living
in the first subregion onto the part of the maximal continuation
living in the second subregion. So in particular, when you shift your
vision from the first subregion to the second subregion, you see the
same part of the maximal continuation.
The claim is that every little structure has a maximal continuation
within R with symmetry from certain specific subregions of R onto
others. And the claim can only be proved by using far more than the
usual ZFC axioms for mathematics. A major thrust of the research is to
determine just what transformations between subregions can be used
here.
There are crude analogies with biology and cosmology. We can think of
E as a region where we find a little structure called a seed (say from
the ground down about a foot into the soil). The seed is allowed to
grow within a wider region R, with plenty of space above ground. The
plant grows in such a way that tiny patterns in the plant are already
present in the seed (think DNA). The mature plant exhibits much
delightful symmetry. Note that here there is a real continuation
process leading up to the fully mature plant, whereas in our
development thus far we have only considered the resulting maximal
continuation (the end result) and not any steps leading up to it.
However, in sections ??, we consider towers of continuations that
reflect the continuation process, and not just the end result.
In cosmology, we can think of the little structure as the primordial
stuff of the big bang, which then grows into what we see today, with
all of its glorious symmetries. We can think of all of the tiny
patterns in what we see today as being somehow present in some form in
the primordial stuff (think the smallest subatomic particles, perhaps
yet to be discovered). However, in this crude analogy, it is not clear
how we should think of the region R and the subregion E. In our setup,
we are thinking of a very conventional idea of space as a fixed region
of points. We need to develop a more nuanced setup in order to refine
this crude analogy with cosmology.
In the formal development, the region R is Q[-1,1]^k, where Q[-1,1] is
the closed rational interval Q intersect [-1,1]. The subregion E is
Q[-1,0)^k. The structures within Q[-1,1]^k are the subsets of
Q[-1,1]^k. The parts of a set are its subsets, and its enlargements
are its supersets. The little structures within Q[-1,0)^k are the
finite subsets of Q[-1,0)^k. The tiny structures within Q[-1,1]^k are
the subsets with at most two elements. Two tiny structures are
equivalent if and only if they are order isomorphic. For the symmetry,
we use boxes and line segments as the regions, and translations for
the transformations.
2. MAXIMAL CONTINUATION IN Q[-1,1]^k
We begin with the definition of maximal continuation in Q[-1,1]^k. The
order of presentation in subsections 2.1 - 2.4 best from a
developmental point of view. For the development most directly
relevant to the informal discussion in section 1, see section 2.4. To
simplify the definitions, we use Q[-1,1]^k instead of more general
subspaces of Q^k.
DEFINITION 2.1. Q,N,Z are the set of all rationals, nonnegative
integers, and integers, respectively. We use a,b,c,p,q for rationals,
n,m,r,s,t for positive integers, x,y,z,w,u,v for tuples of rationals,
all with or without subscripts, unless otherwise indicated. Intervals
are required to be intervals in Q which are nonempty and have
endpoints in the extended rationals. Q[(p,q)] is the interval of
rationals with endpoints p,q, with the four endpoint situations.
Intervals may be degenerate, in the sense of having only one element.
The presence of U. indicates that the left and right sets are
disjoint.
DEFINITION 2.2. Let A,B containedin Q[-1,1]^k. fld(A) is the set of
all coordinates of elements of A. An order isomorphism from A onto B
is an increasing bijection h:fld(A) into fld(B) such that for all
p_1,...,p_k in fld(A), (p_1,...,p_k) in A iff (h(p_1),...,h(p_k)) in
B. B is a continuation of A in Q[-1,1]^k if and only if A containedin
B containedin Q[-1,1]^k, and A,B have the same <=2 element subsets up
to order isomorphism. The latter asserts that there is an order
isomorphism from every <=2 element subset of B onto some (necessarily
equinumerous) subset of A. B is a maximal continuation of A in
Q[-1,1]^k if and only if B is a continuation of A in Q[-1,1]^k and no
B U. {x} is an continuation of A in Q[-1,1]^k.
THEOREM 2.1. Every finite subset of Q[-1,1]^k has a maximal
continuation in Q[-1,1]^k. Furthermore, the maximal continuation can
be taken to be polynomial time computable.
THEOREM 2.2. Subsets of Q[-1,1] of cardinality at most 1 are their own
unique maximal continuation in Q[-1,1]. The remaining finite subsets
of Q[-1,1] have Q[-1,1] as their unique maximal continuation in
Q[-1,1].
We investigate the symmetry properties for which the following holds.
For finite subsets of Q[-1,0)^k, some maximal continuation in
Q[-1,1]^k exhibits the given symmetry property. We use Q[-1,0)^k for
this purpose, in accordance with section 1. We do not want to use
Q[-1,1] for this purpose. See Theorem 2.3.1.
The following definition is used in the lead statement at the
beginning of the Abstract.
DEFINITION 2.3. Let S,A,B containedin Q[-1,1]^k. S translates from A
onto B if and only if there exists c in Q^k such that for all x in
Q[-1,1]^k,
i. x in A if and only if x+c iin B.
ii. x in S intersect A iff x+c in S intersect B.
We give a name to the lead statement.
MAXIMAL CONTINUATION TRANSLATION (specific). MCTs. For finite subsets
of Q[-1,0)^1+k, some maximal continuation in Q[-1,1]^1+k translates
from Q[-1,0) x {(0/k,...,(k-1)/k)} onto Q[-1,0) x {1/k,...,k/k)}.
We can also use the closely related
DEFINITION 2.3.' Let S,A,B containedin Q[-1,1]^k. S translates' from A
onto B if and only if there exists c in Q^k such that for all x in
Q[-1,1]^k, x in S intersect A iff x+c in S intersect B.
The results remain unaffected. We find the original definition more
natural than this ostensibly simpler variant. We refer to the informal
discussion in section 1. We designate two natural fields of vision
A,B, and then say that S looks the same in A as it does in B. But we
really do want to say that before brining S in, fields of vision A and
B are equivalent in the relevant sense.
An alternative lead statement that can only be proved by going far
beyond the usual ZFC axioms for mathematics uses Definition 2.2.1.
MAXIMAL CONTINUATION EMBEDDING (specific). MCEs. For finite subsets of
Q[-1,0)^k, some maximal continuation in Q[-1,1]^k is partially
embedded by the function p if 0 <= p < 0; p+(1/k) if p =
0/k,...,(k-1)/k.
The following list of statements in this section 2 have the featured
logical properties:
1. Maximal Continuation Embedding (order theoretic).
2. Maximal Continuation Embedding (gaps).
3. Proposition 2.3.6.
4. Maximal Continuation Translation (specific).
5. Maximal Continuation Translation (box1).
6. Maximal Continuation Translation (box2).
7. Maximal Continuation Translation (lines).
THEOREM 2.2. 1-7 are explicitly Pi01 over WKL_0 via the Goedel
Completeness Theorem.
THEOREM 2.3. 1-7 are provable in SRP+ but not in SRP, assuming SRP is
consistent. 1-7 are provably equivalent to Con(SRP) over WKL_0. In any
fixed dimension k, 1-7 is provable in SRP. Here SRP cannot be replaced
by any fixed SRP[n], assuming SRP is consistent.
2.1. ORDER THEORETIC SETS
The order theoretic subsets of the Q[-1,1]^k form a robust natural
countable family of concrete subsets of Q[-1,1]^k. Yet they are rich
enough to have rather intricate structure.
DEFINITION 2.1.1. E containedin Q[-1,1]^k is order theoretic if and
only if E = {(p_1,...,p_k): phi}, where phi is a propositional
combination of inequalities of the forms p_i < p_j, p_i < r, r < p_i,
where 1 <= i,j <= k and r is a rational number constant drawn from
Q[-1,1].
Thus for each fixed k, there are infinitely many order theoretic
subsets of Q[-1,1]^k, because the r can be drawn arbitrarily from
Q[-1,1]. However, for a given k and finite list of parameters from
Q[-1,1], there are only finitely many order invariant subsets of
Q[-1,1]^k (with parameters from the list).
THEOREM 2.1.1. A subset of Q[-1,1]^k is order theoretic if and only if
it is first order definable over (Q[-1,1],<) in the sense of model
theory.
DEFINITION 2.1.2. F::Q[-1,1]^k into Q[-1,1]^k if and only if F is a
partial function from Q[-1,1]^k into Q[-1,1]^k. I.e., F is a function
whose domain is a subset of A and whose range is a subset of B. For
any function g, dom(g) is the domain of g and rng(g) is the range of
g.
The order theoretic subsets of Q[-1,1] and the order theoretic
f::Q[-1,1] into Q[-1,1] are readily understandable.
THEOREM 2.1.2. A subset of Q[-1,1] is order theoretic if and only if
it can be written as A_1 U. ... U. A_k U. B, where the A's are
nonempty open intervals from left to right, and B is finite.
THEOREM 2.1.3. Let f::Q into Q. The following are equivalent.
i. dom(f) can be written as A_1 U. ... U. A_k U. B, where the A's are
nonempty open intervals from left to right, and B is finite. In this
decomposition, for each i, f is constant or the identity on A_i.
ii. f is order theoretic.
THEOREM 2.1.4. Let f::Q into Q be strictly increasing. The following
are equivalent.
i. dom(f) can be uniquely written as A_1 U. ... U. A_k U. B, k >= 0,
where the A's are nonempty open intervals from left to right, and B is
finite. In this decomposition, for each i, f is the identity on A_i.
ii. f is order theoretic.
In i, f moves only finitely many points.
2.2. MAXIMAL CONTINUATION EMBEDDING
Maximal continuation embedding can be viewed as a special case of the
maximal continuation invariance in section 2.3. It is a basic tool for
sections 2.3 and 2.4, as well as being of independent interest.
We cannot require any serious F invariance in Theorem 2.1.1.
THEOREM 2.2.1. Let f::Q[-1,1] into Q[-1,1]. Suppose for finite subsets
of Q[-1,1]^k, some maximal continuation in Q[-1,1]^k is f embedded.
Then f is an identity function.
Proof: Suppose f(p) not= p. Clearly the only continuation of {p} is
{p}, and {p} is not f embedded. QED
What went wrong? Well, looking at section 1, let's stop using E = R =
Q[-1,1]^k. We are supposed to use E = Q[-1,0)^k.
DEFINITION 2.2.1. f is an embedding of S containedin Q[-1,1]^k if and only if
i. f::Q[-1,1] into Q[-1,1] is one-one.
ii. For all p_1,...,p_k in Q[-1,1], (p_1,...,p_k) in S iff
(f(p_1,...,f(p_k)) in S.
Note that we can equivalently replace Q[-1,1] with dom(f).
DEFINITION 2.2.2. f is embed usable if and only if f::Q[-1,1] into
Q[-1,1] is one-one and the following holds for all k >= 1. For finite
subsets of Q[-1,0)^k, some maximal continuation in Q[-1,1]^k is f
embedded. f is embed usable/k if and only if this holds for k.
THEOREM 2.2.1. The embed usable (usable/k) functions are closed under
composition and function inverse, and include all identity functions.
THEOREM 2.2.2. f is embed usable/1 if and only if f::Q[-1,1] into
Q[-1,1] and f,f^-1 exist and do not move any negative rationals.
Proof: Let f be embed usable/1. Then f::Q[-1,1] into Q[-1,1] is
one-one. Suppose f(p) = q, where (p < 0 and p not= q) or (p not= q and
q < 0). The only maximal continuation of {p} in Q[-1,1] is {p} which
is not f invariant.
Let f::Q[-1,1] into Q[-1,1] is one-one, where f,f^-1 do not move any
negative rationals. By Theorem 2.3, we have only to show that every
finite subset of Q[-1,0)^k and Q[-1,1]^k itself are f invariant. This
is obvious. QED
THEOREM 2.2.3. Every embed usable function is strictly increasing and
it and its inverse do not move any negative rational. In fact, for any
k >= 2, this is true for embed usable/k.
Proof: Fix k >= 2. Let f be embed usable/k. Suppose p < q and f(p) >=
f(q). Note that {(-1,...,-1,-1/2), (-1,...,-1,-1/3),
(-1/2,...,-1/2,-1/3), (-1/2,...,-1/2,-1/4)} has the unique maximal
continuation in Q[-1,1]^k, {(r,...,r,s): r,s in Q[-1,1] and r < s},
which contains (p,...,p,q) but not (f(p),...,f(p),f(q)). Therefore it
is not f embedded. Suppose f(p) < f(q) and p >= q. Then this set
contains (f(p),...,f(p),f(q)) but not (p,...,p,q), and so is not f
embedded.
Suppose f(p) not= p, p < 0. Note that {(p,...,p)} has the unique
maximal continuation in Q[-1,1]^k, {(p,...,p)}, which is clearly not f
embedded. Suppose f(p) < 0, f(p) not= p. Note that {(f(p),...,f(p)}
has the unique continuation in Q[-1,1]^k, {(f(p),...,f(p)}, which is
clearly not f embedded. QED
Recall the order theoretic f::Q[-1,1] into Q[-1,1] which were very
simply characterized in section 2.1. There are already some very
simple such f for which embed usability is a delicate matter.
MAXIMAL CONTINUATION EMBEDDING (specific). MCEs. For k >= 1, function
p if -1 <= p < 0; p+(1/k) if p = 0,1/k,...,(k-1)/k, is embed usable.
We go well beyond the usual ZFC axioms for mathematics to prove this.
In fact, our proof uses what is called a subtle cardinal (far beyond
ZFC) even for k = 2. For k = 1, the proof stays within Z_2. We do know
that there exist k for which ZFC is not sufficient, but we have not
established that this is the case for k = 2. We lean to the opinion
that for k = 2, ZFC is not sufficient. We have to get heavily into the
details of the proofs of unprovability in order to address this issue.
No difficulties arise with finite functions.
THEOREM 2.2.4. Let k >= 2, and let f::Q[-1,1] into Q[-1,1] be finite.
The following are equivalent.
i. f is embed usable.
ii. f is embed usable/k.
iii. f is strictly increasing and f and its inverse do not move any
negative rationals.
Proof: i implies ii implies iii by Theorem 2.2.3. iii implies i is by
a substantial argument necessarily going well beyond the usual ZFC
axioms for mathematics. We first do it for order theoretic f. There is
an inclusion maximal extension g of f which satisfies *), and which is
the identity at new domain elements. Note that g is order theoretic
and satisfies iii, putting us in the order theoretic case. QED
However, for the order theoretic case, difficulties do arise which are
handled by going well beyond ZFC.
MAXIMAL CONTINUATION EMBEDDING (order theoretic). MCEot. Let k >= 2,
and let f::Q[-1,1] into Q[-1,1] be order theoretic or moves only
finitely many points. The following are equivalent.
i. f is embed usable.
ii. f is embed usable/k.
iii. f is strictly increasing and it and its inverse do not move any
negative rationals.
Proof: i implies ii implies iii by Theorem 2.2.3. iii implies i is by
a substantial argument necessarily going well beyond the usual ZFC
axioms for mathematics. We first do it for order theoretic f. Now
suppose f::Q[-1,1] moves only finitely many points. There is an
inclusion maximal extension g of f which satisfies iii, and which is
the identity at new domain elements. Note that g is order theoretic
and satisfies iii, putting us in the order theoretic case. QED
Obviously MCEot immediately implies MCEs. iii implies i is what needs
far more than ZFC.We know that there exists k such that iii implies ii
for k is beyond ZFC. iii implies ii for k = 1 is trivial. As a nice
probably somewhat long exercise, iii should imply ii for k = 2 in,
say, RCA_0. I would not be surprised if iii implies ii for k = 4
cannot be done in ZFC. Again, I have to get heavily into the details
of the unprovability proofs in order to address this issue.
These issues of the size of k in MCEs and MCEot are orthogonal because
the k's play such different roles.
We now move to a larger class of functions which are crucial for section 2.4.
DEFINITION 2.2.3. f is a piecewise translation if and only if
f::Q[-1,1] into Q[-1,1] and f is the disjoint union of finitely many
functions defined on intervals and which are of the form +c on these
respective intervals.
THEOREM 2.2.5. The piecewise translations are exactly the f::Q[0,1]
into Q[0,1] satisfying the following. There exists a positive integer
n such that the following holds. Subdivide Q[-1,1] into 2n adjacent
closed intervals of length 1/n. Then dom(f), ring(f) are each unions
of the interiors of some of these intervals, together with some of
their endpoints, Furthermore, f maps each of these open intervals in
its domain onto one of these open intervals in its range, and also
mades each of these endpoints in its domain to one of these endpoints
in its range.
Proof: Write f in any way according to Definition 2.2.3. Choose n so
that every endpoint of the intervals and every constant of translation
are integer multiples of 1/n. QED
Theorem 2.2.4 allows us to view piecewise translations as essentially
order theoretic objects. Of course, they are not themselves order
theoretic in the sense of section 2.1.
THEOREM 2.2.5. Let A,B be finite unions of intervals in Q[-1,1]. There
is at most one strictly increasing piecewise translation from A onto
B.
DEFINITION 2.2.4. Let f be a piecewise translation. A gap in f is a
non degenerate interval J in Q[-1,1] which is disjoint from dom(f) U
rng(f), where f maps Q[-1,p] into Q[-1,p], and Q[q,1] into Q[q,1].
MAXIMAL CONTINUATION EMBEDDING (gap). MCEg. Let k >= 2, and let
f::Q[-1,1] into Q[-1,1] be a piecewise translation with a gap. The
following are equivalent.
i. f is embed usable.
ii. f is embed usable/k.
iii. f is strictly increasing and it and its inverse do not move any
negative rationals.
Our understanding of the embed usability of piecewise translations
without a gap is quite poor. Look at
p if -1 <= p < 0; p+(1/2) if 0 <= p <= 1/2.
p if -1 <= p <= 0; p+1/2 if 0 <= p <= 1/2.
p if -1 <= p <= 0; p+(1/3) if 0 < p < 2/3; p if p = 1.
All three are piecewise translations that are strictly increasing and
are the identity on Q[-1,0).
THEOREM 2.2.6. p if -1 <= p < 0; p+(1/2) if 0 <= p <= 1/2 is embed usable.
We have no opinion as to whether the second of these three is embed usable.
We now sketch a proof that the third function is not embed usable.
However, we have no opinion as to whether the first is embed usable.
THEOREM 2.2.7. Some piecewise translation is strictly increasing, the
identity on the negative rationals, left continuous, and not embed
usable/3. In particular, p if -1 <= p <= 0; p+(1/3) if 0 < p < 2/3; p
if p = 1.
Proof: First construct a finite A containedin Q[-1,0)^4, whose
continuations are exactly the A containedin S contianedin Q[-1,1]^5
such that
i. S(p,q,r,s) implies p < q < r <= s.
ii. S(p,q,r,s) and S(p,q',r,s) implies q = q' .
Here p,q,r,s range over Q[-1,1].
Let S be a maximal continuation of A in Q[-1,1]^4 which is embedded by
the displayed function. Suppose there are no p such that S(0,p,1,1).
Then the maximality of S is violated. Let S(0,p,1,1). If p < 2/3 then
S(0,p+(1/3),1,1). If p >= 2/3 then S(0,p-(1/3,1,1). This is my the
embedding. But this contradicts ii. QED
2.3.. MAXIMAL CONTINUATION INVARIANCE
We now seek to impose invariance conditions on the maximal
continuations. In this section, we discuss a particularly general kind
of invariance condition, before using translations in section 2.4.
DEFINITION 2.3.1. S containedin Q[-1,1]^k is F invariant if and only if
i. F:::Q^k into Q^k is one-one.
ii. For all x in dom(F), x in S iff F(x) in S.
We cannot require any serious F invariance in Theorem 2.1.1.
THEOREM 2.3.1. Let F::Q[-1,1]^k into Q[-1,1]^k. Suppose for finite
subsets of Q[-1,1]^k, some maximal continuation in Q[-1,1]^k is F
invariant. Then F is an identity function.
Proof: Suppose F(x) not= x. Clearly the only continuation of {x} is
{x}, and {x} is not F invariant. QED
What went wrong? Well, looking at section 1, let's stop using E = R =
Q[-1,1]^k. We are supposed to use E = Q[-1,0)^k.
DEFINITION 2.3.2. F::Q[-1,1]^k into Q[-1,1]^k is usable (for maximal
continuation invariance) if and only if the following holds. For
finite subsets of Q[-1,0)^k, some maximal continuation in Q[-1,1]^k is
F invariant. A,B containedin Q[-1,1]^k are usable if and only if some
bijection F:A into B is usable.
An overarching goal is to understand what the usable F are, and
consequently, what the usable A,B are. This has proved to be very
challenging even for rather concrete F,A,B. However, there are some
clarifying necessary conditions and sufficient conditions for being
usable.
There is an obvious link between the embed usability of section 2.2
and usability.
DEFINITION 2.3.3. Let f::Q[-1,1]^k into Q[-1,1]^k. We say that F is a
lifting of f if and only if there exists k such that F::Q[-1,1]^k into
Q[-1,1]^k, dom(F) = dom(f)^k, and F(p_1,...,p_k) =
(f(p_1),...,f(p_k)).
THEOREM 2.3.2. f is embed usable if and only if every lifting of f is
usable. f is usable/k if and only if every lifting of f with domain in
Q[-1,1]^k is usable/k.
Recall that for embed usability, we used the important condition *) on
f::Q[-1,1] into Q[-1,1]. We develop an analogously important condition
on F::Q[-1,1]^k into Q[-1,1]^k.
DEFINITION 2.3.4. x,y in Q[-1,1]^k are order equivalent if and only if
for all 1 <= i,j <= k, x_i < x_j iff y_i < y_j. x,y in Q[-1,1]^k are
order equivalent over the negative rationals if and only if for all p
< 0, (x,p) and (y,p) are order equivalent.
Note that both of these notions are equivalence relations.
THEOREM 2.3.3. Let x,y in Q^k be order equivalent. The following are equivalent.
i. x,y have the same set of negative coordinates.
ii. x,y have the same negative coordinates in the same positions.
iii. x,y are order equivalent over the negative rationals.
THEOREM 2.3.4. If F is usable then every x,F(x) are order equivalent
over the negative rationals.
Proof: Let x,F(x) be not order equivalent over the negative rationals.
case 1. x,F(x) are not order equivalent. Let B be a k element subset
of Q[-1,0). Let E be the set of all k-tuples from B that are order
equivalent to x. Then the unique maximal continuation of B consists of
all tuples from Q[-1,1]^k that are order equivalent to x. This cannot
be F invariant.
case 2. x_i < 0 and ,F(x)_i not= x_i. Let B be a 2k+1 element subset
of Q[-1,0) with x_i as the middle element, and excluding F(x)_i. Let E
be the set of all k-tuples from B whose i-th coordinate is x_i. Then
the unique maximal 2-continuation of B consists of all tuples from
Q[-1,1]^k whose i-th coordinate is x_i. This cannot be F invariant.
case 3. F(x)_i < 0 and x_i not= F(x)_i. Argue as in case 2, switching
x_i with F(x)_i.
QED
THEOREM 2.3.5. Let k >= 2, and let F::Q[-1,1]^k into Q[-1,1^k] be
finite. The following are equivalent.
i. F is usable.
ii. F is usable/k.
iii. Every x,F(x) are order equivalent over the negative rationals.
Proof: i implies ii implies iii by Theorem 2.3.4. Suppose iii. Let A =
fld(F). According to the proof of MCEot (the part that stays well
below Z_2), for finite subsets of Q[-1,1]^k, some maximal continuation
S in Q[-1,1]^k has the following property. If x,y are in A^k are order
equivalent and have the same negative elements of A in the same
positions, then x in S iff y in S. Clearly S is F invariant. QED
In section 2.2, after Theorem 2.2.4, we characterized embed usability
for order theoretic f, but it required us to go well beyond ZFC. Here
we would like to do something analogous for usability of order
theoretic F. There seem to be many difficulties here. However, there
is an important special case that will be used in section 2.4.
PROPOSITION 2.3.6. Let F:J^i x E^j, where J is an interval in
Q[-1,1]^i, E is a finite subset of Q[-1,1]. Assume that for all u in
E, the function F(x,u) is the identity on J^i. Then F is usable if and
only if F preserves order equivalence over the negative rationals.
We label the above as a Proposition since we prove it by necessarily
going well beyond ZFC.
Note that the F in Proposition 2.3.6 are order theoretic. If we use
multiple intervals, or a union of intervals, instead of just one
interval there, some difficulties arise which we have not sorted out.
THEOREM 2.3.7. For all k >= 2, there is an F::Q[-1,1]^k into Q[-1,1]^k
with every x,F(x) order equivalent over the negative rationals, that
is not usable. We can take F to be piecewise linear with domain
Q[-1,1]^k.
Proof: This can be proved by brutally using Theorem 2.2.7. However, we
give a simpler argument resulting in a simpler function - but not a
piecewise translation. Let F be defined at exactly the (p,q,...,q), 0
<= p < q <= 1, with F(p,q,...,q) = (p,(p+q)/2,...,(p+q)/2). Let E be a
finite subset of Q[-1,0)^k consisting of elements of the form
(p,q,...,q), p < q, where
i. (p,q,...,q), (p,q',...,q') in E implies q = q'.
ii. There exist (p,q,...,q), (p',q',...,q') in E with p < p', and with
all possibilities for the placement of q with respect to p',q'. I.e.,
below p', at p', between p',q', at q', or above q'.
The continuations of E are exactly its supersets of k-tuples whose
elements have the form (p,q,...,q), p < q, where q uniquely depends on
p. Thus its maximal continuations have for each p, a unique q with
(p,q,...,q) included. Clearly such a set must not be F invariant. For
the second claim, extend F to all of Q[-1,1]^k by the identity. QED
2.4. MAXIMAL CONTINUATION TRANSLATION
Recall this definition from the beginning of section 2.
DEFINITION 2.3. Let S,A,B containedin Q[-1,1]^k. S translates from A
onto B if and only if there exists c in Q^k such that for all x in
Q[-1,1]^k,
i. x in A if and only if x+c iin B.
ii. x in S intersect A iff x+c in S intersect B.
DEFINITION 2.4.1. A,B are translation usable if and only if there
exists k such that the following holds. For finite subsets of
Q[-1,0]^k, some maximal continuation in Q[-1,1]^k translates from A
onto B.
We can now restate MCTs, which is our lead statement at the beginning
of the Abstract, in the following form.
MAXIMAL CONTINUATION TRANSLATION (specific). MCTs. For all k, Q[-1,0)
x {(0/k,...,(k-1)/k)}, Q[-1,0) x {(1/k,...,k/k)} are translation
usable.
Here is a necessary condition for translation usability.
THEOREM 2.4.1. If A,B are translation usable then A,B have the same
elements up to order equivalence over the negative rationals.
Note that these two displayed sets are both boxes and lines segments.
First we focus on boxes.
DEFINITION 2.4.2. A box is a product of at least 1 and finitely many
intervals in Q[-1,1]. The intervals of a box are these factors. The
sides of a box are its non degenerate intervals.
MAXIMAL CONTINUATION TRANSLATION (box1). MCTb1. Two boxes whose sides
have only sides of length 1 are translation usable if and only if they
have the same elements up to order equivalence over the negative
rationals.
Here is a sharper form.
MAXIMAL CONTINUATION TRANSLATION (box2). MCTb2. Two boxes whose sides
are all the same or have the same respective lengths >=1, are
translation usable if and only if they have the same elements up to
order equivalence over the negative rationals.
DEFINITION 2.4.3. A line segment is the segment between two points in
some Q[-1,1]^k, with or without the two points.
MAXIMAL CONTINUATION TRANSLATION (lines). MCTl. Two line segments of
the same length >= 1, in the direction of a vector of 0's and 1's, are
translation usable if and only if they have the same elements up to
order equivalence over the negative rationals.
***********************************************
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 698th 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-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html
600: Removing Deep Pathology 1 8/15/15 10:37PM
601: Finite Emulation Theory 1/perfect? 8/22/15 1:17AM
602: Removing Deep Pathology 2 8/23/15 6:35PM
603: Removing Deep Pathology 3 8/25/15 10:24AM
604: Finite Emulation Theory 2 8/26/15 2:54PM
605: Integer and Real Functions 8/27/15 1:50PM
606: Simple Theory of Types 8/29/15 6:30PM
607: Hindman's Theorem 8/30/15 3:58PM
608: Integer and Real Functions 2 9/1/15 6:40AM
609. Finite Continuation Theory 17 9/315 1:17PM
610: Function Continuation Theory 1 9/4/15 3:40PM
611: Function Emulation/Continuation Theory 2 9/8/15 12:58AM
612: Binary Operation Emulation and Continuation 1 9/7/15 4:35PM
613: Optimal Function Theory 1 9/13/15 11:30AM
614: Adventures in Formalization 1 9/14/15 1:43PM
615: Adventures in Formalization 2 9/14/15 1:44PM
616: Adventures in Formalization 3 9/14/15 1:45PM
617: Removing Connectives 1 9/115/15 7:47AM
618: Adventures in Formalization 4 9/15/15 3:07PM
619: Nonstandardism 1 9/17/15 9:57AM
620: Nonstandardism 2 9/18/15 2:12AM
621: Adventures in Formalization 5 9/18/15 12:54PM
622: Adventures in Formalization 6 9/29/15 3:33AM
623: Optimal Function Theory 2 9/22/15 12:02AM
624: Optimal Function Theory 3 9/22/15 11:18AM
625: Optimal Function Theory 4 9/23/15 10:16PM
626: Optimal Function Theory 5 9/2515 10:26PM
627: Optimal Function Theory 6 9/29/15 2:21AM
628: Optimal Function Theory 7 10/2/15 6:23PM
629: Boolean Algebra/Simplicity 10/3/15 9:41AM
630: Optimal Function Theory 8 10/3/15 6PM
631: Order Theoretic Optimization 1 10/1215 12:16AM
632: Rigorous Formalization of Mathematics 1 10/13/15 8:12PM
633: Constrained Function Theory 1 10/18/15 1AM
634: Fixed Point Minimization 1 10/20/15 11:47PM
635: Fixed Point Minimization 2 10/21/15 11:52PM
636: Fixed Point Minimization 3 10/22/15 5:49PM
637: Progress in Pi01 Incompleteness 1 10/25/15 8:45PM
638: Rigorous Formalization of Mathematics 2 10/25/15 10:47PM
639: Progress in Pi01 Incompleteness 2 10/27/15 10:38PM
640: Progress in Pi01 Incompleteness 3 10/30/15 2:30PM
641: Progress in Pi01 Incompleteness 4 10/31/15 8:12PM
642: Rigorous Formalization of Mathematics 3
643: Constrained Subsets of N, #1 11/3/15 11:57PM
644: Fixed Point Selectors 1 11/16/15 8:38AM
645: Fixed Point Minimizers #1 11/22/15 7:46PM
646: Philosophy of Incompleteness 1 Nov 24 17:19:46 EST 2015
647: General Incompleteness almost everywhere 1 11/30/15 6:52PM
648: Necessary Irrelevance 1 12/21/15 4:01AM
649: Necessary Irrelevance 2 12/21/15 8:53PM
650: Necessary Irrelevance 3 12/24/15 2:42AM
651: Pi01 Incompleteness Update 2/2/16 7:58AM
652: Pi01 Incompleteness Update/2 2/7/16 10:06PM
653: Pi01 Incompleteness/SRP,HUGE 2/8/16 3:20PM
654: Theory Inspired by Automated Proving 1 2/11/16 2:55AM
655: Pi01 Incompleteness/SRP,HUGE/2 2/12/16 11:40PM
656: Pi01 Incompleteness/SRP,HUGE/3 2/13/16 1:21PM
657: Definitional Complexity Theory 1 2/15/16 12:39AM
658: Definitional Complexity Theory 2 2/15/16 5:28AM
659: Pi01 Incompleteness/SRP,HUGE/4 2/22/16 4:26PM
660: Pi01 Incompleteness/SRP,HUGE/5 2/22/16 11:57PM
661: Pi01 Incompleteness/SRP,HUGE/6 2/24/16 1:12PM
662: Pi01 Incompleteness/SRP,HUGE/7 2/25/16 1:04AM
663: Pi01 Incompleteness/SRP,HUGE/8 2/25/16 3:59PM
664: Unsolvability in Number Theory 3/1/16 8:04AM
665: Pi01 Incompleteness/SRP,HUGE/9 3/1/16 9:07PM
666: Pi01 Incompleteness/SRP,HUGE/10 13/18/16 10:43AM
667: Pi01 Incompleteness/SRP,HUGE/11 3/24/16 9:56PM
668: Pi01 Incompleteness/SRP,HUGE/12 4/7/16 6:33PM
669: Pi01 Incompleteness/SRP,HUGE/13 4/17/16 2:51PM
670: Pi01 Incompleteness/SRP,HUGE/14 4/28/16 1:40AM
671: Pi01 Incompleteness/SRP,HUGE/15 4/30/16 12:03AM
672: Refuting the Continuum Hypothesis? 5/1/16 1:11AM
673: Pi01 Incompleteness/SRP,HUGE/16 5/1/16 11:27PM
674: Refuting the Continuum Hypothesis?/2 5/4/16 2:36AM
675: Embedded Maximality and Pi01 Incompleteness/1 5/7/16 12:45AM
676: Refuting the Continuum Hypothesis?/3 5/10/16 3:30AM
677: Embedded Maximality and Pi01 Incompleteness/2 5/17/16 7:50PM
678: Symmetric Optimality and Pi01 Incompleteness/1 5/19/16 1:22AM
679: Symmetric Maximality and Pi01 Incompleteness/1 5/23/16 9:21PM
680: Large Cardinals and Continuations/1 5/29/16 10:58PM
681: Large Cardinals and Continuations/2 6/1/16 4:01AM
682: Large Cardinals and Continuations/3 6/2/16 8:05AM
683: Large Cardinals and Continuations/4 6/2/16 11:21PM
684: Large Cardinals and Continuations/5 6/3/16 3:56AM
685: Large Cardinals and Continuations/6 6/4/16 8:39PM
686: Refuting the Continuum Hypothesis?/4 6/616 9:29PM
687: Large Cardinals and Continuations/7 6/7/16 10:28PM
688: Large Cardinals and Continuations/8 6/9/16 11::41PM
689: Large Cardinals and Continuations/9 6/11/16 2:51PM
690: Two Brief Sketches 6/13/16 1:18AM
691: Large Cardinals and Continuations/10 6/13/16 9:09PM
692: Large Cardinals and Continuations/11 6/15/16 10:22PM
693: Refuting the Continuum Hypothesis?/5 6/21/16 10:44AM
694: Large Cardinals and Continuations/12 6/29/16 11:46PM
695: Refuting the Continuum Hypothesis?/6 7/16 2:28AM
696: Refuting the Continuum Hypothesis?/7 7/ 5/16 7:41PM
697: Refuting the Continuum Hypothesis?/8 7/6/16 6:40PM
Harvey Friedman
More information about the FOM
mailing list