939: Stable Maximality/1

[Harvey Friedman]

Here we give our choice of the lead statement for Concrete
Incompleteness from ZFC. The plan is for the treatment of this lead
statement to be presented in September on Zoom hosted by U Gent.

I now have a way of presenting the Lead Statement with almost no
definitions required. My latest expositional idea gets rid of even the
notion of Embedding and Invariance that I was using before. However,
after I present the raw simple combinatorial statement, we can stand
back and point to how it can be restated using these more abstract
notions. .

This new way of presenting the Lead Statement was inspired by how
effective I was able to present the Lead Statement in the important
and still intricate special case of Q[-1,1]^2 to the gifted high
school students at the 2022 Ross Summer Program. I now like the way I
now lift from dimension 2 to dimension k.

***********************

DEFINITION 1. Q[-n,n] is the set of rationals in [-n,n]. We say that
x,y in Q[-n,n]^k are order equivalent if and only if for all 1 <= i,j
<= k, x_i < x_j iff y_i < y_j.

Order equivalence has a rich history and the number of equivalence
classes in dimension k (using any linearly ordered set with at least k
elements) is sometimes called the Fubini numbers or ordered Bell
numbers. See https://oeis.org/A000670 My favorite formulation is in

Elliott Mendelson, Races with Ties, Math. Mag., Vol. 55, No. 3 (1982),
pp. 170-175.

which is the first line in comments in https://oeis.org/A000670 I like
my notation ot(k) for the number of order types of k-tuples. Then
ot(1) = 1, ot(2) = 3, ot(3) = 13, ot(4) = 75.

DEFINITION 2. S is an emulator of E containedin Q[-n,n]^k if and only
if S containedin Q[-n,n]^k and the concatenation of any two elements
of S is order equivalent to the concatenation of some two elements of
E.

DEFINITION 3. S is a maximal emulator of E containedin Q[-n,n]^k if
and only if S is an emulator of E containedin Q[-n,n]^k which is not a
subset of any emulator of E containedin Q[-n,n]^k.

The Lead Statement reads as follows:

LEAD STATEMENT. Every subset of Q[-n,n]^k has a negatively stable
maximal emulator.

In the 2022 Summer Ross Program for Gifted High School Students I
focused only on the easiest nontrivial case of Q[-1,1]^2. There the
notion of negatively stable can be stated in a way totally friendly
for Gifted High School.

HIGH SCHOOL DEFINITION. S containedin Q[-1,1]^2 is negatively stable
if and only if the following holds for all p in Q[-1,0),
(0,0) in S iff (1,1) in S
(p,0) in S iff (p,1) in S
(0,p) in S iff (1,p) in S

BASIC LEAD THEOREM.  BLT. Every subset of Q[-1,1]^2 has a negatively
stable maximal emulator.

I know how to prove BLT using just beyond Z_2 using transfinite
induction on omega_1. Naturally I didn't try to present this proof to
Gifted High School. But I did present a proof of the following easily
in RCA0:

EFFECTIVE LEAD THEOREM. ELT. Every <=3 element subset of Q[-1,1]^2 has
a recursive (algorithmic) negatively stable maximal emulator.

(Below see a stronger form of BLT, still in dimension 2, which I prove
in a bit more than Z_2, and where I believe that Z_2 does not
suffice.).

Now how do we conveniently give the higher dimensional form of BLT?
First note that we can put the High School Definition in the following
form. For all p,q in Q[-1,0), these four equivalences hold:

                           (p or 0, q or 0) in S if and only if (p or
1, q or 1) in S

DEFINITION 4. S containedin Q[-n,n]^k is negatively stable if and only
if for all p_1,...,p_k in Q[-1,0) and m_1,...,m_k in {0,...,n-1},
these 2^k equivalences hold:

                           (p_1 or m_1, ..., p_k or m_k) in S iff (p_1
or m_1 + 1 ,...  p_k or m_k + 1) in S

It is obvious that for k = 2 and n = 1 this is the same as the High
School Definition of negatively stable above.

We repeat the Lead Statement retitled.

NEGATIVELY STABLE MAXIMAL EMULATOR.  NSME. Every subset of Q[-n,n]^k
has a negatively stable maximal emulator.

THEOREM. NSME is provably equivalent to Con(SRP) over WKL0.

This is precisely what is intended to be fully proved in the upcoming
Gent Lectures in September.

Before we continue, here are some important remarks about NMSE.

RCA0 proves that every subset of Q[-n,n]^k has a finite subset with
the same emulators, and therefore the same maximal emulators. So we
can equivalently rewrite NSME as

NSME/1. Every finite subset of Q[-n,n]^k has a negatively stable
maximal emulator.

In this form, we see that NSME is provably equivalent to a statement
asserting of an effective sequence of sentences in first order
predicate calculus with equality, that they all have a countable
model. Then using WKL0, by Goedel's Completeness Theorem, NSME is
implicitly Pi01. I.e., there is a Pi01 sentence phi such that WKL0
proves that NSME is equivalent to phi.

We also get the equivalence over ACA0 of NSME with

NSME/2. Every finite subset of Q[-n,n]^k has a delta02 negatively
stable maximal emulator.

and this is a purely arithmetic sentence.

Moreover, RCA0 proves that every subset of Q[-n,n]^k has a finite
subset with at most f(k) elements, with the same emulators. Here f(k)
can be chosen to be roughly exponential in k. This leads to a further
variant of NSME, by replacing "finite" by "<=f(k) element"..

At the essence of NSME, we find that there are four important
parameters that beg for investigation.

k = dimension
n = endpoint
r = size
d = degree

k and n arise with Q[-n,n]^k. Really only 0,...,n have a role and that
there is a negative left endpoint. I use -n as the left endpoint only
for elegant symmetry.

r is the bound on the cardinality of the given subset of Q[-n,n]^k.

The degree d is in connection with the emulators. Emulators are the
same as the 2-emulators according to the following definition:

DEFINITION 5. S is a d-emulator of E containedin Q[-n,n]^k if and only
if S containedin Q[-n,n]^k and the concatenation of any d elements of
S is order equivalent to the concatenation of  some d elements of E. S
is a maximal d-emulator of E containedin Q[-n,n]^k if and only if S is
a d-emulator of E containedin Q[-n,n]^k which is not a proper subset
of any d-emulator of E containedin Q[-n,n]^k.

We now have the four parameter form of NSME.

NSME. Every at most r element subset of Q[-n,n]^k has a negatively
stable maximal d-emulator.

Let's now get clear what is quantified and what is fixed.

NSME(dim/k,end/n,size/r,deg/d) with k,n,r,d particular positive integers, means

*every at most r element subset of Q[-n,n]^k has a negatively stable
maximal d-emulator*

We are allowed to leave off some of the /i, meaning we are quantifying
instead of fixing. E.g., NMSE(dim/3,end,size,deg/3) means

*Every finite subset of Q[-n,n]^3 has a negatively stable maximal 3-emulator.*

We have proved the following using a bit more than Z_2.

THEOREM. NSME(dim/2,end,size,deg).

I think it likely that this above cannot be proved in Z_2. Haven't
really tried this reversal.

The prospects for proving strength are not good if we use small size
r. However, there really seems to be an interesting intricate subject
well within ZFC with small size r. In fact,

HIGH SCHOOL ThEOREM. NSME(dim/2,end/1,size/3,deg/2). With recursive.
Proof in RCA0.

This proof is at a perfect level for gifted high school. All very
explicitly combinatorial with very elementary not really trivial
constructions, and a lot of bookkeeping.

Here "with recursive" means that the negatively stable maximal
emulator is required to be recursive. We have refuted recursiveness
for NSME(dim,end,size,deg).

A goal is to show that NSME(dim/3,end/2,size,deg/2) is not provable in
ZFC. However, my first goal is to get a complete manuscript showing

THEOREM. NSME(dim,end,size,deg/2) and NSME(dim,end,size,deg) are
provably equivalent to Con(SRP) over WKL0.

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

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 939th 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
936: Stable Maximality/Tangible Incompleteness/2  6/4/22  11:31PM
937: Logic of Real Numbers/1  6/22/22  7:49AM
938: Logic of Real Functions/1 7/9/22  2:42AM

Harvey Friedman