# Showing a set is computable

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)

• What does the notation $\ulcorner\phi\urcorner$ mean? Aug 18 at 15:14
• @tolUene That's one of the common notations for the Godel number of the formula $\phi$. Aug 18 at 15:28
• 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. Aug 18 at 15:31

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