1
$\begingroup$

I am trying to understand the last part of the proof of Lemma 15.2 in these notes: https://math.boisestate.edu/~scoskey/courses/0708s-461ru/002Propositional.pdf

It states: "Since $\Sigma$ is finitely satisfiable, there exists a truth assignment $v$ which satisfies $\Sigma_{0} \cap \Delta_{0}$. Since $\Sigma_{0} \models \lnot \alpha$, it follows that $\overline{v}(\lnot \alpha) = T$. Hence $v$ satisfies $\Delta_{0} \cup \{\lnot \alpha\}$."

I can see the first line, since $\Sigma_{0} \cap \Delta_{0}$ is a finite subset of $\Sigma$ and therefore is satisfiable. I do not understand why the following lines follow from it. Is it possible that they mean $\Sigma_{0} \cup \Delta_{0}$ instead of $\Sigma_{0} \cap \Delta_{0}$?

$\endgroup$

1 Answer 1

1
$\begingroup$

You are right, there is a typo, they mean $\Sigma_0 \cup \Delta_0$ instead of $\Sigma_0 \cap \Delta_0$. The crucial point is that if $v$ satisfies $\Sigma_0 \cap \Delta_0$, we cannot deduce that $\overline{v}(\lnot \alpha) = \top$. But if $v$ satisfies $\Sigma_0 \cup \Delta_0$, everything works.

Indeed, since $\Sigma_0 \subseteq \Sigma$ and $\Delta_0 \subseteq \Sigma$, we have that $\Sigma_0 \cup \Delta_0 \subseteq \Sigma$ and hence (by finite satisfiability of $\Sigma$) there exists a truth assignment $v$ which satisfies $\Sigma_0 \cup \Delta_0$. Since $\Sigma_0 \models \lnot\alpha$, it follows that $\overline{v}(\lnot \alpha)=\top$ (because $v$ satisfies $\Sigma_0$: this would not be the case if we took $v$ satisfying $\Sigma_0 \cap \Delta_0$ instead of $\Sigma_0 \cup \Delta_0$). Hence, $v$ satisfies $\Delta = \Delta_0 \cup \{\lnot \alpha\}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .