Results 1 to 6 of 6

Math Help - Fol 9

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 9

    Enderton 2.6.2

    Let T_1 and T_2 be theories (in the same language) such that

    (i) T_1 \subseteq T_2,
    (ii) T_1 is complete, and
    (iii) T_2 is satisfiable. Show that T_1 = T_2.

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

    Before I get started, I need to understand some definitions related to this problem.

    (*) A theory T is said to be complete iff for every sentence \sigma, either \sigma \in T or \neg \sigma \in T.

    I am confused with an unsatisfiable theory, where a theory is defined to be a set of sentences closed under logical implication.

    The textbook gives an example of an unsatisfiable theory, which is the theory consisting of all sentences of the language. Why is this unsatisfiable theory? Any description or example?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Fol 9

    A theory is unsatisfiable if no structure makes all sentences from the theory true. Any theory that contains a formula and its negation is unsatisfiable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 9

    A theory is defined to be a set of sentences closed under logical implications.

    As you said, if I am not mistaken, for an unsatisfiable theory T, there exists a sentence \sigma such that

    T \models \sigma and T \models \neg \sigma, where \sigma \in T and \neg \sigma \in T.

    I was having hard time finding an example of T and \sigma. Is there any concrete example of an unsatisfiable theory T and \sigma for the above?

    Additionally, is there any example of an inconsistent theory T and a sentence \sigma such that

    T \vdash \sigma and T \vdash \neg \sigma?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Fol 9

    The completion of the set \{0=0, \neg 0=0\} under logical implication is unsatisfiable and inconsistent. It logically implies and derives any sentence.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 9

    Quote Originally Posted by emakarov View Post
    The completion of the set \{0=0, \neg 0=0\} under logical implication is unsatisfiable and inconsistent. It logically implies and derives any sentence.
    What is the completion of the set \{0=0, \neg 0=0\} under logical implication?

    As you know, T is a theory iff T is a set of sentences such that for any sentence \sigma of the language,

    T \models \sigma \rightarrow \sigma \in T.

    If it logically implies anything, is it the theory consisting of all the sentences of the language? If the theory consists of all the sentences of the language, is the empty structure the only model for it?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Fol 9

    Quote Originally Posted by logics View Post
    What is the completion of the set \{0=0, \neg 0=0\} under logical implication?
    It's the set of all sentences.

    Quote Originally Posted by logics View Post
    If it logically implies anything, is it the theory consisting of all the sentences of the language?
    Yes.

    Quote Originally Posted by logics View Post
    If the theory consists of all the sentences of the language, is the empty structure the only model for it?
    No; rather, no structure is a model of it. Also, the definition of structure in first-order logic usually has a requirement that the universe is nonempty. Otherwise, the formula \forall x\,Px\to\exists x\,Px is not a tautology.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum