# diagonal lemma and the negation function

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?

## 2 Answers

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.)

• Thanks! That is indeed the solid theoretical explanation that I needed. Super! – erik Dec 14 '19 at 2:10

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

• Interesting. Do you mean that f cannot make use of the truth value of s? That is indeed very conceivable, because according to Tarski's undefinability theorem, it is not possible to define the one-variable formula true($\ulcorner s\urcorner$). Hence, something like eval($\ulcorner s\urcorner$) could also be unsupported, because eval effectively amounts to computing the truth value for the sentence. It would be nice if someone could confirm something like that, a bit more theoretically ... – erik Dec 13 '19 at 11:17