1

I was watching a video: https://youtu.be/HeQX2HjkcNo?t=1171 and had a quesion on the incompleteness proof.

In the video, he introduces us to the statement: "There is no proof for the statement with Godel number $g$"

Then he says that the trick is that the Godel number of that statement is $g$. My question is how can you be sure that such a number $g$ exists? Since the conjecture itself has $g$ in it, wouldn't the Godel number be dependent on $g$? More specifically, I believe that the Godel number of any statement that has a number $x$ is greater than $x$. Is that not always the case?

B2VSi
  • 1,005
  • 2
    A statement that explicitly contains the numeral for $x$ (e.g. $SS\dots SS0$ with $x$ occurrences of the "successor" symbol $S$) will indeed have Gödel number bigger than $x$. But a statement can contain a description of how to compute $x$, and then its Gödel number can be much smaller. Part of Gödel's discovery was a method for producing a statement that contains a description of how to compute its own Gödel number. – Andreas Blass Jun 04 '23 at 18:17
  • Ah, thank you!! That is interesting – B2VSi Jun 04 '23 at 18:32
  • 5
    I believe this is fundamentally a duplicate of this question. That said, this is a very good and natural question to have about the incompleteness theorem, and I don't know why it got downvoted. – Noah Schweber Jun 04 '23 at 20:47
  • See also this MO thread, about pathological Godel numbering mechanisms which do allow literally-the-same fixed points! – Noah Schweber Jun 04 '23 at 20:57

0 Answers0