# A consistent set of formulas is satisfiable.

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: $$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}$$

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

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.

• Great! the notes that I follow have no single proof, but they have the lemma 'satisfiable implies consistent' at the beginning and 'consistent implies satisfiable' after the lemmas about maximally consistent. I made the error to move the 2nd together with the 1st. now I understand why. I assume that your complete is in "my" 'maximally consistent', and my truth assignment is your model or valuation. – PeptideChain Apr 30 '18 at 13:36
• Your (**) is probably my 'Given a consistent set of formulas $\Sigma$, there is a maximally consistent set of formulas $\Gamma$ such that $\Sigma\subset\Gamma$.' – PeptideChain Apr 30 '18 at 13:37