3
$\begingroup$

I'm doing some excercises from the book "The Incompleteness Phenomenom" from Goldstern and Judah.

I have to do this and I don't know how to start.

Let $\Sigma_1 $ and $\Sigma_2$ be sets of sentences such that there is no model $M$ such that both $M\vDash \Sigma_1$ and $M\vDash \Sigma_2$.

Prove that there exists a sentence $\varphi$ such that:

Every model of $\Sigma_1$ satisfies $\varphi$ and every model of $\Sigma_2$ satisfies $\neg \varphi$.

I will be very grateful if you could give me a hint :) Thank you.

$\endgroup$
2
$\begingroup$

Hint/Sketch: Show that if any of $\Sigma_1$ or $\Sigma_2$ are inconsistent then the "theorem" hold. Thus we may assume both $\Sigma_1$ and $\Sigma_2$ are consistent. What can we now say about $\Sigma_1\cup\Sigma_2$? Use the compactness theorem on this larger set to now deduce the theorem.

Edit Further solution: By compactness we have an inconsistent finite subset $A\subseteq \Sigma_1\cup\Sigma_2$. As both $\Sigma_1$ and $\Sigma_2$ are consistent, $A\not\subseteq \Sigma_1$ and $A\not\subseteq \Sigma_2$. Let $\varphi$ be a conjunction of all sentences from $\Sigma_1$ which are in $A$ and let $\psi$ be a conjunction of all sentences from $\Sigma_2$ which are in $A$.

If $N\models \Sigma_1$ then clearly $N\models \varphi$. If $M\models \Sigma_2$ then $M\models \psi$ but then if $M\models \varphi $ too $M\models A$ which it can't since $A$ is inconsistent. Thus $M\not\models \varphi$ i.e. $M\models \neg \varphi$.

$\endgroup$
  • $\begingroup$ $\Sigma_1 \cup \Sigma_2$ is inconsistent, then by compactness theorem, there exists a finite subset inconsistent, and now...?? $\endgroup$ – Alopiso Apr 5 '16 at 8:35
  • $\begingroup$ Added more details to the solution, see above. $\endgroup$ – Ove Ahlman Apr 5 '16 at 9:01
0
$\begingroup$

By the completeness theorem, "there is no model $M$…" means "$\Sigma_1 \cup \Sigma_2$ is inconsistent". So there are $\alpha$ provable from $\Sigma_1$, $\beta$ provable from $\Sigma_2$ such that $\{ \alpha, \beta \} \vdash \bot$, or else one of $\Sigma_1, \Sigma_2$ is inconsistent.

Now consider $\alpha \wedge \neg \beta$.

$\endgroup$
  • $\begingroup$ Do I have to prove that every model of $\Sigma_1 $ and $\Sigma_2$ satisfies $\alpha \wedge \neg \beta$ and $\neg( \alpha \wedge \neg \beta)$?? $\endgroup$ – Alopiso Apr 5 '16 at 8:38
  • $\begingroup$ If by that you mean "every model of $\Sigma_1$ satisfies $\alpha \wedge \neg \beta$ and every model of $\Sigma_2$ satisfies $\neg(\alpha \wedge \neg \beta)$", then yes. $\endgroup$ – Patrick Stevens Apr 5 '16 at 8:52
  • $\begingroup$ Why not just consider $\alpha$? Every model of $\Sigma_1$ satisfies $\alpha$ and every model of $\Sigma_2$ satisfies $\beta$ which implies $\neg\alpha.$ $\endgroup$ – bof Apr 5 '16 at 8:58
  • $\begingroup$ @bof That seems to work more cleanly. $\endgroup$ – Patrick Stevens Apr 5 '16 at 8:59

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.