Results 1 to 4 of 4

Thread: Fol 7

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 7

    Enderton Problem 6 in Section 2.5

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

    =========
    Since $\displaystyle \Sigma_1 \cup \Sigma_2$ is unsatisfiable, it is inconsistent by the completeness theorem. Therefore, $\displaystyle \Sigma_1 \cup \Sigma_2 \vdash \tau$ and $\displaystyle \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,577
    Thanks
    790

    Re: Fol 7

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

    As the hint says, by the compactness theorem there exists a finite subset of $\displaystyle \Sigma_1\cup\Sigma_2$ that is unsatisfiable. By dividing this subset into subsets of $\displaystyle \Sigma_1$ and $\displaystyle \Sigma_2$ we have two formulas $\displaystyle \phi_1$ and $\displaystyle \phi_2$ such that $\displaystyle \phi_1\land\phi_2$ is unsatisfiable and $\displaystyle \phi_i$ is a conjunction of formulas from $\displaystyle \Sigma_i$ ($\displaystyle 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 $\displaystyle \text{Mod } \Sigma_1$ denote the class of models of $\displaystyle \Sigma_1$, i.e., does $\displaystyle \text{Mod } \Sigma_1 \subseteq \text{Mod }\tau$ mean $\displaystyle \Sigma_1\models\tau$?
    Yes, I think so.

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

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

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

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

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

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Fol 7

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


/mathhelpforum @mathhelpforum