Set of formulas sigma satisfiable iff no contradiction beta such that sigma implies beta

931 Views Asked by At

Lemma 2.34 A set of formulas $\Sigma$ is satisfiable if and only if there is no contradiction $\mu$ such that $\Sigma\vDash\mu$.

Proof (1) $\Sigma$ is satisfiable implies that there is a truth assignment $u$, such that $\forall\alpha\in \Sigma:u(\alpha)=\top$ therefore there is no contradiction $\beta$ such that $\Sigma\vDash\beta$, because $\forall\alpha\in \Sigma:u(\alpha)=\top$, but $u(\beta)=\bot$ (from definition of contradiction).

(2) On the other side if there is no contradiction $\beta$ such that $\Sigma\vDash\beta$ it means that there is no formula $\beta$ such that there is a truth assignment $u$, such that (i) $\Sigma\vDash\beta$, that is $\forall\alpha\in \Sigma:u(\alpha)=\top$, and $u(\beta)=\top$, (ii) $\beta$ is contradiction, that is $u(\beta)=\bot$. Therefore, since there is a truth assignment $u$, such that $\forall\alpha\in \Sigma:u(\alpha)=\top$ ($\color{blue}{\text{otherwise in the previous implication step we could not prove that there is no contradiction}}$), then $\Sigma$ is satisfiable.

Is this proof correct? In particular: Am I allowed to use the implication in blue?

EDIT

Adapted proof after the answer of @DerekElkins.

Proof (1) $\Sigma$ is satisfiable implies that there is a truth assignment $u$, such that $\forall\alpha\in \Sigma:u(\alpha)=\top$. $\Sigma\vDash\mu$ means that if there is a truth assignment $u$ such that $\forall\alpha\in \Sigma:u(\alpha)=\top$, than $u(\mu)=\top$. But this is not possible if $\mu$ is a contradiction, since a formula $\beta$ is a contradiction if for every truth assignment $v$, $v(\beta)=\bot$. Therefore there is no contradiction $\mu$ such that $\Sigma\vDash\mu$.

(2) On the other side, we have that there is no contradiction $\beta$ such that $\Sigma\vDash\beta$, or, stated with other words, we have that for every contradiction $\beta$ follows $\Sigma\nvDash\beta$. We proceed by contradiction. Suppose $\Sigma$ is not satisfiable, then there is no truth assignment $u$, such that $\forall \alpha\in\Sigma:\ u(\alpha)=\top$. But if there is no such truth assignment $u$, we can not state that 'there is no contradiction $\beta$ such that $\Sigma\vDash\beta$', because we can not prove $\Sigma\vDash\beta$. Therefore $\Sigma$ must be satisfiable.

EDIT 2 Definitions

We say that a formula $\mu$ is satisfiable if there is some truth assignment which satisfies $\mu$. We say that the formulas $\mu_1,\cdots,\mu_n$ are satisfiable if there is some truth assignment which satisfies all $\mu_i$, $1\leq i\leq n$.

2

There are 2 best solutions below

5
On BEST ANSWER

To answer the question you seem to be focusing on, you definitely can use facts you've proven earlier in the proof to help prove later parts of the proof. Put a different way, you could split this lemma into two lemmas with the latter lemma referring to the former lemma. That said, you don't appear to be referring to the previous result but to the assumption of the previous result. Presumably, "$\Sigma$ is satisfiable" means by definition "there is a truth assignment $u$ such that $\forall \alpha\in\Sigma.u(\alpha)=\top$". So while you can use the previously established result as a whole, you can't take some intermediate step, let alone some assumption, out of context and use it elsewhere. To apply the ideas you're learning about now to the meta-logic, you essentially showed $\Gamma\cup\{\varphi\}\vdash\psi$. Then, while attempting to show $\Gamma\vdash\chi$, you are claiming that $\varphi$ holds, because you wouldn't have been able to prove $\psi$ without it, but $\psi$ doesn't hold in context $\Gamma$. Actually, the situation is more like you are attempting to prove $\Gamma\cup\{\psi\}\vdash\varphi$, so $\psi$ does hold in context $\Gamma\cup\{\psi\}$, but in this case it is (trivially) provable without assuming $\varphi$ so its provability still doesn't allow us to establish $\varphi$.

What you want to do is note that "there is no contradiction $\beta$ such that $\Sigma\vDash\beta$" is equivalent to "for every contradiction $\beta$, $\Sigma\not\vDash\beta$". By definition, $\Sigma\vDash\beta$ means for every truth assignment $u$, $\forall \alpha\in\Sigma.u(\alpha)=\top$, $u(\beta)=\top$, but, of course, $u(\beta)=\bot$ so this could only be true vacuously. That is, there can be no truth assignment $u$, such that $\forall\alpha\in\Sigma.u(\alpha)=\top$. We have the negation of this statement, i.e. that there is such a truth assignment, which is to say that $\Sigma$ is satisfiable. $\square$

The first half of your proof could also be made clearer by stating why certain steps are allowable and making the contradiction clearer. Specifically, articulate definitions. When proving things, everything follows from definitions. This leads to the following: By definition, $\Sigma$ is satisfiable means that there is a truth assignment $u$ such that $\forall\alpha\in\Sigma.u(\alpha)=\top$. Assume we have a contradiction $\beta$, i.e. a formula $\beta$ such that for every truth assignment $v$, $v(\beta)=\bot$, for which $\Sigma\vDash\beta$. By definition, $\Sigma\vDash\beta$ means that for every truth assignment $v$, if $\forall\alpha\in\Sigma.v(\alpha)=\top$ then $v(\beta)=\top$. In particular, for the truth assignment $u$ witnessing the satisfiability of $\Sigma$, $u(\beta)=\top$, but $u(\beta)=\bot$ so we have a contradiction. Thus it can't be the case that a contradiction $\beta$ exists for which $\Sigma\vDash\beta$. $\square$

0
On

Here is a proof of Lemma 2.34 which is the result of trying to solve the same exercise but from A Problem Course in Mathematical Logic (http://euclid.trentu.ca/math/sb/pcml/) > Chapter 2 > Proposition 2.10:

$\begin{split} \text{There is no contradiction } \chi \text{ such that } \Sigma \vDash \chi & \iff \neg (\exists \chi)(\chi \text { is a contradiction} \implies \Sigma \vDash \chi) \\ & \iff (\forall \chi) \neg (\chi \text { is a contradiction} \implies \Sigma \vDash \chi) \\ & \iff (\forall \chi)(\chi \text { is a contradiction} \land \Sigma \nvDash \chi) \\ & \iff (\forall \chi)(\chi \text { is a contradiction} \land (\exists v)(v \text{ is a truth assignment} \land (\forall \sigma)( \sigma \in \Sigma \implies v(\sigma) = T) \land v(\chi) = F)) \\ & \iff \Sigma \text{ is satisfiable and } \chi \text{ is any contradiction} \end{split}$

In this way you don't need to divide the proof in 2 parts. Also take into account that $\Sigma \vDash \chi$, $\Sigma \nvDash \chi$ and $\Sigma$ is satisfiable mean:

  • $\begin{split} \Sigma \vDash \chi & \iff (\forall v)((v \text{ is a truth assignment} \land (\forall \sigma)(\sigma \in \Sigma \implies v(\sigma) = T)) \implies v(\chi) = T) \\ \\ \end{split}$

  • $\begin{split} \Sigma \nvDash \chi & \iff \neg \Sigma \vDash \chi \\ & \iff \neg (\forall v)((v \text{ is a truth assignment} \land (\forall \sigma)(\sigma \in \Sigma \implies v(\sigma) = T)) \implies v(\chi) = T) \\ & \iff (\exists v) \neg ((v \text{ is a truth assignment} \land (\forall \sigma)(\sigma \in \Sigma \implies v(\sigma) = T)) \implies v(\chi) = T) \\ & \iff (\exists v)(v \text{ is a truth assignment} \land (\forall \sigma)(\sigma \in \Sigma \implies v(\sigma) = T) \land v(\chi) = F) \\ \\ \end{split}$

  • $\begin{split} \Sigma \text{ is satisfiable} & \iff (\exists v)(v \text{ is a truth assignment} \land (\forall \sigma)( \sigma \in \Sigma \implies v(\sigma) = T)) \\ \\ \end{split}$

If you want and introduction to formal logic check out in your local library the appendices and the first chapter of the book:

  • Mendelson, Elliott. 2008. Number Systems and the Foundations of Analysis. Mineola, N.Y: Dover Publications. ISBN-13: 978-0486457925

This book is a really good introduction because it contains exercises where you need to transform english sentences into symbols of propositional and first order logic. Also check out: