Symbolic Logic; April 25
Selmer Bringsjord
Gödel numbering scheme
The Diagonalization of a Formula
Let A be an expression having gödel number n. Then define
to be the expression n. The diagonalization
of A is the expression
Then if A is a formula in L, the language of arithmetic, that contains just the variable x free, the diagonalization of A will be a sentence that ``says that" A is true of its own gödel number.
Lemma I
There is a recursive function, diag, which works like this. If n is the gödel number of an expression A, diag(n) is the gödel number of the diagonalization of A.