In trying to understand Godel’s incompleteness theorem, I have come across an apparent paradox. There must be a mistake somewhere but I cannot find it and would be very grateful for anyone to point out where it lies. The paradox uses a typical Cantor diagonalization argument.
Given a relatively rich first order language such as Peano Arithmetic, finite operations such as deciding whether a number is the Godel number of a valid proof, can be captured by wffs in the language.
Specifically, my understanding of PA is that the following is true. Suppose I give a finite set of operations, each of which could be carried out by a Turing machine, and which take a numeral n as the input, and produce a wff as the output (I am not confining it to the case where the output is another numeral). Call this procedure P. So given any numeral n, the procedure gives a wff which could be written (in the metalanguage) as P(n). Then this procedure can be represented inside the language itself, captured by a wff φ(x) with just one free variable x, such that the outcome of the procedure on the number n as above is given by the sentence φ(n) where n is the numeral in the object language corresponding to n.
Now choose P as follows. Suppose given your n. List the wffs with just one free variable x in an enumerable sequence φ1(x), φ2(x) etc, which can certainly be done by listing such wffs in the order of their Godel numbers. Continue until you get to φn(x). Now substitute n for x in this, and form the sentence “not-φn(n)”.
This provides a method of mechanically writing down the sentence “not-φn(n)” for any n. There must therefore be a wff φ(x) which captures this mechanical process, that is, such that “φ(n)” is the sentence “not-φn(n)”.
But now the usual argument leads to a contradiction. For the wff φ must be one of the φk in the enumeration for some k, so the sentence φ(k) must be identical to the sentence φk(k), but it is also by definition the sentence not-φk(k).
The only point at which the argument can break down, as far as I can see, is the assumption that P can be captured by a wff. But that seems to go against the idea that everything finitely computable can be expressed within the language. Any ideas?