[FOM] 812: Goedel's Second Reworked/3

[Harvey Friedman]

This concerns the Structural Fact. Recall from my Goedel's Second
Reworked/2, https://cs.nyu.edu/pipermail/fom/2018-May/021003.html

STRUCTURAL FACT. 1. There is an r.e. set whose complement is not r.e.
2. There is an r.e. set A such that every r.e. set B somewhere agrees
with A. (I.e., there exists n such that n in A iff n
in B.)
3. There is an r.e. set A such that every r.e. set B somewhere low
level provably agrees with A. (I.e., there exists n such that a very
weak system of arithmetic (fixed in advance, like EFA or much weaker)
proves n* in A iff n* in B.)

There is something PARTICULARLY FRIENDLY and INTERESTING about the
"right" proof of Structural Fact.

In mathematics generally, if you want to prove the existence of an
object which has some relationship to all objects of a certain kind -
I think a rather common occurrence stated in this generality - you
generally want to try to build that object step by step so that it has
the desired relationship with all objects of that certain kind.

So when looked at in this way, we could make a distinction between an
"in your face do the obvious construction" and "a diagonal argument".

In the case of the Structural Fact 2) -- obviously 1) and 2) are
trivially equivalent -- we have the following OBVIOUSLY SUPERFRIENDLY
construction.

Let B_1,B_2,... be an r.e. enumeration of the r.e. sets. (The whole
subject of recursion theory and in some sense the whole of modern
computing technology, depends on this, and this is not a diagonal
argument).

Generate A so that

A agrees with B_1 at your favorite place
A agrees with B_2 at you favorite new place
A agrees with B_3 at your favorite new new place
A agrees with B_4 at your favorite new new new place
...

or, in order to be more mathematically neat, construct A so that

A agrees with B_1 at 1
A agrees with B_2 at 2
A agrees with B_3 at 3
A agrees with B_4 at 4
...

I.e., have A generate 1 like B_1 generates 1, A generate 2 like B_2
generates 2, and so forth, with obvious TIME SHARING, a very important
interesting idea theoretically and practically. CHURCH'S THESIS NICELY
APPLIED in a very interesting (well known) way!!

For 3, just use this A. Obviously it provably works.

Now this is so friendly and essentially FORCED ON YOU mathematically,
that it should be distinguished from any MYSTERIOUS diagonal arguments
- like self reference.

In fact, it is so interesting, and so forced on you, and so
uncluttered, that the GSIT student doesn't feel anything strange, and
should be unfazed and very happy at this point.

The rest of my proof of GSIT is also totally friendly, and has not
even the slightest indication of any diagonal argument.

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

Harvey Friedman