Results 1 to 2 of 2

Math Help - Fol 11

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum