How exactly are consistency and satisfiability related in first order logic?

Question

A set $\Gamma$ is consistent if there is $\psi$ such that $\Gamma \not\vdash \psi$.

A set $\Gamma$ is satisfiable if there is a model such that $\Gamma \vDash \psi$ for any $\psi \in \Gamma$.

Intuitively, I understand that for a set to be consistent it must not contain any contradictions, otherwise we can prove anything from it.

I know that if a set is consistent then it is satisfiable, from the completeness theorem, but is it true the other way around? Does satisfiability imply consistency when talking about sets of sentences? I would think not, since satisfiability depends on the model chosen, but I haven't been able to come across any proof or theorem regarding this, or maybe I haven't understood this correctly.

Answer 1

First of all, your definition of satisfiability is wrong. It is not that $\Gamma \vDash \psi$ for every $\psi \in \Gamma$ (which is of course trivially true for any $\Gamma$!), but rather that $\Gamma$ has a model, i.e. that there is an interpretation $I$ such that $I \vDash \psi$ for every $\psi \in \Gamma$

Now, if you say that consistency is $\Gamma \not\vdash \psi$, then by the $\vdash$ you must be referring to some derivational system $S$, so it depends on that derivational system.

For example, for the derivational system that contains no derivational rules (the 'null' system $N$), we have that $\{P, \neg P\} \not \vdash_N Q$, and thus relative to $N$, $\{P, \neg P\}$ is consistent .. but it is clearly not satisfiable.

On the other hand, for the derivational system $B$, whose only rule of derivation is Hokus Ponens (which is: $\vdash \phi$, i.e. you can infer any statement from nothing), we have don't have any $\psi$ such that $\{ \} \not \vdash_B \psi$, and thus relative to $B$, $\{ \}$ is inconsistent, and yet clearly it is satisfiable.

OK, but those are weird systems. As long as we are dealing with a system $S$ that is both sound and complete, consistency and satisfiability are the same thing. Here is why. First, let's establish that for any sound and complete $S$:

Lemma: $\Gamma \vdash_S \bot$ iff for any $\psi$: $\Gamma \vdash \psi$

Proof:

'if': Trivial. Just pick $\psi = \bot$

'only if': We know that $\bot$ implies any $\psi$, and so since $S$ is complete, it can derive $\psi$ from $\bot$. Hence, if $\Gamma \vdash_S \bot$, then $\Gamma \vdash_S \psi$ for any $\psi$

For any $\Gamma$:

$\Gamma$ is consistent iff

There is some $\psi$ such that $\Gamma \not \vdash_S \psi$ iff (Lemma)

$\Gamma \not \vdash_S \bot$ iff (soundness and completeness of $S$)

$\Gamma \not \vDash \bot$ iff

There is no interpretation $I$ such that $I \vDash \psi$ for all $\psi \in \Gamma$ and $I \not \vdash \bot$ iff ($I \not \vdash \bot$ is trivially true)

There is no interpretation $I$ such that $I \vDash \psi$ for all $\psi \in \Gamma$ iff

$\Gamma$ is satisfiable

Answer 2

• Consistency: ∃ψ, Γ⊬ψ
• Satisfiability:∃I, I⊨Γ
• Soundness: Γ⊢ψ ⇒ Γ⊨ψ
• Completeness: Γ⊨ψ ⇒ Γ⊢ψ

1. Satisfiability implies consistency iff the system is sound.

The "if" direction: Suppose Γ is not consistent, then Γ⊢⊥, which implies Γ⊨⊥ by soundness. So any interpretation I with I⊨Γ must have I⊨⊥, which is impossible. Thus Γ is unsatisfiable, .

The "only if" direction: Suppose Γ⊢ψ, thus Γ∪{¬ψ} is inconsistent, which implies that Γ∪{¬ψ} is unsatisfiable. So any interpretation I with I⊨Γ must have I⊭¬ψ i.e. I⊨ψ. So be definition Γ⊨ψ.

2. Consistency implies satisfiability iff the system is complete.

The "if" direction: Suppose Γ is consistent, then there is some ψ such that Γ⊬ψ. By completeness, Γ⊭ψ. Thus Γ must be satisfiable, because otherwise it could entail everything by definition. This is the same argument as in Bram28's answer, except it should be "There exists an interpretation" instead of "There is no interpretation" there.

The "only if" direction: Suppose Γ⊬ψ. Then Γ∪{¬ψ} must be consistent. This implies satisfiability, i.e. there exists an interpretation I such that I⊨Γ and I⊨¬ψ i.e. I⊭ψ. So be definition Γ⊭ψ.