1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "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). $\endgroup$ – Noah Schweber May 4 at 15:11
  • $\begingroup$ Good point Noah. Replace "possibly" with "easily". $\endgroup$ – Doubt May 4 at 15:13

Your Answer

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

Browse other questions tagged or ask your own question.