# Is $\{ \delta \mid \Sigma \vdash \delta \} \cup \{ \delta \mid T \vdash \delta \} = \{ \delta \mid \Sigma \cup T \vdash \delta \}$?

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 \}?$$

• What did you try? Where did you get stuck? – 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$.
• 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. – Stefan Mesken Nov 4 '16 at 0:47