Can you disprove this counterexample to the diagonal lemma?

65 Views Asked by At

I was looking at the Diagonal Lemma or Fix point theorem which states in every Theory $T$ every formula with one variable $ B(n) $ has a fix point: $T \vdash G \leftrightarrow B(\# G)$. Where $\#F$ denotes the Gödel number for $F$ and $n$ is a natural number.

https://plato.stanford.edu/entries/goedel-incompleteness/sup2.html

https://en.wikipedia.org/wiki/Diagonal_lemma

Let $F=\%N$ denote the the inverse of $N=\#F$ (taking a number $N$ from the set of Gödel numbers of syntactically correct formulas and return said formula)

It is easy to see that the formula $A(N) := \lnot \%N$ cannot have a fixpoint, since $A(\#D) = \lnot D \leftrightarrow D$ is a contradiction for all statements $D$.

What part about this counterexample is wrong?

1

There are 1 best solutions below

0
On

The "formula" $\neg\%N$ is not actually a formula in the relevant language, so the diagonal lemma doesn't apply to it. In fact, you've basically written an impossibility proof: that there's no way, inside the language itself, to "unpack" a coded sentence so that it can be operated on via Booleans etc. This turns into Tarski's undefinability theorem.