Union of sets and set satisfiability and tautologies

1k Views Asked by At

I was troubled with these two questions: I have to prove/refute many statements, but only two of which troubled me:

(1) If $A ∪ B$ is satisfiable, then both $A$ and $B$ are satisfiable. I know for a fact that the other way around is not correct (the union of two satisfiable sets is not necessarily satisfiable). I have tried to disprove the statement with many examples, but so far no avail. Moreover, I have tried to prove the statement, yet it does not seem so right.

(2) β is a tautology if and only if for every $α, α ⊢_{} β$. I proved the first direction, however, the second one did not go as smoothly.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $\omega$ be a propositional evaluation such that $\omega\models A\cup B$. Then, per definition, for any $\alpha\in A\cup B$, we have $\omega\models\alpha$.

Note, that thus

  1. For all $\alpha\in A\subseteq A\cup B$: $\omega\models\alpha$, i.e. $\omega\models A$.
  2. For all $\alpha\in B\subseteq A\cup B$: $\omega\models\alpha$, i.e. $\omega\models B$.

The key point is here really that if a set is satisfiable, then all formulas in the set are simultaneously satisfiable, i.e. there is an evaluation such that all formulas from the set are true in this model.

So if $A\cup B$ is satisfiable, then all formulas from both $A$ and $B$ are satisfiable by at least one model.


For the second one, suppose $\alpha\models\beta$ for any $\alpha$. Thus also $\gamma\lor\neg\gamma\models\beta$ for some $\gamma$ (just setting $\alpha=\gamma\lor\neg\gamma$).

Now $\gamma\lor\neg\gamma\models\beta$ means that for every evaluation $\omega$, if $\omega\models\gamma\lor\neg\gamma$, then $\omega\models\beta$. But every evaluation $\omega$ fulfills $\omega\models\gamma\lor\neg\gamma$. Thus, every evaluation $\omega$ fulfills $\omega\models\beta$ and thus $\beta$ is a tautology.

The inverse direction is pretty straightforward as if $\beta$ is a tautology, then $\omega\models\beta$ for any evaluation $\omega$. Thus, for any $\alpha$, if $\omega\models\alpha$, then $\omega\models\beta$ anyway, so $\alpha\models\beta$.