diagonal lemma and the negation function

Question

Carnap's diagonal lemma asserts that for every computable formula f, accepting a natural number as argument and resolving to {false,true}, there exists a logic sentence s for which:

s $\leftrightarrow$ f($\ulcorner s\urcorner$)

With $\ulcorner s\urcorner$ the Gödel encoding for logic sentence s.

I have a problem with the example function f($\ulcorner s\urcorner$) = $\neg$s. It looks like according to Carnap's diagonal lemma, there exists a logic sentence s for which the following could hold:

s $\leftrightarrow$ $\neg$s

This is obviously, in one way or another, a wrong interpretation of what the lemma says or implies, but I cannot explain why it is wrong ... What's wrong?

Answer 1

The way you've stated the diagonal lemma is odd (and I've not seen it put that way before). The standard phrasing is:

For every formula $\varphi(x)$, there is some sentence $\sigma$ such that $$PA\vdash \sigma\leftrightarrow\varphi(\ulcorner\sigma\urcorner).$$

Note that there is no $f$ here! Rather, we're talking about properties: intuitively, the conclusion is that PA proves "$\sigma$ is true iff $\sigma$ has property $\varphi$." This makes things a little easier to see, in my opinion: in order to implement your argument we'd want to let $\varphi$ be the formula "is false."

So what your argument lets us conclude is that no such $\varphi$ exists - that is, Tarski's theorem.

---

Now let's shift to the language of the OP, and see how the version of the diagonal lemma that you state emerges.

Suppose $f$ is a computable function from (codes for) sentences to $\{0,1\}$ (treating $0$ as false and $1$ as true). Then $f$ is representable in PA, say by $\psi_f$. Let $\varphi_f$ be the formula $$\psi_f(\ulcorner\sigma\urcorner)=1.$$ Then applying the diagonal lemma as stated above with $\varphi=\varphi_f$ we get some $\sigma$ such that $$PA\vdash\sigma\leftrightarrow \psi_f(\ulcorner\sigma\urcorner)=1$$ (which could suggestively be written in a minor abuse of notation as "$PA\vdash\sigma\leftrightarrow f(\ulcorner\sigma\urcorner)$" - conflating $0/1$ with true/false and conflating $f$ with its representing formula).

The argument you gives shows that the map $n$ sending a sentence to the truth value of its negation is not computable; more snappily, the set of true sentences of arithmetic is not computable. (Note that this is actually weaker than the conclusion gotten above, since every computable function is definable.)

Answer 2

Carnap's lemma applies to computable functions. Your function is not computable.