0
$\begingroup$

The problem goes like this:

Let $\Delta$ be a set of wffs such that (i) every finite subset of $\Delta$ is satisfiable, and (ii) for every wff $\alpha$, either $\alpha\in\Delta$ or $\neg\alpha\in\Delta$. Define the truth assignment $v$: $v(A)=T$ iff $A\in\Delta$, $v(A)=F$ iff $A\not\in\Delta$ for each sentence symbol $A$. Show that for every wff $\varphi$, $\bar{v}(\bar{\varphi})=T$ iff $\varphi\in\Delta$.

I tried to prove it by contradiction or contrapositive, but I always ended up showing finite satisfiability of finite subset that includes $\varphi$ with the given truth assignment which is absurd because finite satisfiability doesn't depend on a special truth assignment; one needs to consider all the possible truth assignments to decide the finite satisfiability. How should one prove this problem?

$\endgroup$

1 Answer 1

0
$\begingroup$

By induction on the complexity of $\varphi$.

Base case: $\varphi$ is a sentence symbol $A$. Then, by def of $v$: $v(\varphi)=v(A)= \text T$ iff $A \in \Delta$.

Induction step: for simplicity, consider two basic connectives only: $\lnot, \lor$.

Let $\varphi, \psi$ such that the property holds and let $\sigma := \lnot \varphi$.

We have that $\overline v(\sigma)=\overline v(\lnot \varphi)= \text T$ iff $\overline v(\varphi)=\text F$. And this, by hypothesis: iff $\varphi \notin \Delta$.

By (ii) we have that: if $\varphi \notin \Delta$, then $\lnot \varphi \in \Delta$.

Thus, so far we have: if $\overline v(\varphi)=\text F$, then $\lnot \varphi \in \Delta$.

Now assume that $\lnot \varphi \in \Delta$. By (i) $\Delta$ is consistent. Thus $\varphi \notin \Delta$.

And by the argument above we have $\overline v(\varphi)=\text F$.

Same for $\sigma := (\varphi \lor \psi)$.

$\endgroup$

You must log in to answer this question.

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