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

Results 1 to 2 of 2

- Nov 14th 2011, 01:52 AM #1

- Joined
- Nov 2011
- Posts
- 59

## Fol 11

Enderton 2.6.9

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

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

(*) For a finite language, is effectively enumerable.

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

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

...

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

Any help will be appreciated.

- Nov 14th 2011, 07:48 AM #2

- Joined
- Oct 2009
- Posts
- 5,573
- Thanks
- 789