[FOM] 824: Tangible Incompleteness/3

Wed Jul 18 23:13:45 EDT 2018

THIS POSTING IS SELF CONTAINED

Section 4 of https://cs.nyu.edu/pipermail/fom/2018-July/021107.html
was not done right.

The actual characterization given there of the usable rudimentary/Z+
ME usable equivalence relations is not correct as it stands, and there
are some technical issues I haven't resolved yet.

It appears that I can avoid certain unresolved technical issues by
using symmetric order invariant/Z instead of rudimentary/Z+.

Below supersedes
https://cs.nyu.edu/pipermail/fom/2018-July/021107.html and is self
contained. We are now preparing a full manuscript 108 on our
Downloadable website page.

1. Default Stable.
2. Embeddings.
3. Symmetric Order Invariant/Z.
4. Future.

1. DEFAULT STABLE

We still adhere to our convention that p,q with or without subscripts
stand for rationals, unless otherwise indicated, and that
i,j,k,n,m,r,s,t, with or without subscripts stand for positive
integers, unless otherwise indicated.

The lead statements in Emulation Theory are as follows.

MAXIMAL EMULATION STABILITY. MES. Every finite subset of Q[0,n]^k has
a stable maximal emulator.

MAXIMAL DUPLICATOR STABILITY. MDS. Every finite subset of Q[0,n]^k has
a stable maximal duplicator.

MAXIMAL CLIQUE STABILITY. MCS. Every order invariant graph on Q[0,n]^k
has a stable maximal clique.

Recall that S is an emulator of E containedin Q[0,n]^k if and only if
every element of S^2 is order equivalent to an element of E^2. S is a
duplicator of E containedin Q[1,n]^k if and only if every element of
S^2 is order equivalent to an element of E^2 and vice versa.

Here is the default stable:

DEFINITION 1.1. S containedin Q[0,n]^k is stable if and only if for all
p < i_1,...,i_k-1 < n, (p,i_1,...,i_k-1) in S iff (p,i_1 + 1,...,i_k-1
+ 1) in S.

This is a natural strengthening of my original

*) S containedin Q[0,k]^k is stable if and only if for all
p < 1, (p,1,...,k-1) in S iff (p,2,...,k) in S

that i originally claimed was enough to get independence from ZFC. So
far, *) is "the one that got away".

There is a long story about how I can weaken the default stable and
get it much closer
to *), but this ongoing story is for another time.

THEOREM 1.1. MES, MDS, MCS with the default stable are equivalent
to Con(SRP) over WKL_0.

2. FOUR EQUIVALENCE RELATIONS

Note that our default stable asserts that S is completely invariant
with respect to a relation on Q[0,n]^k. Actually, it proves best to
think of the Q^k as the master spaces, and restrict down to the
Q[0,n]^k as subspaces. Here is the relation associated with the default stable:

DEFINITiON 2.1. Let x,y in Q^k. y is the default lift of x if and only if
i. x_1 = y_1 < x_2,...,x_k.
ii. for all 2 <= i <= k, y_i = x_i + 1.
iii. x_2,...,x_k in Z.

Thus we can rewrite

MAXIMAL EMULATOR STABILITY. MES. Every finite subset of Q[0,n]^k has a
completely default lift invariant maximal emulator.

Although we believe that we have the (or a) right choice for default stable,
given the widely diverse audiences for Goedel Incompleteness, once
we move to more systematic perspectives, like complete invariance,
it is best to move to equivalence relations.

We now make the following two definitions in preparation for a
systematic theory.

DEFINITION 2.1. Let R be an equivalence relation on Q^k. R is ME (MD)
usable if and only if every finite subset of every Q[0,n]^k has a completely R
invariant maximal emulator (duplicator). R is MC usable if and only if
every order invariant graph on every Q[0,n]^k has a completely R invariant
maximal clique.

We now introduce four natural equivalence relations on Q^k.

DEFINITION 2.2. x,y in Q^k are upZ (downZ) equivalent if and only if
x,y are increasing (<=), (decreasing (>=)), repetition equivalent, and
extend a common nonempty sequence by strictly greater (lower)
integers.

DEFINITION 2.3. x,y in Q^k are full upZ (full downZ) equivalent if
and only if x,y have a common permutation that is upZ (downZ)
equivalent.

We can incorporate these four equivalence relations into MES, MDS,
MCS, arriving at these four statements below for just MES, for a total
of twelve statements. (Invariance and complete invariance with respect
to equivalence relations are the same).

upZ is MES usable.
downZ is MES usable.
full upZ is MES usable.
full downZ is MES usable.

Note that the first two (last two) of these statements are symmetric
to each other.

THEOREM 2.1. All twelve statements are equivalent to Con(SRP) over WKL_0.

THEOREM 2.2. If we eliminate "nonempty" in the definitions of upZ,
downZ, then all twelve statements are refutable in RCA_0 (for k >= 2).

3. SYMMETRIC ORDER INVARiANT/Z

DEFINITION 3.1. An equivalence relation R on Q^k is symmetric if and
only if for all for all x,y in Q^k and coordinate permutations pi, x R
y iff pi(x) R pi(y).

Note that full upZ and full downZ are the least symmetric equivalence
relations containing upZ and downZ, respectively.

Also note that our four equivalence relations upZ, downZ, full upZ, full
downZ on each Q^k involve only < and "being an integer". The following
strengthening of order equivalence nicely reflects this situation.

DEFINITION 3.2. x,y in Q^k are order equivalent/Z if and only if x,y
are order equivalent and for all 1 <= i <= k, x_i in Z iff y_i in Z. X
containedin Q^r is order invariant/Z if and only if for all order
equivalent/Z x,y in Q^k, x in X iff y in X.

THEOREM 3.1. upZ, downZ, full upZ, full downZ are order invariant/Z
equivalence relations on the Q^k. Full upZ and full downZ are
symmetric order invariant/Z equivalence relations on the Q^k.

We now want to determine exactly what the ME, MD, MC usable symmetric
order invariant/Z equivalence relations on Q^k are.

SYMMETRIC ORDER INVARIANT/Z ME USE. SOIZMEU. A symmetric order
invariant/Z equivalence relation on Q^k is ME usable if and only if it
is contained in full upZ, contained in full downZ, or contained in the
Z-diagonal {((p,...,p),(q,...,q)): p,q in Z or p = q}.

THEOREM 3.1. SOIZMEU is equivalent to Con(SRP) over WKL_0. RCA_0
proves that all ME usable symmetric order invariant/Z equivalence
relations are among those listed in SOIZMEU.

Analogous results hold for MD and MC.

Thus we have TEMPLATED OUT stability and usability, and are left only
with Maximal Emulators, Maximal Duplicators, or Maximal cliques in
order invariant graphs, which are permanently embedded in the fabric
of elementary mathematics.

4. FUTURE

The obvious future is to expand the family of symmetric order
invariant/Z equivalence relations systematically, and obtain exact
determinations of use as in Theorem 3.1. There is much to do with
order invariant/Z, but the original default stable is not order
invariant/Z. Instead it is order invariant/Z,+1. Highly ambitious
along these lines is to work with order invariant/Z,+,-,0,1 relations
(not necessarily equivalence relations, and invariance instead of
complete invariance) and to drop symmetric. Then there is the issue of
determining the logical status of the statements arising in these
ways.

There is the issue of cutting down the size of k,n in Q[0,n]^k.

There are many more issues in many more directions.

************************************************************************
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 824th 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

Harvey Friedman