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!

  • 1
    $\begingroup$ How do you define computable? Surely you can come up with an algorithm that solves 1. $\endgroup$ – Andrés E. Caicedo Nov 17 '18 at 21:23
  • $\begingroup$ Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set $\endgroup$ – Rebecca Bonham Nov 17 '18 at 21:34
  • $\begingroup$ 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. $\endgroup$ – Rebecca Bonham Nov 17 '18 at 21:37
  • 1
    $\begingroup$ 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). $\endgroup$ – Rob Arthan Nov 17 '18 at 23:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Nov 17 '18 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.