935: Stable Maximality/Tangible Incompleteness/1

Fri Jun 3 19:05:16 EDT 2022

We thoroughly rework 930-932, making the connection between very familiar
mathematical structures and Tangible Incompleteness simpler, and more
vivid. We now prefer to break things down to the most elemental level, and
pare down the generality in favor of complete immediate transparency. Later
we will be much more general after the well motivated development is
solidly in place.

Proposition 3.7 is our official lead Tangible Incompleteness. The rest of
this account can be viewed as a motivating buildup to Proposition 3.7
starting from the basic core mathematical development in sections 1,2. The
Tangible Incompleteness here results from a compelling combination of
stability (critically stability sequences) and maximality (maximal
emulators) in intervals of rationals.

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. 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 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 x_i = y_i < min(x).

For the D we are interested in, we do not even have short 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 critical stability sequence of length
at least 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
"critical stability", using the usual ordering on the J.

3. TANGIBLE INCOMPLETENESS

Here J refers to any non degenerate interval of *rationals* with the usual
ordering. We combine critical 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 critical stability.

DEFINITION 3.1. Let S,T be sets of k-tuples. fld(S) is the set of all
coordinates of elements of S. An isomorphism is a bijection f:fld(S) into
fld(T) such that for all z in fld(S)^k, z in S iff f(z) in T. Here f
applies coordinatewise.

DEFINITION 3.2. Let S,T be sets of k-tuples. T is an emulator of S if and
only if 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 if and only if T is an
emulator of S which is not a proper subset of any emulator T' containedin
fld(T)^k of S.

THEOREM 3.1. Every set of k-tuples 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 critical
stability sequence of length n.

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

THEOREM 3.5. 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.6. 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 critical stability sequence x.

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

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

THEOREM 3.8. Theorem 3.1 is provably equivalent to AxC over ZF. Theorems
3.2 and 3.3 are provable in RCA0. Proposition 3.4 is provable in WKL0 +
Con(SRP). Theorem 3.5 is provable in RCA0 + Con(PA). Propositions 3.6 and
3.7 are provably equivalent to Con(SRP) over WKL0.

In items 3.1 - 3.7, the front set can be obviously taken to be finite. Also
using this, we see that items 3.2 - 3.7 are each implicitly Pi01 via the
Goedel Completeness Theorem.

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

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 935th 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

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