# Math Help - Fol 7

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

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

3. ## Re: Fol 7

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

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