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

$\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)$?

• From "$\Gamma$ is consistent" it does NOT follow that either $\Gamma\models\varphi$ or $\Gamma\models\neg\varphi$ for all sentences $\varphi$. That property is completeness.
– bof
Commented Dec 5, 2016 at 12:18
• Yea, you are right. The definition gives there is no $\Gamma \models \varphi \land \neg \varphi$. Commented Dec 5, 2016 at 12:28
• Some texts regard this as the very definition of consistency, so there would be nothing to prove. Since apparently you have something to prove, you must have a different definition of consistency: can you tell us what that is? (And it is not your first sentence, since that is completeness) Commented Dec 5, 2016 at 13:41
• @Bram28 A theory $Γ$ is consistent if there is no sentence $ψ$ so that $Γ⊨ψ∧¬ψ$, and it is inconsistent if there is such a sentence. Commented Dec 5, 2016 at 13:51
• @yashirq OK, I figured that's what it is but you never know ... It is always good to state in the Question what you have to work with! Anyway, yes, if $M \vDash \Gamma$ then $M \vDash \varphi$ for all $\varphi \in \Gamma$ (by definition of $M \Vdash \varphi$). Ans since $M$ is a structure, you have that whenever $M \vDash \varphi$ then $M \not \vDash \not \varphi$ (By definition of it being a structure), and finally you have $M \vDash \varphi \land \psi$ iff $M \vDash \varphi$ and $M \vDash \psi$ by formal semantics of the $\land$, so you can't have $M \vDash \phi \land \neg \phi$. Commented Dec 5, 2016 at 14:07

(I'm actually not confident the following proof is correct. Bram28's answer and user21820's comment make me think that this is more involved. In Bram28's answer, I'm confused why extending to a complete theory is necessary.)

Only if: We can prove the contrapositive. Suppose there is no structure $$M$$ such that $$M \models \Gamma$$. We want to show that $$\Gamma$$ is inconsistent. For every structure $$M$$, we have $$M\not\models \Gamma$$, so the implication $$\text{if }M \models \Gamma \text{, then } M \models \bot$$ is true for every $$M$$ (because the antecedent is always false). Thus $$\Gamma \models \bot$$. By the completeness theorem, $$\Gamma \vdash \bot$$, so $$\Gamma$$ is inconsistent.

If: Again, we will prove the contrapositive. Suppose $$\Gamma$$ is inconsistent, so that $$\Gamma \vdash \bot$$. Suppose for sake of contradiction that there is some structure $$M$$ such that $$M \models \Gamma$$. By the soundness theorem we have $$\Gamma \models \bot$$. Thus $$M \models \bot$$, a contradiction. So there is no $$M$$ such that $$M\models \Gamma$$.

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!

• Um I think you're talking about propositional logic, which is vastly simpler than for first-order logic... Commented Dec 20, 2016 at 13:54

The right to left implication is obvious, so let's cover only the left to right implication.

Let $$L$$ be the language. For each formula $$\varphi$$ whose only free variable is $$x$$ and such that $$\Gamma \vdash \exists x \varphi(x)$$, add a new constant symbol $$c_\varphi$$. Let $$L'$$ be the language obtained this way.

WLOG, we can assume that $$\Gamma$$ is complete. Let $$L$$ be the language. For each formula $$\varphi$$ whose only free variable is $$x$$ and such that $$\Gamma \vdash \exists x \varphi(x)$$, add a new constant symbol $$c_\varphi$$. Let $$L'$$ be the language obtained this way. Chose any completion $$\Gamma'$$ of $$\Gamma$$ in the language $$L'$$. Clearly, a model of $$\Gamma'$$ induces a model of $$\Gamma$$ (just forget the extra constant symbols).

Let $$Terms$$ be the set of $$L'$$-terms, consider the following equivalence relation on $$Terms$$ : $$t \sim t' : \Longleftrightarrow \Gamma' \vdash t = t'$$

Set $$\boxed{M := Terms / \sim}$$, the domain of our model.

Interpretation of constant symbols :

Let $$c \in L'$$ be a constant symbol, it is interpreted as the equivalence class $$c^M := c^\sim \in M$$.

Interpretation of function symbols :

Let $$f \in L$$ be an $$n$$-ary function symbol. Its interpretation is the (well defined) function $$f^M$$ :
$$f^M : \begin{matrix} M^n & \mapsto & M \\(t_1^{\ \sim}, \dots, t_n^{\ \sim}) & \mapsto & (ft_1, \dots, t_n)^\sim\end{matrix}$$

Interpretation of relation symbols :

Let $$R \in L$$ be a $$n$$-ary relation symbol. Its interpretation is the set $$R^M \subseteq M^n$$ defined bellow : $$R^M := \{(t_1^{\ \sim}, \dots, t_n^{\ \sim}) \in M^n \ \big| \ \Gamma'\vdash R t_1,\dots,t_n\}$$ Once again, it is well defined in the sense that whenever $$u_i \sim t_i$$ for $$1\leqslant i \leqslant n$$, one has $$(t_1^{\ \sim}, \dots, t_n^{\ \sim})\in R^M \Leftrightarrow (u_1^{\ \sim}, \dots, u_n^{\ \sim}) \in R^M$$

The $$L'$$ structure defined this way is a model of $$\Gamma'$$. Hence, we have a model of $$\Gamma$$.

• This is Henkin's theorem btw. Commented Dec 17, 2019 at 15:27

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.

• I don't understand why there is $\Gamma \not\models \varphi$. $\Gamma$ is consistent, we can have either $\Gamma \models \varphi$ or $\Gamma \not\models \varphi$. But we don't know which case. Commented Dec 5, 2016 at 12:04
• Of course, but if $\Gamma\models\theta$ for all $\theta$, then it can deduce everything, so you can deduce from $\Gamma$ every formula $\varphi$ (take $\theta=\varphi$) and its negation (take $\theta=\neg\varphi$). Commented Dec 5, 2016 at 12:08
• Well, I see. So can we also say there exists $\Gamma \models \varphi$....otherwise $\Gamma$ would satisfy $\neg \varphi$? Is it the same meaning? Commented Dec 5, 2016 at 12:17