0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – PeptideChain Apr 30 '18 at 13:36
  • $\begingroup$ 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$.' $\endgroup$ – PeptideChain Apr 30 '18 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.