Exercise 1.2.10 from Model Theory by Chang and Keisler.

Question

I am reading Model Theory by Chang and Keisler, and I am having some trouble with exercise 1.2.10, which asks me to prove that if $\Sigma \vdash \varphi$ for all $\varphi \in \Gamma$ and $\Sigma \cup \Gamma \vdash \theta$, then $\Sigma \vdash \theta$ for propositional logic. The result seems intuitively clear to me: if we can prove $\theta$ from $\Sigma$ and $\Gamma$ together, and if everything in $\Gamma$ can be proven from $\Sigma$, then $\Sigma$ itself is enough to prove $\theta$. However, I am having trouble giving a rigorous proof of this. I tried using the deduction theorem, but this only works for singleton sets, which $\Gamma$ might not be. I assume it can be proven fairly simply, but right now it escapes me.

If anyone can give a hint or a proof of this, that would be much appreciated. I would prefer to frame the proof in model-theoretic terms rather than purely logical terms.

Answer 1

While Ittay's proof is correct, it is grounded in proof theory: a key fact is that you can prepend the proofs of all the propositions you need from $\Gamma$ with the proof of $\theta$ from $\Gamma$ and get a proof of $\theta$ from $\Sigma$ alone. Since you asked for a more model-theoretic proof, I'll provide one here in some detail. (Also, since you asked for a model-theoretic proof, I'm considering the question as it applies to semantic consequence ("$\models$") rather than provability ("$\vdash$"). It is a theorem that the two notions coincide.)

In propositional logic, a "model" is an assignment of True or False to each propositional variable (essentially, a row of the truth table). If $M$ is such a "model," write $M \models \theta$ if the assignments in $M$ yield $\theta$ as a true sentence. If $\Sigma$ is a set of sentences, say $\Sigma \models \theta$ if, for all $M \models \Sigma$ (that is, $M\models \sigma$ for all $\sigma \in \Sigma$), $M \models \theta$. In words, $\Sigma \models \theta$ if, in every row of the truth table where all the axioms from $\Sigma$ hold, $\theta$ also holds.

In the preceding framework, assume that

1. $\Sigma \models \varphi$ for all $\varphi \in \Gamma$, and
2. $\Sigma \cup \Gamma \models \theta$.

We want to show $\Sigma \models \theta$. That is, if we fix an arbitrary "model" $M$ and assume $M \models \Sigma$, we want to show $M \models \theta$. From assumption 1, we know that $M \models \varphi$ for all $\varphi \in \Gamma$, i.e. $M \models \Gamma$. Since we've shows $M \models \Sigma \cup \Gamma$, assumption 2 yields $M \models \theta$, as desired.

Answer 2

If $\Sigma \cup \Gamma $ proves $\theta$, then there is a proof of $\theta$ using axioms from $\Sigma \cup \Gamma$. Since a proof is a finite thing, only finitely many sentences from $\Gamma$ participate in the proof. Call these $\gamma_1,\cdots ,\gamma_n$. Then $\Sigma \cup \{\gamma_1\wedge \cdots \wedge \gamma_n\}$ proves $\theta$, and since $\Sigma $ proves $\gamma_1\wedge \cdots \wedge \gamma_n$, you are done.