# Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic

I am struggling with the following two problems:

1. Suppose that $$M$$ is a structure with finite universe and finite alphabet. Show that the set of formulas $$\{\varphi$$ $$\mid$$ for every $$M$$-assignment $$\nu$$ of the variables, $$(M,\nu) \models \varphi\}$$ is computable.

2. Give an example of a finite language such that the set of formulas $$\{\varphi$$ $$\mid$$ for every finite structure $$M$$ which interprets that language and every $$M$$-assignment $$\nu$$ of the variables, $$(M,\nu) \models \varphi\}$$ is not computable.

Note that in the above problems, "$$(M,\nu) \models \varphi$$" is to be read as "$$\varphi$$ holds in $$M$$ when the variables of $$\varphi$$ are evaluated in $$M$$ according to $$\nu$$."

Now let $$V:= \{\varphi \mid \varphi$$ is a validity $$\}$$, where "A formula $$\varphi$$ is a validity" means "For all $$(M,\nu)$$, if $$(M,\nu)$$ interprets all the nonlogical symbols of $$\varphi$$, then $$(M,\nu) \models \varphi$$." I know that $$V \geq_m H$$ and therefore $$V$$ is not computable. The example sought by the second problem would seem to involve this theorem.

Unfortunately I can't see much further beyond this. Would anyone be so kind to share any hints or remarks that would help me begin to understand how to work towards a solution of these?

Thank you so much!

• How do you define computable? Surely you can come up with an algorithm that solves 1. – Andrés E. Caicedo Nov 17 '18 at 21:23
• Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set – Rebecca Bonham Nov 17 '18 at 21:34
• Intuitively, I understand the idea of algorithmically deciding whether each $\varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense. – Rebecca Bonham Nov 17 '18 at 21:37
• For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $\phi$, it is a finite task to check whether $\phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $\phi$ holds). – Rob Arthan Nov 17 '18 at 23:41
• If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case. – Rob Arthan Nov 17 '18 at 23:53