Prove that a theory $\Gamma$ is consistent if and only if there is a structure $M$ so that $M$ $\models$ $\Gamma$.

Question

$\Gamma$ is consistent, then either $\Gamma \models \varphi$ or $\Gamma \models \neg \varphi$ (but not both) for all sentences $\varphi$.

Can we assume $M$ is a structure such that $M \models \varphi$ for all $\varphi \in \Gamma$? I think this is incorrect because if so, $M \models \Gamma$ will be true trivially. We are assuming what we want to prove. If this is wrong, what else can I try?

On the other side, from $M \models \Gamma$, we have $M \models \varphi$ for every $\varphi \in \Gamma$.

Then can we say $M \not\models \neg\varphi$? And how can we finish the prove with $\neg (M \models \varphi \land \neg\varphi)$?

Answer 1

If $\Gamma$ is consistent (i.e. $\Gamma\models\varphi\longrightarrow\Gamma\not\models\neg\varphi$) then clearly there exists a formula $\varphi$ such that $\Gamma\not\models\varphi$. So $\Gamma$ has a model $M\models\Gamma$, since otherwise every model of $\Gamma$ (since there are none) would satisfy $\varphi$. This may seem a bit tricky, to use a void hypothesis, but if you think a moment you will realise that it is not.

The converse is clear, right? If $\Gamma$ has a model, the inconsistence of $\Gamma$ would imply that some $\varphi$ is true and false in that model.

Answer 2

From right to left is the easy one: if $M \vDash \Gamma$ then $ M \vDash \varphi$ for all $\varphi\in \Gamma$ (by definition of $M\vDashφ$). Ans since M is a structure, you have that whenever $M\vDash \varphi $ then $M\not \vDash\neg \varphi$ (By definition of it being a structure), and finally you have $M⊨ \varphi \land \psi$ iff $M\vDash\varphi$ and $M\vDash \psi$ by formal semantics of the $\land$, so you can't have $\Gamma \vDash\varphi \land \neg \varphi$. So: if $\Gamma$ were inconsistent, we would have $\Gamma\vDash\varphi \land \neg \varphi$, and thus $M \vDash\varphi \land \neg \varphi$, and thus both $M\vDash \varphi $ and $M \vDash \neg \varphi$. But as we just saw, that is impossible. So, $M$ is consistent.

From left to right is a good bit harder! As pointed out, we can't assume $\Gamma$ is complete ... but we can extend $\Gamma$ into $\Gamma$' such that $\Gamma$' is complete: Roughly, you consider any of the sentences $\varphi$ that can be generated from your language for which $\Gamma \not \vDash \varphi$ and $\Gamma \not \vDash \neg \varphi$, and add them one by one to $\Gamma$ (one by one, so that once you have added $\varphi$, you don't end up adding $\neg \varphi$ as well ... it is a good thing that for any enumerable language all sentences from that language are enumerable as well!).

And, now you can show that any consistent and complete set of sentences $\Gamma$ has a model by focusing on the atomic statements of $\Gamma$ and translating those into a structure $M$ so that $M$ indeed becomes a model for $\Gamma$.

So: given that $\Gamma$' has a model, $\Gamma$ has a model as well (the same one!)

But there are lots of technical details to this proof!