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

71 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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$.