0
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – bof
    Commented Dec 5, 2016 at 12:18
  • $\begingroup$ Yea, you are right. The definition gives there is no $\Gamma \models \varphi \land \neg \varphi$. $\endgroup$
    – yashirq
    Commented Dec 5, 2016 at 12:28
  • $\begingroup$ 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) $\endgroup$
    – Bram28
    Commented Dec 5, 2016 at 13:41
  • $\begingroup$ @Bram28 A theory $Γ$ is consistent if there is no sentence $ψ$ so that $Γ⊨ψ∧¬ψ$, and it is inconsistent if there is such a sentence. $\endgroup$
    – yashirq
    Commented Dec 5, 2016 at 13:51
  • $\begingroup$ @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$. $\endgroup$
    – Bram28
    Commented Dec 5, 2016 at 14:07

4 Answers 4

1
$\begingroup$

(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$.

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Um I think you're talking about propositional logic, which is vastly simpler than for first-order logic... $\endgroup$
    – user21820
    Commented Dec 20, 2016 at 13:54
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ This is Henkin's theorem btw. $\endgroup$ Commented Dec 17, 2019 at 15:27
-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – yashirq
    Commented Dec 5, 2016 at 12:04
  • $\begingroup$ 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$). $\endgroup$
    – W. Rether
    Commented Dec 5, 2016 at 12:08
  • $\begingroup$ Well, I see. So can we also say there exists $\Gamma \models \varphi$....otherwise $\Gamma$ would satisfy $\neg \varphi$? Is it the same meaning? $\endgroup$
    – yashirq
    Commented Dec 5, 2016 at 12:17

Not the answer you're looking for? Browse other questions tagged .