Godel diagonalization lemma

martdowd at aol.com martdowd at aol.com
Tue Oct 12 14:12:12 EDT 2021


I'm working on trying to bridge the gap in my proof of P $\neq$ NP.
I've written up a proof of the Godel diagonalization lemma to work from.
It turned out so well I thought I'ld post it.  $\LA$ is my name for PV.

Martin Dowd

\def\LA{{\mathcal L}\text{A}}

A formula of $\LA$ is a string of symbols.
It can be coded as an integer.
The notation $y=\lc F\rc$ will be used to indicate that
 the value $y$ is the code for $F$.
Let $F$ be a formula with variables $\vec x,y$.
Godel diagonalization constructs a closed term $D$,
 whose value is $\lc F\frac{D}{y}\rc$.
Thus, $F\frac{D}{y}$, which has variables $\vec x$, refers to itself.

$\Sub_y(y,z)$ is $\lc F\frac{T}{y}$ when $y=\lc F\rc$ and $z=\lc T\rc$.
$Num(y)$ is $\lc N_y\rc$ where $N_y$ is the numeral for the value $y$.
There are $\LA$ terms for these functions.

Suppose $F$ is a formula with variables $\vec x,y$.
Let $G$ be $F\frac{\Sub(y,\Num(y))}{y}$; it has variables $\vec x,y$.
Let $H$ be $G\frac{N_{\lc G\rc}}{y}$; it has variables $\vec x$.
Then $H$ is $F\frac{\Sub(N_{\lc G\rc},\Num(N_{\lc G\rc}))}{y}$,
 i.e., $F\frac{D}{y}$
 where $D$ is $\Sub(N_{\lc G\rc},\Num(N_{\lc G\rc}))$.

The value of $D$ is $\lc G\frac {N_G}{y}\rc$, i.e., $\lc H\rc$.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211012/8ec5bec5/attachment-0001.html>

More information about the FOM mailing list