0
$\begingroup$

Let $V = \{\ulcorner\phi\urcorner \mid A \vdash \phi\}$, where $A$ is $\{(\forall{x})(\forall{y})x=y\}$. I'm having trouble understanding why my book* states (in the solution to problem $1$, Section $7.7.1$) that $V$ is computable, even though $U = \{\ulcorner\phi\urcorner \mid \emptyset \vdash \phi\} = \{\ulcorner\phi\urcorner \mid \emptyset \vDash \phi\}$ is not computable (by the undecidability of the Entsheidungsproblem).

A note about notation: $\ulcorner\phi\urcorner$ is the Gödel number of the formula $\phi$.

*"A Friendly Introduction to Mathematical Logic" (Leary; Kristiansen; $2$nd edition)

$\endgroup$
3
  • $\begingroup$ What does the notation $\ulcorner\phi\urcorner$ mean? $\endgroup$
    – tolUene
    Aug 18 at 15:14
  • 1
    $\begingroup$ @tolUene That's one of the common notations for the Godel number of the formula $\phi$. $\endgroup$ Aug 18 at 15:28
  • 1
    $\begingroup$ To the OP, it's helpful (justified by the completeness/soundness theorem) to think semantically at first: can you come up with an intuitive way to tell whether a sentence is provable from $A$? The key is that "provable from $A$" is the same as "true as long as there is only one element in the universe." $U$ is indeed much more complicated than $V$, since $\emptyset$ puts no restrictions on the relevant models but $A$ does. $\endgroup$ Aug 18 at 15:31

1 Answer 1

1
$\begingroup$

The reason is that it is much "easier" to check whether a sentence follows from $A$ than whether it is true or not, since $A$ essentially tells you all objects that you are quantifying over are the same. That is, checking if $\exists x . \phi$ is true (where $x$ is the only variable in $\phi$) amounts to checking whether $\phi$ is true for some arbitrary choice of $x$. The same obviously holds for $\forall x. \phi$. Since we can write any formula $\phi$ in the form $\forall x_1 \exists x_2 \forall x_3 \ldots \exists x_n . \phi'$ (where the only variables in $\phi$ are $x_1, \ldots, x_n$), to check whether $\phi$ is true, it suffices to check whether $\phi'$ is true for some arbitrarily chosen value of $x_1 = x_2 = \ldots = x_n$.

$\endgroup$

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.