855: Lower Equivalent and Stable Maximal Sets/1

[Harvey Friedman]

The statements in 854 are very natural generalizations of what we have
in this 855, and so 854 is not to be discarded.

1. PURELY ORDER ThEORETtIC

DEFINITION 1.1., We use J for any rational interval, which is a an
interval of rationals with endpoints from Q U {-infinity,inifnity}}.
Let E containedin J^k A square in E is a subset A^2 containedin E. A
maximal square in E containedin J^k is a square in E contianedin J^k
which is not a proper subset of any square in E containedin J^k.

Note that if k is odd then the only square and maximal square in E
containedin J^k is the empty set.

DEFINITION 1.2. Let x,y in J^k and S containedin J^k. S is x,y
equivalent if and only if x in S iff y in S.

THEOREM 1.1.. Let x,y in J^k be order equivalent, J open. Every order
invariant subset of J^k has an x,y equivalent maximal square.

Theorem 1.1 is by an easy use of Ramsey's Theorem. it is provable in RCA_0/

THEOREM 1.2. Let x,y in J^k be order equivalent, J not closed. Every
order invariant subset of J^k has an x,y equivalent maximal square.

Theorem 1.2 is by a harder use of Ramsey's Theorem. It is provable in
RCA_0 + for all n, the n-th Turing jump exists.

DEFINITION 1.3. Let x,y in J^k and S containedin J^k. S is lower x,y
equivalent if and only if for all x',y' resulting from replacing one
or more x_i,y_i with various p,p < min(xy), x' in S iff y' in S. S
 is relatively lower x,y equivalent if and only if for all x',y'
resulting from replacing one or more x_i,y_i with various p,p strictly
lower than all remaining x_i,y_i, then x' in S iff y' in S.

EXAMPLE OF LOWER REPLACEMENT: Use J^4 = Q[0,1]^4 and (2/3,1,1/3,2) R
(3/4,7/8,1/4,3), where R has other pairs. We can replace the second
and third coordinates on both sides by 1/8 and 1/9 respectively,
obtaining (2/3,1/8,1/9,2), (3/4,1/8,1/9,3).

EXAMPLE OF RELATIVELY LOWER REPLACEMENT: In the above, we can replace the second
and third coordinates on both sides by 1/3 and 1/4 respectively,
obtaining (2/3,1/3,1/4,2), (3/4,1/3,1/4,3).

PROPOSITION 1.3. Let x,y in J^k be order equivalent. Every order
invariant subset of J^k has a lower x,y equivalent maximal square.

PROPOSITION 1.4. Let x,y in J^k be order equivalent. Every order
invariant subset of J^k has a relatively lower x,y equivalent maximal
square.

THEOREM 1.5. Propositions 1.3, 1.4 are provably equivalent to Con(SRP)
over WKL_0 where the implication to Con(SRP) is provable in RCA_0.

We can use any of our ten categories for this in addition to squares.

These Propositions are implicitly Pi01 via the Goedel Completeness Theorem.

2. ORDER THEORETIC WITH N DISTINGUISHED

DEFINITION 2.1. S containedin J^k is N stable if and only if for all
order equivalent x,y in N^k, x in S iff y in S.

THEOREM 2.1.. Every order invariant subset of open J^k has an N stable
maximal square.

Theorem 2.1 is by an easy use of Ramsey's Theorem. It is provable in RCA_0.

THEOREM 2.2. Every order invariant subset of not closed J^k has an N
stable maximal square.

Theorem 2.2 is by a harder use of Ramsey's Theorem. It is provable in
RCA_0 + for all n, the n-th Turing jump exists.

DEFINITION 2.2. Let S containedin J^k. S is lower N lower stable if
and only if for all order equivalent x,y in (J intersect N)^k, if
x',y' in J^k resut from replacing one or more x_i,y_i with various p,p
< min(xy), x' in S iff y' in S. S  is relatively N lower stable if
and only if for all order equivalent x,y in (J intersect N)^k, if
x',y' in J^k result from replacing one or more x_i,y_i with various
p,p strictly lower than all remaining x_i,y_i, then x' in S iff y'
in S.

THEOREM 2.3.. Every order invariant subset of J^k has an N lower
stable maximal square.

THEOREM 2.4.. Every order invariant subset of J^k has a relatively N
lower stable maximal square.

THEOREM 2.5. Propositions 2.3, 2.4 are provably equivalent to Con(SRP)
over WKL_0 where the implication to Con(SRP) is provable in RCA_0.

We can use any of our ten categories for this in addition to squares.

3. IN THE INTEGERS

We now move from Q to Z to give explicitly Pi02 and Pi01 Tangible
Incompletenss. We use normal interval notation in the integers. We
feature two of our ten categories - cliques in graphs. The squares
used in sections 1,2 are a bit more awkward to use here.

We work entirely in the finite spaces [-nr,nr]^k. We need to use the
approach in section 2.

DEFINITION 3.1. A clique extender of clique S in graph G on
[-nr,nr]^k is an x such that S U. {x} is a clique in G. A maximal
clique in graph G on
[-nr,nr]^k is a clique with no clique extender.

DEFINITION 3.2. S is a weakly maximal clique in graph G on [-nr,nr]^k
if and only if S is a clique in G where there is no nonempty set of
clique extenders R[S^k x {(0,r,2r,...,nr)}], where R containedin [-nr,nr]k^2 +
n + k is order invariant.

DEFINITION 3.3. S containedin [-nr,nr]^k is rN lower stable if and only if
for all order equivalent x,y in {0,r,...,nr}^k, if x',y' in [-nr,nr]^k
results from x,y by replacing one or more x_i,y_i by various p,p <
min(xy), then x' in S iff y' in S.

DEFINITION 3.4. S containedin [-nr,nr]^k is relatively rN lower stable
if and only if
for all order equivalent x,y in {0,r,...,nr}^k, if x',y' in [-nr,nr]^k
results from x,y by replacing one or more x_i,y_i by various p,p
strictly less than the remaining x_i,y_i, then x' in S iff y' in S.

INTEGER LOWER INVARIANT WEAKLY MAXIMAL CLIQUES/1. ILIWMC/1. Every
order invariant graph on [-nr,nr^]k, r >> k,n, has an rN lower
stable weakly maximal clique.

INTEGER RELATIVELY LOWER INVARIANT WEAKLY MAXIMAL CLIQUES/1. ILIWMC/1. Every
order invariant graph on [-nr,nr]^k, r >> k,n, has a relatively rN lower
stable weakly maximal clique.

INTEGER LOWER INVARIANT WEAKLY MAXIMAL CLIQUES/1. ILIWMC/2. Every
order invariant graph on [-nr,nr]^k, r > (8kn)!, has an rN lower
stable weakly maximal clique.

INTEGER RELATIVELY LOWER INVARIANT WEAKLY MAXIMAL CLIQUES/1. ILIWMC/2. Every
order invariant graph on [-nr,nr]^k, r > (8kn)!, has a relatively rN lower
stable weakly maximal clique.

THEOREM. All four of the above provably equivalent to Con(SRP) over EFA.

The above will work for square legs, cube legs, and emulators.

Obviously the last two are explicitly Pi01.

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

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 855th 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
853: Embedded Maximality (revisited)/1 5/3/20 10:19PM
854: Lower R Invariant Maximal Sets/1:

Harvey Friedman