[FOM] 823: Tangible Incompleteness/2

Harvey Friedman hmflogic at gmail.com
Tue Jul 17 22:54:29 EDT 2018 

NEW MANUSCRIPT AT
http://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
   #106  July 14c, 2018
also #108 is coming shortly! please look for it!!

Before I begin, let me mention the typo in
https://cs.nyu.edu/pipermail/fom/2018-July/021104.html   At one spot I
wrote 'strongly stable" when I meant "fully stable".

Even though my main effort right now is putting together the promised
reversals of MES as promised, it looks like I
have got my hands on some very important additions to the story.

I am putting together manuscript #108 with proofs of what I claim
here, except for the reversals, which are also underway.

THERE IS A BREAKTHROUGH CLAIMED HERE IN SECTION 4. Thus I have
succeeded in getting a complete understanding of equivalence relation
invariance in

0) maximal emulators, maximal duplicators, maximal cliques

in the context of rationals with only < and "being a positive integer".

(0) is clearly firmly and irrevocably embedded in the very fabric of
mathematics.

This complete understanding cannot be established in ZFC, but it can
be established in SRP+.

1. Move from Q[0,k]^k to Q[0,n]^k.
2. New Default Stable.
3. Four Equivalence Relations.
4. Rudimentary/Z+ EQR Use.
5. Rudimentary/Z+ REL Use.
not here
6. Rudimentary/Z+,+1^Z+ EQR Use.
not here
7. Rudimentary/Z+,+1^Z+ REL Use.
not here

1. MOVE FROM Q[0,k]^k TO Q[0,n]^k

Recall our lead trio:

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

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

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

For a number of reasons, we are making the move from Q[0,k]^k to the
more general Q[0,n]^k with an eye toward greater flexibility,
especially for the future. For example, we will want to find very
small k such that MES is independent of ZFC for k. We might find an
even smaller k if we allow n > k. Or we might find an n < k, with the
same k, and so forth. Also the theory of Rudimentary Equivalence
Relations discussed in section 5 is much more naturally applied after
the move from the Q[0,k]^k to the Q[0,n]^k,

2. NEW DEFAULT STABLE

The new lead statements of Emulation Theory now read

MAXIMAL EMULATOR 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.

There is no change in emulators, duplicators, order invariant graphs,
cliques, and maximality, as we change from Q[0,k]^k to Q[0,n]^k.

We now present the default notion of stability used in the official
MES, MDS, MCS above.

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 condition can be read unambiguously in light of our longstanding
convention that occurs in all my manuscripts, that p,q with or without
subscripts range over the rationals, unless indicated otherwise, and
i,j,k,n,m,r,s,t with or without subscripts range over the positive
integers, unless indicated otherwise.

1) is obviously a natural strengthening of my original

2) 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, this is "the one that got away".

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

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

3. FOUR EQUIVALENCE RELATIONS USED

Note that our default stable 1) 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:

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 1) is the right choice for default stable,
given the widely diverse audiences for Goedelian Incompleteness, once
we move to more systematic perspectives, like complete invariance,
there are better alternatives. We will return to default stable and
default lift in section 7.

It is most natural to focus on invariance with respect to equivalence
relations here. We now introduce four particularly natural equivalence
relations.

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 sequence by strictly greater (lower) positive
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 use these four in MES, MDS, MCS, arriving at, for example,

MES[full upZ+]. Every finite subset of Q[0,n]^k has a full up
invariant maximal emulator.

DEFINITION 2.4. 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 an R
invariant maximal emulator (duplicator). R is MC usable if and only if
for every order invariant graph on every Q[0,n]^k has an R invariant
maximal clique.

THEOREM 3.1. All twelve statement:"upZ+, downZ+, full upZ+, full
downZ+ on Q^k is ME, MD, MC usable" are equivalent to Con(SRP) over
WKL_0.

4. RUDIMENTARY/Z  EQR USE.

Note that our four equivalence relations upZ+, downZ+, full upZ+, full
downZ+ on each Q^k involves only < and "being a positive integer".

DEFINITION 4.1. A containedin Q^r is rudimentary/Z+,< if and only if A
is parameterless quantifier free definable over (Q,<,Z+).

RUDIMENTARY(Z+ ME USE. RMEU(Z+). A rudimentary/Z+ equivalence relation
on Q^k is ME usable if and only if it is included in full upZ+ or
included in full downZ+.

THEOREM 4.1. RMEU(Z+) is equivalent to Con(SRP) over WKL_0.

This also characterizations full upZ+ and full downZ+ as the two
maximum rudimentary/Z+ equivalence relations that can be used in ME.

************************************************************************
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 823rd 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

Harvey Friedman

More information about the FOM mailing list