853: Embedded Maximality (revisited)/1

Sun May 3 22:19:44 EDT 2020

You may recall that we used embeddings for the punch line for the Lead
Statements in Chapter 2 of the Tangible Incompleteness book. The first
version of #110
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
is based on Embeddings, But then we switched to Invariant Maximality
with the complete invariance with respect to ush/N.

We decided to have a section on Embedded Maximality where we go back
to the use of embeddings. The idea is that Embedded Maximality will
sit side by side Invariant Maximality, since on second thoughts, they
both have their advantages.

In Embedded Maximality the integers play no role (as points), and so
we work entirely in the spaces Q[-1,1]^k. In Invariant Maximality it is
much more convenient to work in the spaces Q[-n,n]^k. This is an
advantage for Embedded Maximality. On the other hand, in Invariant
Maximality we use a particular very natural function ush/N (the upper
shift for N) for our complete invariance. We also completely
characterize which suitably invariant shifts that can be used. This
advantage goes to Invariant Maximality.

1. FINITE EMBEDDED MAXIMALITY REVISITED
2. EMBEDDED MAXIMALITY REVISITED

1. Finite Embedded Maximality Revisited

DEFINITION 1.1. f::A into B if and only if f is a partial function
from A into B. fld(f) = dom(f) union rng(g). Let f::Q[-1,1] into Q[-1,1]
and S containedin Q[-1,1]^k. f embeds S if and only if for all
p1,...,pk,f(p1),...,f(pk) in Q[0,1], (p1,...,pk) in S iff
(f(p1),...,f(pk)) in S. f affects p if and only if
there exists q not= p such that f(p) = q or f(q) = p. Let K be a set
of f::Q[-1,1] into Q[-1,1]. K affects p if and only if some f in K
affects p.

FINITE EMBEDDED MAXIMALITY/1. (ACA0 + "for all n, the n-th Turing jump
of 0 exists"). Let K be a finite set of finite f::Q[-1,1] into Q[-1,1],
where all f in K are strictly increasing and K does not affect both -1
and 1. Then every order invariant subset of Q[-1,1]^2k has a K embedded
maximal square.

FINITE EMBEDDED MAXIMALITY/1. (ACA0 + "for all n, the n-th Turing jump
of 0 exists"). The following are equivalent for finite f::Q[-1,1] into
Q[-1,1]..
i. f is strictly increasing and there are no p,q in Q(-1,1) such that
((f(-1) = p and f(q) = 1) or (f(p) = -1 and f(1) = q)).
ii. Every order invariant subset of Q[0,1]^2k has an f embedded maximal square.

Proof: Assume i and let R be an order invariant relation on Q[0,1]^k
Assume f::Q[0,1] into Q[0,1] is finite and strictly increasing. We can
assume f affects both -1 and 1.
1. f(0) = 1 or f(1) = 0. Suppose (0,...,0) notR (0,...,0). Then any
maximal square excludes (0,...,0),(1,...,1), and so is f embedded.
Suppose (0,...,0) notR (1,...,1). Then any maximal square whose leg
has (1/2,...,1/2) is missing (0,...,0),(1,...,1), and so is f
embedded. Suppose (0,...,0) R (0,...,0) and (0,...,0) R (1,...,1).
Then any maximal square whose leg has (0,...,0),(1,...,1) is f
embedded.
2. We can assume p,q in Q(-1,1) and f(-1) = p and f(1) = q. Then there
exists -1 < r < 1 outside fld(f) such that f maps below r to below r
and maps above r to above r. Let R be an order
invariant binary relation on Q[-1,1]^k. Move from Q[-1,1] to Q. Build a
tower of maximal legs of squares on Q[-1,1]k, Q[-2,2]k, ..., Q[-n,n]k,
where n is sufficiently large relative to f,k. Choose a suitably large
set of indiscernibles among 1,2,...,n with respect to the constant 0,
the - operation, the maximal leg for Q[-n,n]k, and <, Let these be j_1
< j_2 ... j_2r. We will use the maximal leg on Q[-j_r,j_r]^k with
endpoints -j_r, j_r, and we use  -j_1,...,-j_r,j_r+1,...,j_2r and j-2r
to imitate f.

For the converse, it suffices to consider two cases for refutation in
dimension k = 2, even for order invariant graphs and maximal cliques.
.
a. f(-1) = 0, f(1/2) = 1. Define graph where the not adjacents are
the (a,b),(a,b), and the  (a<b),(c>d) and the (c>d),(a<b), where a < d
and b < c. Let S be an f embedded maximal clique. Then (0,1) in S
and so (-1,1/2) in S. Also (1/2,-1) in S and so (1,0) in S. But
(-1,1/2),(1,0) are not adjacent.

b. f(-1) = 0, f(0) = 1. Same graph. Let S be an f embedded maximal
clique. Then (0,1) in S and so (-1,0) in S. Also (0,-1) in S and
so (1,0) in S. But (-1,0),(1,0) are not adjacent.

QED

Necessary and sufficient conditions for finite sets K of finite
f::Q[-1,1] into Q[-1,1] require more work.

2. Embedded Maximality Revisited

DEFINITION 2.1. f::A into B if and only if f is a partial function
from A into B. fld(f) = dom(f) union rng(f). A fully extended finite
f::Q[-1,1] into Q[-1,1] is the result of extending some nonempty finite
g::Q[-1,1] into Q[-1,1] by the identity strictly below min(fld(g)) and
the identity strictly above max(fld(g)). A ;lower (higher) extended
finite f::Q[-1,1] into Q[-1,1] is the result of extending some nonempty finite
g::Q[-1,1] into Q[-1,1] by the identity strictly below min(fld(f))
(strictly above max(fld(f)). .

THEOREM 2.1. In all three notions from Definition 2.1, the g can be
unique recovered from the f,

EMBEDDED MAXIMALITY. The following hold.
i. Let f be a strictly increasing lower (upper) finite g:Q into Q.
Every order invariant subset of Q[-1,1]^2k has an f embedded maximal
square.
ii. Let f be a strictly increasing fully extended finite g::Q[-1,1]
into Q[-1,1].
Every order invariant subset of Q[-1,1]^2k has an f embedded maximal
square.
iii. Let K be a finite set of strictly increasing lower (upper) finite
g::Q[-1,1] into Q[-1,1]. Every order invariant subset of Q[-1,1]^2k has a K
embedded maximal square.
iv. There is a K consisting of a strictly increasing lower finite
g:Q[-1,1] into Q[-1,1] and a strictly increasing upper finite h:Q[-1,1] into
Q[-1,1] such that the following is false. Every order invariant subset of
Q[-1,1]^2k has a K embedded maximal square.

THEOREM 2.2. In Embedded Maximality, iv is provable in RCA0, i,ii,iii
are provable in WKL0 + Con(SRP). iii is provably equivalent to
Con(SRP) over RCA0 and implies Con(SRP) over RCA0.

We are morally certain that i,ii are provably equivalent to Con(SRP)
over WKL0 and imply Con(SRP) over RCA0, but the reversal is more
difficult than for iii, and we need to go over more details.

QUESTION: For which f::Q[-1,1]^k and for which sets K of f::Q[-1,1] is
it the case that every order invariant subset of Q[-1,1]^2k has an f
(K) embedded maximal square?

We are quite far from having a complete answer to this question, even
for very rudimentary f and K.

DEFINITION 2.2. f::Q[-1,1] into Q[-1,1] is an almost identity if and
only if f is
the union of a finite function and the identity on a finite union of
nonempty open intervals.

THEOREM 1.3. (Zermelo set theory) Let f::Q[-1,1] be an almost identity
where domain misses a nonempty interval in Q[-1,1].  Every order
invariant subset of Q[-1,1]^2k has an f embedded maximal square.

#######################################

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 851st 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-799 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

800: Beyond Perfectly Natural/6  4/3/18  8:37PM
801: Big Foundational Issues/1  4/4/18  12:15AM
802: Systematic f.o.m./1  4/4/18  1:06AM
803: Perfectly Natural/7  4/11/18  1:02AM
804: Beyond Perfectly Natural/8  4/12/18  11:23PM
805: Beyond Perfectly Natural/9  4/20/18  10:47PM
806: Beyond Perfectly Natural/10  4/22/18  9:06PM
807: Beyond Perfectly Natural/11  4/29/18  9:19PM
808: Big Foundational Issues/2  5/1/18  12:24AM
809: Goedel's Second Reworked/1  5/20/18  3:47PM
810: Goedel's Second Reworked/2  5/23/18  10:59AM
811: Big Foundational Issues/3  5/23/18  10:06PM
812: Goedel's Second Reworked/3  5/24/18  9:57AM
813: Beyond Perfectly Natural/12  05/29/18  6:22AM
814: Beyond Perfectly Natural/13  6/3/18  2:05PM
815: Beyond Perfectly Natural/14  6/5/18  9:41PM
816: Beyond Perfectly Natural/15  6/8/18  1:20AM
817: Beyond Perfectly Natural/16  Jun 13 01:08:40
818: Beyond Perfectly Natural/17  6/13/18  4:16PM
819: Sugared ZFC Formalization/1  6/13/18  6:42PM
820: Sugared ZFC Formalization/2  6/14/18  6:45PM
821: Beyond Perfectly Natural/18  6/17/18  1:11AM
822: Tangible Incompleteness/1  7/14/18  10:56PM
823: Tangible Incompleteness/2  7/17/18  10:54PM
824: Tangible Incompleteness/3  7/18/18  11:13PM
825: Tangible Incompleteness/4  7/20/18  12:37AM
826: Tangible Incompleteness/5  7/26/18  11:37PM
827: Tangible Incompleteness Restarted/1  9/23/19  11:19PM
828: Tangible Incompleteness Restarted/2  9/23/19  11:19PM
829: Tangible Incompleteness Restarted/3  9/23/19  11:20PM
830: Tangible Incompleteness Restarted/4  9/26/19  1:17 PM
831: Tangible Incompleteness Restarted/5  9/29/19  2:54AM
832: Tangible Incompleteness Restarted/6  10/2/19  1:15PM
833: Tangible Incompleteness Restarted/7  10/5/19  2:34PM
834: Tangible Incompleteness Restarted/8  10/10/19  5:02PM
835: Tangible Incompleteness Restarted/9  10/13/19  4:50AM
836: Tangible Incompleteness Restarted/10  10/14/19  12:34PM
837: Tangible Incompleteness Restarted/11 10/18/20  02:58AM
838: New Tangible Incompleteness/1 1/11/20 1:04PM
839: New Tangible Incompleteness/2 1/13/20 1:10 PM
840: New Tangible Incompleteness/3 1/14/20 4:50PM
841: New Tangible Incompleteness/4 1/15/20 1:58PM
842: Gromov's "most powerful language" and set theory  2/8/20  2:53AM
843: Brand New Tangible Incompleteness/1 3/22/20 10:50PM
844: Brand New Tangible Incompleteness/2 3/24/20  12:37AM
845: Brand New Tangible Incompleteness/3 3/28/20 7:25AM
846: Brand New Tangible Incompleteness/4 4/1/20 12:32 AM
847: Brand New Tangible Incompleteness/5 4/9/20 1 34AM
848. Set Equation Theory/1 4/15 11:45PM
849. Set Equation Theory/2 4/16/20 4:50PM
850: Set Equation Theory/3 4/26/20 12:06AM
851: Product Inequality Theory/1 4/29/20 12:08AM
852: Order Theoretic Maximality/1 4/30/20 7:17PM

Harvey Friedman