Damjan Bojadziev

Reconstructing diagonalization(s)

Yearbook of the Kurt Gödel Society 1989, pp.74-77, Wien 1990

Self-referential sentences of arithmetic can be constructed without presupposing the idea of diagonalization. Using some suggestive notation, a fairly general solution scheme can be set up: 
(n)    P(subst(beta(num(ß-1(x))),ß-1(x)))
                           |       /
                           | ß(n) /
                           |     /
                           |    /
          P(subst(beta(num(n)),n))
ß(x) is a primitive recursive function, n is the Gödel number of the formula above, n is the numeral of that number and the function num(x) maps a number to the Gödel number of its numeral. The function subst(x,y) describes, through Gödel numbers, substitutions of terms into formulas: if x is the number of a term, and y is the number of a formula (containing a free variable), the term subst(x,y) refers to the result of the corresponding substitution (for simplicity, the notation does not specify the variable). When the term ß(n), described by the term beta(num(n)), is substituted into the formula above, the resulting sentence refers to (the Gödel number of) the result of that very substitution, and thus to itself.

The special case in which ß(x) is linear covers diagonalization and simple generalizations of diagonalization, which can be described as diagonalization along other diagonals (other than the main one). For example:

diagonalization
ß(x) = ß-1(x) = x, beta(x) = x

sub-diagonalization (k diagonals down from the main one)
ß(x) = x + k, ß-1(x) = x - k,
beta(x) = sum(x,num(k))
The two substitutions involved in self-reference - the one described in the formula and the one performed on it - coincide only in (simple) diagonalization. When diagonalization is done along other diagonals or curves, the two substitutions are different, but they still cooperate in such a way that the resulting sentence describes the result of the very substitution which produced it. What is already present in the formula, combined with what is substituted into it, evaluates to a description of what that substitution produces.
If you have seen a reference to this paper, please leave a message.