3
$\begingroup$

I was looking for an example for a a non- complete set of formulas (not finite) that might be decidable and I found the following statement:

Given a recursive language $L$ the set $\{ \phi \ | \ \phi$ is a universal sentence with an infinite model$ \}$ is a recursive set.

I guess that one has to build such algorithm by hand, and by compactness one know that if $\phi$ does not have an infinite model then there is some $m$ such that $\phi \cup \{ \exists x_{1}\dots x_{m} \big(\bigwedge x_{i} \neq x_{j} \big)\}$ must be inconsistent. So my ideas was "coding" arbitrarily large structures and checking recursively if the sentence holds or not. But the problem with this idea is that it is actually only giving al algorithm listing the complement! Any hint will be appreciated!

Improve this question
$\endgroup$
2
  • $\begingroup$ Where did you find this statement? $\endgroup$
    – Wojowu
    Commented Jul 3, 2017 at 14:06
  • 6
    $\begingroup$ The statement is false. For example, given a sentence $\psi$ in the language of arithmetic, the Skolemization of $Q+\psi$ (which is a universal sentence, computable from $\psi$) has an infinite model iff $Q+\psi$ is consistent, hence your statement would imply that $Q$ is decidable. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2017 at 14:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .