1. ## Fol 11

Enderton 2.6.9

Say that a set $\Sigma$ of sentences has the finite model property iff each member $\sigma$ of $\Sigma$, if it has any model at all, has a finite model. Assume that $\Sigma$ is a set of sentences in a finite language (i.e., a language with finitely many parameters) and that $\Sigma$ has finite model property. Give an effective procedure that, given any member $\sigma$ of $\Sigma$, will decide whether or not $\sigma$ has any models. Suggestion: Is the set of such sentences effectively enumerable? Is its complement effectively enumerable?

=============================
(*) For a finite language, $\{\sigma | \sigma \text{ has a finite model}\}$ is effectively enumerable.

If $\sigma \in \Sigma$ has any models, then $\Sigma$ has a finite model. By (*), there is an effective procedure to produce the answer "Yes" if $\sigma$ has any models.

An effective procedure to produce the answer "No" if $\sigma$ does not have any models is as follows.
...

=================

Any help will be appreciated.

2. ## Re: Fol 11

My guess is that you are supposed to use the fact that the set of tautologies is enumerable because of the completeness theorem.