Justify the truth or the falseness of the following sentence. If the sentence is false, you can present a counterexample.

Let $\Sigma$ and $T$ be two sets of propositional logic formulas. Is it always true that $$ \{ \delta \mid \Sigma \vdash \delta \} \cup \{ \delta \mid T \vdash \delta \} = \{ \delta \mid \Sigma \cup T \vdash \delta \}? $$

  • $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – Noah Schweber Nov 4 '16 at 0:43

Note that $$ \{ \delta \mid \Sigma \vdash \delta \} \cup \{ \delta \mid T \vdash \delta \} \subseteq \{ \delta \mid \Sigma \cup T \vdash \delta \}. $$ Why is that? Well, if $\delta$ is provable from $\Sigma$, then it is provable from any larger theory. So it is provable from $\Sigma \cup T$. (Similarly if $\delta$ is provable from $T$.)

However, the other inclusion doesn't hold in general. To see this let $\{ v_n \mid n \in \mathbb N \}$ be your set of propositional variables and let $\Sigma = \{ v_{1} \}$ and $T = \{ v_{2} \}$. Now $\Sigma \cup T \vdash v_{1} \wedge v_{2}$ but $\Sigma \not \vdash v_{1} \wedge v_{2}$ and $T \not \vdash v_{1} \wedge v_{2}$. It should be clear that $\Sigma \cup T \vdash v_{1} \wedge v_{2}$, so let me prove that $\Sigma \not \vdash v_{1} \wedge v_{2}$ (virtually the same proof yields $T \not \vdash v_{1} \wedge v_{2}$).

Let $I \colon \{ v_n \mid n \in \mathbb N \} \to \{0,1\}$ be such that $I(v_1) = 1$ and $I(v) = 0$ for all other $v$. Clearly $v_1 [I]$ and $\neg v_2 [I]$, i.e. $\Sigma[I]$ is true, but $v_1 \wedge v_2[I]$ is false. By soundness this yields that $\Sigma \not \vdash v_1 \wedge v_2$.

  • 1
    $\begingroup$ Note the usefulness of soundness in this particular example. In general - demonstrating that some formula $\phi$ cannot be proved from a given set of assumptions is really hard. Soundness allows us to instead provide a model that satisfies the given set of assumptions, but doesn't satisfy $\phi$ - which is almost trivial. $\endgroup$ – Stefan Mesken Nov 4 '16 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.