Simple examples of the diagonal lemma

166 Views Asked by At

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}<y$. 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?