In his epochal 1931 paper on the incompleteness theorems Gödel wrote, regarding his undecidable statement, saying, in effect, “I am unprovable,”

The tendency of this footnote might be that if one tried to express the statement directly, there might indeed be a faulty circularity. In my own paper, “Outline of a Theory of Truth,” I expressed some doubt about this tendency, and stated that the Gödel theorem could be proved using ‘direct’ self-reference. To quote this paper,

As I say in footnote 6, there are several ways of obtaining the Gödel theorem using direct self-reference, analogously to ‘Jack is short’. Note that, as I say in footnote 5, I am not claiming that this technique could be used to obtain self-referential propositions. Perhaps this is what Gödel had in mind in his own footnote. Let us look at how Gödel’s first incompleteness theorem is to be done these ways.

One way, observed independently by Raymond Smullyan, is to use a nonstandard Gödel numbering where a formula can contain a numeral designating its own Gödel number.Footnote ¹ This is clearly impossible under the usual Gödel prime power numbering, or various other variants. That this should not happen might be a natural restriction, since a Gödel number might be thought to correspond with a formula as a composite object, and this might be thought to preclude a formula from containing a numeral designating its own Gödel number.

Nevertheless we propose a nonstandard Gödel numbering allowing a statement to contain a numeral designating its own Gödel number. We can proceed as follows. Let $x_{1}$ be a fixed variable. Let $A_{1}(x_{1})$ , $A_{2}(x_{1})$ , …be an enumeration of all those formulae that contain at most $x_{1}$ free (Gödel’s class signs). We assume that the language of the system studied contains, either directly or by virtue of interpretation, the language of arithmetic. Numerals can be assumed to be terms $0$ followed by (or preceded by) finitely many successor symbols (allowing none). We use $0^{(n)}$ for $0$ with n successor symbols; $n=0$ is allowed, as I said. $0^{(n)}$ denotes the number n.

Let the ‘original’ Gödel numbering be Gödel’s own prime power product numbering, except that the smallest prime used is $3$ , so that Gödel numbers are always odd. In the ‘new’ numbering, all Gödel numbers coincide with the ‘original’, except that for each n, the formula

$$ \begin{align*} (\exists x_{1})(x_{1}=0^{(2k_{n})}\wedge A_{n}(x_{1})), \end{align*} $$

gets the Gödel number $2k_{n}$ , where $k_{n}$ is the original Gödel number of $(\exists x_{1})(x_{1}=0^{(n)}\wedge A_{n}(x_{1}))$ . The ‘new’ numbering allows a formula to contain a numeral designating its Gödel number, and in that sense it is a self-referential Gödel numbering.

In this self-referential Gödel numbering, every formula $A_{n}(x_{1})$ has an ‘instance’ $(\exists x_{1})(x_{1}=0^{(2k_{n})}\wedge A_{n}(x_{1}))$ asserting that its own Gödel number satisfies $A_{n}(x_{1})$ . The Gödel incompleteness theorem is the special case where $A_{n}(x_{1})$ is unprovability in the system.

The ‘new’ Gödel number is in effective $1-1$ correspondence with the old one, where the inverse function is also effective. The complexity of a property in the arithmetical hierarchy ( $\Sigma _{1}^{0}, \Pi _{1}^{0}$ , etc.) does not change when the ‘new’ Gödel numbers replace the old.Footnote ²

Much more natural, in my opinion, for getting ‘direct’ self-reference, is the use of added constants.Footnote ⁴ Once again, let $A_{1}(x_{1}), A_{2}(x_{1}), \ldots , A_{i}(x_{1})$ be an enumeration of all those formulae of the language L containing at most the variable $x_{1}$ free. Let $a_{1}, a_{2}, \ldots $ be a denumerable list of constants, none of which are in the original language L. Give Gödel numbers to the formulae of the extended language in a conventional way. Now add to the axioms of the original system S, an infinite set of axioms $a_{i}=0^{(n_{i})}$ , where $n_{i}$ is the Gödel number of $A_{i}(a_{i})$ . The resulting system is $S^{\prime }$ . Pretty clearly $S^{\prime }$ is a conservative extension of S. It simply extends S by adding an infinite set of constants with specific numerical values—new names for particular numbers. Every proof in $S^{\prime }$ becomes a proof in S if each constant is replaced by the corresponding numeral.

Now, for the Gödel (first incompleteness) theorem, consider the predicate (in the original language, without the extra constants) that says that $x_{1}$ is the Gödel number of a formula unprovable in the extended system $S^{\prime }$ . Call this $\operatorname {\mathrm {\sim }}\text {Thm}_{S^{\prime }}(x_{1})$ . This is a $\Pi _{1}^{0}$ predicate and is a formula $A_{i}(x_{1})$ for some i. In our construction, there is a constant $a_{i}$ of $S^{\prime }$ such that $a_{i}=0^{(n_{i})}$ is an axiom of $S^{\prime }$ , where $n_{i}$ is the Gödel number of $A_{i}(a_{i})$ . Then it is easily shown, in the usual way, that $A_{i}(a_{i})$ is unprovable in $S^{\prime }$ if $S^{\prime }$ is consistent, and that $\operatorname {\mathrm {\sim }} A_{i}(a_{i})$ is unprovable in $S^{\prime }$ if $S^{\prime }$ is $\omega $ -consistent (or even $1$ -consistent). Given that $S^{\prime }$ is a conservative extension of S, the same things must be true of $A_{i}(0^{(n_{i})})$ in the original system S as well.

The particular case of unprovability is just one example. For any definable property we obviously can use this construction to formulate a statement that ‘says of itself’ that it has that property (the ‘self-reference lemma’).

A more delicate construction uses only a single constant a, and a single extra axiom, in defining the system $S^{*}$ extending S. It will have only one extra axiom, which will be called (*). In the case of Gödel’s first incompleteness theorem, we wish to construct a statement saying that it itself is unprovable. So given the constant a, we consider the single formula standing for the statement

(*) $$ \begin{align} & a \mbox{ is unprovable in the system }S^{*}, \mbox{ which is } S \mbox{ extended} \nonumber\\ & \mbox{by adding } \ulcorner a=0^{(a)}\urcorner \mbox{ as a single axiom} \end{align} $$

(Of course this is to be written out symbolically.) The constant a occurs in (*) only as explicitly shown. Note that in (*), the constant a is both used and mentioned. In a standard Gödel numbering of the extended language, (*) has a particular Gödel number. Say it is n. Then let the extended system $S^{*}$ be axiomatized by adding $a=0^{(n)}$ as an axiom.

Given this extra axiom, $a=0^{(n)}$ , note that (*) will say that it itself (i.e., its Gödel number) is unprovable in the system $S^{*}$ itself. Now we can once again deduce that (*) is unprovable in $S^{*}$ if $S^{*}$ is consistent, its negation is unprovable in $S^{*}$ if $S^{*}$ is $\omega $ -consistent, etc. Also once again $S^{*}$ is a conservative extension of S, so that any proof in S is valid in $S^{*}$ iff it was valid in S, just as in the previous argument with an infinity of constants. And once again, this allows us to transfer the result to the original system S. Clearly also the argument extends to results about any definable $A(x_{1})$ in place of unprovability (the self-reference lemma).