Results 1 to 4 of 4

Math Help - Fol 7

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 7

    Enderton Problem 6 in Section 2.5

    Let \Sigma_1 and \Sigma_2 be sets of sentences such that nothing is a model of both \Sigma_1 and \Sigma_2. Show that there is a sentence \tau such that \text{Mod } \Sigma_1 \subseteq \text{Mod }\tau and \text{Mod } \Sigma_2 \subseteq \text {Mod } \neg \tau. (This can be stated Disjoint \text{EC}_\Delta classes can be separated by an EC class.) Suggestion: \Sigma_1 \cup \Sigma_2 is unsatisfiable; apply compactness.

    =========
    Since \Sigma_1 \cup \Sigma_2 is unsatisfiable, it is inconsistent by the completeness theorem. Therefore, \Sigma_1 \cup \Sigma_2 \vdash \tau and \Sigma_1 \cup \Sigma_2 \vdash \neg \tau. I am stuck here.

    Any help will be highly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Fol 7

    Does \text{Mod } \Sigma_1 denote the class of models of \Sigma_1, i.e., does \text{Mod } \Sigma_1 \subseteq \text{Mod }\tau mean \Sigma_1\models\tau?

    As the hint says, by the compactness theorem there exists a finite subset of \Sigma_1\cup\Sigma_2 that is unsatisfiable. By dividing this subset into subsets of \Sigma_1 and \Sigma_2 we have two formulas \phi_1 and \phi_2 such that \phi_1\land\phi_2 is unsatisfiable and \phi_i is a conjunction of formulas from \Sigma_i ( i=1,2). Try to go from there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 7

    Quote Originally Posted by emakarov View Post
    Does \text{Mod } \Sigma_1 denote the class of models of \Sigma_1, i.e., does \text{Mod } \Sigma_1 \subseteq \text{Mod }\tau mean \Sigma_1\models\tau?
    Yes, I think so.

    As the hint says, by the compactness theorem there exists a finite subset of \Sigma_1\cup\Sigma_2 that is unsatisfiable. By dividing this subset into subsets of \Sigma_1 and \Sigma_2 we have two formulas \phi_1 and \phi_2 such that \phi_1\land\phi_2 is unsatisfiable and \phi_i is a conjunction of formulas from \Sigma_i ( i=1,2). Try to go from there.

    By compactness theorem, there exists a finite subset X of \Sigma_1 \cup \Sigma_2 that is not satisfiable. Then, X = X_1 \cup X_2, where X_1 = X \cap \Sigma_1, and X_2 = X \cap \Sigma_2.

    I still can't find \tau. In your construction what is the corresponding \tau?

    For example, if \tau \in X_1, then \text{Mod }\Sigma_1 \subseteq \text{Mod }\tau, since \tau is an element of \Sigma_1. But we don't know X is maximal in the sense that \neg \tau \in X_2.

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

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Fol 7

    Take \tau=\bigwedge X_1 (conjunction of formulas in X_1). Also note that \bigwedge X_2\to\neg\tau is a tautology since \tau\land\bigwedge X_2 is unsatisfiable.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum