1. ## 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.

2. ## 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.

3. ## Re: Fol 7

Originally Posted by emakarov
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.

4. ## 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.