a set of sentences is satisfiable under two valuations iff every finite subset of it is satisfiable under two valuations

44 Views Asked by At

Let $\varGamma$ be a set of sentences.
We say that HS($\varGamma$) if there are two valuations P1 and P2 such that for every $\theta$ $\in$ $\varGamma$:
The value of $\theta$ under P1 is True or The value of $\theta$ under P2 is True.
Prove or disprove: HS($\varGamma$) iff for every finite $\Delta$ $\subseteq$ $\varGamma$ it's true that HS($\Delta$)
PS: $\varGamma$ may be an infinite set.

1

There are 1 best solutions below

0
On

For each propositional variable $p$ that occurs in $\Gamma$, let $p'$ be a new propositional variable. For each $\theta\in\Gamma$, obtain $\theta'$ by replacing every propositional variable in $\theta$ by its primed version. Then HS$(\Gamma)$ is equivalent to satisfiability of $\{\theta\lor\theta':\theta\in\Gamma\}$. So your result follows by applying the compactness theorem to this $\{\theta\lor\theta':\theta\in\Gamma\}$.