1
$\begingroup$

Given a theory $S$, $M(S)$ denotes the class of models of $S$, that is, if $A\in M(S)$, then $A\vDash S$.

The theorem goes like this: Given two theories $S$ and $T$ of the same first order language such that $M(S)\cap M(T)=\emptyset$, there exists $\theta\in S$ and $\phi\in T$ such that no models of $\theta$ is a model of $\phi$.

To prove the contrapositive statement, suppose that for every pair of $\theta\in S$ and $\phi\in T$, there exists a model $A$ such that $A\vDash\theta\land\phi$.

Let $\Pi\subset S\cup T$ be a finite subset. If I can show that $\Pi$ has a model, then by compactness theorem we can conclude that $S\cup T$ has a model, which finishes the proof.

If $\Pi\subset S$ or $\Pi\subset T$, then the result follows immediately (since $M(S)\neq\emptyset$ and $M(T)\neq\emptyset$). So suppose $\Pi=\{\theta_1,...\theta_m,\phi_1,...\phi_n\}$ with each $\theta_i\in S$ and each $\phi_i\in T$. Then for each pair of $\theta_i$ and $\phi_j$ there is a model $A_{i,j}$ such that $A_{i,j}\vDash\theta_i\land\phi_j$.

Here is where I'm stuck, I want to construct a model $A$ that satisfies $\theta_i\land\phi_j$ for each $i\leq m$ and $j\leq n$. But I'm not sure how/if am I able to do that.

$\endgroup$
  • $\begingroup$ What definition of "theory" are you using? Is a theory just any set of sentences, or is it deductively closed? $\endgroup$ – bof Sep 28 '17 at 10:15
  • $\begingroup$ $S$ is a theory in a first order language $L$ if $S=Ent(\Sigma)$ for some $\Sigma\subset L$. $Ent(\Sigma):=\{\phi\mid\phi$ is a $L$ sentence, and if $A\vDash\Sigma$ then $A\vDash\phi\}$. $\endgroup$ – Sid Caroline Sep 28 '17 at 10:23
  • $\begingroup$ @bof yes, a theory is deductively closed. A theory is a set of sentences that are consequences of a set of axioms. $\endgroup$ – Sid Caroline Sep 28 '17 at 10:26
  • 1
    $\begingroup$ So, if $\theta_1,\dots,\theta_m\in S,$ then $\theta_1\land\cdots\land\theta_m\in S?$ $\endgroup$ – bof Sep 28 '17 at 10:28
  • $\begingroup$ Why can't you just say: if $S\cup T$ is inconsistent, then some finite subset $S_0\cup T_0\ (S_0\subseteq S,\ T_0\subseteq T)$ is inconsistent; let $\theta$ be the conjunction of the sentences in $S_0$ and let $\phi$ be the conjunction of the sentences in $T_0?$ $\endgroup$ – bof Sep 28 '17 at 10:33
1
$\begingroup$

To prove the contrapositive statement, suppose that for every pair of $\theta\in S$ and $\phi\in T$, there exists a model $A$ such that $A\vDash\theta\land\phi$.

Suppose for a contradiction $S\cup T$ is not satisfiable. Then by compactness theorem there exists a finite subset $S_0\cup T_0\subset S\cup T$ that is not satisfiable. Let $S_0\cup T_0$ be such, with $S_0=\{\theta_1,...,\theta_m\}\subset S$ and $T_0=\{\phi_1,...,\phi_n\}\subset T$. Then $S_0\cup T_0=\{\theta_1,...,\theta_m,\phi_1,...,\phi_n\}$.

Let $\theta=\theta_1\land...\theta_m$, $\phi=\phi_1\land...\phi_n$. Then by definition of theory, $\theta\in S$ and $\phi\in T$. By our hypothesis, there exists a model $A$ such that $A\vDash\theta\land\phi$. Hence $A\vDash\theta_1\land...\land\theta_m\land\phi_1\land...\land\phi_n$. Hence $A\vDash S_0\cup T_0$, which contradicts that $S_0\cup T_0$ being not satisfiable.

Hence $S\cup T$ is satisfiable. So $M(S)\cap M(T)\neq\emptyset$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.