936: Stable Maximality/Tangible Incompleteness/2

[Harvey Friedman]

We improve on https://cs.nyu.edu/pipermail/fom/2022-June/023382.html in two
ways. Firstly, we add a stronger notion of stability. The former
critical stability is not called global critical stability. And we
introduce the stronger local critical stability.

Secondly, we correct the definition of emulator and maximal emulator so
that they properly use ambient spaces as in S containedin D^k, where the
ambient space is D^k. .

Section 1 remains unchanged.

The lead statements of Tangible Incompleteness are now Proposition 3.12 and
the stronger Proposition 3.13.

1. Stability sequences for sets.
2. Critical and super critical stability sequences for sets.
3. Tangible Incompleteness.

1. STABILITY SEQUENCES FOR SETS

We use n,m,r,s,t,i,j,k, with and without subscripts, for positive integers
unless indicated otherwise.

DEFINITION 1.1. We say that x is a stability sequence for S containedin D^k if
and only if
i. x is a nonempty finite sequence from D with distinct terms.
ii. (y_1,...,y_k) in S iff (z_1,...,z_k) in S, provided each z_i is the
next term in x after the term y_i. in x

I.e., membership in S for sequences of terms of x, not including the last
term of x, remains stable after replacing each term by the next term of x.
We can view this as a kind of local invariance or shifting condition on S.

THEOREM 1.1. Every S containedin D^k, D infinite, has stability sequences of
 every nonzero finite length.

This is proved using the classical infinite Ramsey theorem from 1930.
However, at this level of generality, we really have no control over the
stability sequences.

THEOREM 1.2. Let D be infinite. There exists S containedin D^2 such that
for |D| many d in D, d is not present in any stability sequence of length 3 for
S containedin D^2.

However, we have much greater control for important sets S from core
mathematics. It is natural to focus on the rationals, real algebraics, and
reals.

THEOREM 1.3. Let J be a nondegenerate interval of real numbers and S
containedin J^k be semi algebraic. For all n >= 1, the set of all maximum
(minimum) terms of the stability sequences of length n for S containedin J^k
 is co finite in J.

THEOREM 1.4. Let J be a nondegenerate interval of real algebraic numbers
and S containedin J^k be rational semi algebraic. For all n >= 1, the set
of all maximum (minimum) terms of the stability sequences of length n for S
containedin J^k is co finite in J.

THEOREM 1.5. Let J be a nondegenerate interval of rational numbers and S
containedin J^k be rational piecewise linear. For all n >= 1, the set of
all maximum (minimum) terms of the stability sequences of length n for S
containedin J^k is co finite in J.

2. LOCAL AND GLOBAL CRITICAL STABILITY SEQUENCES FOR SETS WITH UNDERLYING
LINEAR ORDERING

Now for the first time, we bring a linear ordering into the picture.

DEFINITION 2.1. We say that x is a global critical stability sequence  for
S containedin D^k if and only if
i. D = (D,<) is a linearly ordered set.
ii. x is a nonempty finite sequence from D with distinct terms.
iii. (y_1,...,y_k) in S iff (z_1,...,z_k) in S, provided for all i, z_i is
the next term in x after the term y_i in x, or y_i = z_i is less than all
terms of x.

DEFINITION 2.2. We say that x is a local critical stability sequence  for S
containedin D^k if and only if
i. D = (D,<) is a linearly ordered set.
ii. x is a nonempty finite sequence from D with distinct terms.
iii. (y_1,...,y_k) in S iff (z_1,...,z_k) in S, provided for all i, z_i is
the next term in x after the term y_i in x, or y_i = z_i is less than all
terms of x that are some y_j not= z_j or some z_j not= y_j.

Here global refers to the use of all points less than all terms of x. Local
refers to the use of all points less than all terms of x meeting come
criteria related to the given y_1,...,y_k,z_1,...,z_k.

It is obvious that local critical implies global critical and not vice
versa.

We can obviously simply Definition 2.2 slightly as follows:

DEFINITION 2.2'. We say that x is a local critical stability sequence  for
S containedin D^k if and only if
i. D = (D,<) is a linearly ordered set.
ii. x is a nonempty finite sequence from D with distinct terms.
iii. (y_1,...,y_k) in S iff (z_1,...,z_k) in S, provided for all i, z_i is
the next term in x after the term y_i in x, or y_i = z_i is less than all
y_j,z_j such that  y_j not= z_j or z_j not= y_j.

For the D we are interested in, we do not even have short global critical
stability sequences for general S.

THEOREM 2.1. Let |D| <= |R|, where D is linearly ordered.  There exists S
containedin D^2 such that there is no global critical stability sequence of
length 2 of S containedin D^2.

However, semi algebraic sets are quite different in this regard than
arbitrary sets.

THEOREM 2.2. Theorems 1.3 - 1.5 all hold with "stability" replaced by
"global critical stability", using the usual ordering on the J.

But local critical stability is harder to obtain.

THEOREM 2.3. Theorems 1.3 - 1.5 are false for local critical stability even
for dimension k = 3 and length n = 3.

A natural place where we can achieve local critical stability is in the
ordered semiring generated by 0,1 and generators 1 < g_1 < g_2 < ... . Here
we take semi algebraic to mean Boolean combinations of polynomial
inequalities with coefficients from N. The sequence g_1,...,g_n is a local
critical stability sequence for semi algebraic sets in this ordered
semiring. More can be done with wider notions of semi algebraic here.

THEOREM 2.4.Theorems 1.3 - 1.5 all hold with "stability" replace by "local
critical stability", using the ordered semigring generated by 0,1 and
generators 1 < g_1 < g_2 < ... .

3. TANGIBLE INCOMPLETENESS

Here J refers to any non degenerate interval of *rationals* with the usual
ordering. We combine global/local stability sequences with maximality. The
maximality notion that we use is particularly natural and does not involve
the order. The order only comes into play with the global/local critical
stability.

DEFINITION 3.1. Let S,T containedin D^k. An isomorphism is a bijection f:D into
D such that for all z in D^k, z in S iff f(z) in T. Here f applies
coordinatewise.

DEFINITION 3.2. T is an emulator of S containedin D^k if and only if T
containedin D^k, and every 2 element subset of T is isomorphic  to some 2
element subset of S.

DEFINITION 3.3. T is a maximal emulator of S containedin D^k if and only if T
is an emulator of S which is not a proper subset of any emulator T' of S.

THEOREM 3.1. Every subset of every D^k  has a maximal emulator.

THEOREM 3.2. Every subset of J^k has a maximal emulator.

Corresponding to Theorem 1.1:

THEOREM 3.3. Every subset of J^k has a maximal emulator with a stability
sequence of length n.

Corresponding to Theorem 2.2:

PROPOSITION 3.4. Every subset of J^k has a maximal emulator with a
global critical
stability sequence of length n.

Corresponding to Theorem 2.4:

PROPOSITION 3.5. Every subset of J^k has a maximal emulator with a
local critical
stability sequence of length n.

We pause here and consider logical strengths.

THEOREM 3.6. Theorem 3.1 is provably equivalent to ZFC over ZF. Theorem 3.2
is provable in RCA0. Theorem 3.3 is provable in RCA0 + Con(PA).
Propositions 3.4, 3.5 are provably equivalent to Con(SRP) over WKL0.

In light of the purely order theoretic nature of maximal emulators and
critical stability, we can fix the stability sequences in advance.

THEOREM 3.7. Let x be a finite sequence of distinct elements of J, not
containing its left endpoint. Every subset of J^k has a maximal emulator
with stability sequence x.

PROPOSITION 3.8. Let x be a finite sequence of distinct elements of J, not
containing its left endpoint. Every subset of J^k has a maximal emulator
with global critical stability sequence x.

PROPOSITION 3.9. Let x be a finite sequence of distinct elements of J, not
containing its left endpoint. Every subset of J^k has a maximal emulator
with local critical stability sequence x.

THEOREM 3.10. Theorem 3.7 is provable in WKL0 + Con(PA). Propositions 3.8,
3.9 are provably equivalent to Con(SRP) over WKL0.

We can also use a specific natural critical stability sequence. Q[a,b] is Q
intersect [a,b].

THEOREM 3.11. Every subset of Q[0,n]^k has a maximal emulator with
stability sequence 1,2,...,n.

PROPOSITION 3.12. Every subset of Q[0,n]^k has a maximal emulator with
global stability sequence 1,2,...,n.

PROPOSITION 3.13. Every subset of Q[0,n]^k has a maximal emulator with
local stability sequence 1,2,...,n

THEOREM 3.14. Theorem 3.11 is provable in WKL0 + Con(PA). Propositions 3.12,
3.13 are provably equivalent to Con(SRP) over WKL0.

In the statements under investigation,  the front set can be obviously
taken to be finite. Also using this, we see that they each are implicitly
Pi01 via the Goedel Completeness Theorem (with the exception of the set
theoretic Theorem 3.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 936th 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-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM
918: Tangible Incompleteness and Clique Construction/1  12/11/21  10:15PM
919: Proof Theory of Arithmetic/2  12/11/21  10:17PM
920: Polynomials and PA  1/7/22  4:35PM
921: Polynomials and PA/2  1/9/22  6:57 PM
922: WQO Games  1/10/22 5:32AM
923: Polynomials and PA/3  1/11/22  10:30 PM
924: Polynomials and PA/4  1/13/22  2:02 AM
925: Polynomials and PA/5  2/1/22  9::04PM
926: Polynomials and PA/6  2/1/22 11:20AM
927: Order Invariant Games/1  03/04/22  9:11AM
928: Order Invariant Games/2  03/7/22  4:22AM
929: Physical Infinity/randomness  3/21/22 02:14AM
930: Tangible Indiscernibles/1 05/07/22  7:46PM
931: Tangible Indiscernibles/2 5/14/22  1:34PM
932: Tangible Indiscernibles/3  5/14/22  1:34PM
933: Provable Functions of Set Theories/1 5/16/22  7/11AM
934: Provable Ordinals of Set Theories/1  5/17/22  8:35AM
935: Stable Maximality/Tangible Incompleteness/1  6/3/22  7:05PM

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220604/87a630e6/attachment-0001.html>