[Math] A consistent set of formulas is satisfiable.

logicpropositional-calculus

Is the following proof correct, or I miss something?

Lemma
A consistent set of formulas is satisfiable.

Proof

Let be $\Sigma$ is consistent set of formulas, thus, from Proposition ???, there is no $\alpha$ such that $\Sigma\vdash\alpha$ and $\Sigma\vdash\neg\alpha$. Thus we can define a truth assignment
$u$ as follows:
\begin{equation}
u(\alpha)=\begin{cases}\top&\text{if $\Sigma\vdash\alpha$}\\
\bot&\text{if $\Sigma\vdash\neg\alpha$}\\
\top\text{ (or $\bot$)}&\text{otherwise.}
\end{cases}
\end{equation}

For all $\beta\in\Sigma$ we have $\Sigma\vdash\beta$, thus $u(\beta)=\top$.
Therefore $\Sigma$ is satisfiable.

Definitions

I use a definition of consistent that I proved (Proposition ???) to be equivalent to 'there is no $\alpha$ such that $\Sigma\vdash\alpha$ and $\Sigma\vdash\neg\alpha$'.

A set of formula $\Sigma$ is satisfiable if there is a truth assignment that satisfies all formula in $\Sigma$.

Best Answer

This is incorrect: consider the situation where we have two propositional atoms $p$ and $q$, and $\Sigma=\emptyset$ (so doesn't prove anything other than tautologies). According to your definition of $u$, there is no restriction on what truth values can be assigned to each of the following sentences (each of which is undecidable in $\Sigma$):

  • $p$,

  • $q$,

  • $\neg(p\wedge q)$.

However, clearly we can't assign each of them "$\top$." So your approach for defining a valuation for $\Sigma$ needs to be more complicated: it needs to take into account how the various sentences, even those undecidable in $\Sigma$, interact with each other.

Note that this problem would not arise if we assumed additionally that $\Sigma$ was complete: that is, for each $\varphi$, either $\varphi\in \Sigma$ or $\neg\varphi\in\Sigma$. (Indeed, then the third clause of your definition of $u$ would be unnecessary.) So what is immediately true is:

$(*)\quad$ Any complete consistent theory has a model.

So now you need to prove:

$(**)\quad$ Any consistent theory is contained in a complete consistent theory.

It's also worth mentioning for contrast what happens in first-order logic. (In particular, this old question nicely parallels yours.)

In first-order logic, the notion of satisfiability is more complex: a model is not just a truth assignment. We still have "consistency implies satisfiability" (for the right proof system, anyways), but the proof is a bit more complicated. However, it evolves quite nicely from the proof of the completeness theorem for propositional logic; see this exposition by Bezhanishvili.

Related Question