[FOM] 809: Goedel's Second Reworked/1

[Harvey Friedman]

I am planning some posts with this title, one or more presenting a
NEWLY SIMPLIFIED PROOF of GSIT, and one or more presenting a NEWLY
SIMPLIFIED STATEMENT of GSIT.

This post concerns the NEWLY SIMPLIFIED PROOF OF GSIT.

There has been a major advance in SIMPLIFIED PROOFS OF GSIT (Goedel's
second incompleteness theorem). My former best can be seen at
https://cs.nyu.edu/pipermail/fom/2017-December/020729.html

We now see how to extend ideas from there

TO NOW PUSH THE DIAGONALIZATION MUCH FURTHER AWAY FROM THE PROOF AND
INVISIBLY HIDDEN FAR AWAY IN THE USUAL PROOF OF A WELL KNOWN
STRUCTURAL FACT ABOUT TURING MACHINES.

THUS, if you accept a well known interesting structural fact in
recursion theory, there is ABSOLUTELY NO DIAGONALIZATION INVOLVED,
ABSOLUTELY NO STRANGE CONSTRUCTION, ABSOLUTELY NO DIAGONAL
CONSTRUCTION, and indeed the argument IS PLEASANTLY STRAIGHTFORWARD.

Here is the structural fact, stated simply and then more sharply. The
simple and the sharp forms have the SAME WELL KNOWN PROOF.

MY PROOF OF GSIT  DEFINITELY REQUIRES THE SHARPER FORM, and I have NOT
been able to get away with the plain vanilla form of the structural
fact.

STRUCTURAL FACT. 1. 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.)
2. 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.)

Proof: The standard proof of 1) uses A = {e: the e-th TM halts at e}.
This standard proof also establishes 2) without change. QED

PROOF OF GSIT. Fix an r.e. theory T containing a very weak system of
arithmetic, which proves Con(T). We will show that T is inconsistent.

Let A be from the Structural Fact. Apply the Structural Fact (sharp
form) to B = [n: T refutes n in A}. Fix n such that

n* in A iff n* in B

is low level provable. In particular

T proves (n* in A iff n* in B)

I.e.,

1) T proves (n* in A and n* in B) or (n* notin A and n* notin B)

Now T refutes the first disjunct in the formula in 1). To see this, we
argue in T (which proves Con(T)) as follows.

Assume n* in A and n* in B
T proves n* in A
T proves n* notin A
T is inconsistent
T is consistent
contradiction

Hence T proves the second disjunct in the formula in 1). In
particular, T proves n* notin A, and so n* in B and T proves n* in B.
But T proves n* notin B, and so T is inconsistent. QED

COMMENT: There is a particular construction of a set needed in the
proof of GSIT: namely B = [n: T refutes n in A}. However look at how
simple and totally natural and transparent that construction of B is.

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

Harvey Friedman