# Simple examples of the diagonal lemma

According to Boolos' Computability and Logic, the diagonal lemma states:

Let $$T$$ be a theory containing $$\mathbf{Q}$$. Then for any formula $$B(y)$$ there is a sentence $$G$$ such that $$\vdash_T\,G\leftrightarrow B(\ulcorner G\urcorner).$$

$$\mathbf{Q}$$ is Boolos' version of Robinson arithmetic. The proof of the lemma involves constructing a sentence $$G$$ which one, in practice, could not possibly write down. But what if we take some simple examples.

• Here's one: let $$B(y)$$ be $$\mathbf{0}^{\prime\prime}. Then we can take $$G$$ to be the sentence $$\mathbf{0}=\mathbf{0}$$, correct? Certainly $$\ulcorner G\urcorner$$ is much greater than 2, so $$G\leftrightarrow B(\ulcorner G\urcorner)$$ is valid.

• Here's another: let $$B(y)$$ be $$y<\mathbf{0}^{\prime\prime}$$. There aren't any sentences with Godel numbers less than 2, so we choose any false sentence we like for $$G$$, such as $$\mathbf{0}=\mathbf{0}^\prime$$. Then, once again, $$G\leftrightarrow B(\ulcorner G\urcorner)$$ is valid.

I am correct in believing that, for very simple formulas $$B(y)$$ of arithmetic, it's actually incredibly easy to construct a diagonal sentence $$G$$? In general, though, is this method not feasible?

• "The proof of the lemma involves constructing a sentence 𝐺 which one, in practice, could not possibly write down." It's not actually that bad - long, yes, but I don't think they're more than a few pages long (at least, according to reasonably efficient coding systems). – Noah Schweber May 4 at 15:11
• Good point Noah. Replace "possibly" with "easily". – Doubt May 4 at 15:13