I am struggling with the following two problems:
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.
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!