Showing a set is computable

53 Views Asked by At

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)

1

There are 1 best solutions below

0
On BEST ANSWER

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