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?


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

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

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

  • $\begingroup$ 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 ... $\endgroup$ – erik Dec 13 '19 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.