2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess that going from $M \models \Sigma \cup \Gamma$ and $\Sigma \cup \Gamma \models \theta$ to $M \models \theta$ uses some kind of transitivity of $\models$? I haven't seen this yet. $\endgroup$ – mrp Oct 27 '15 at 7:35
  • $\begingroup$ @mrp No special transitivity property; everything I did was directly from definitions. "$\Sigma \cup \Gamma \models \theta$" is defined as "every model of $\Sigma \cup \Gamma$ is also a model of $\theta$." $\endgroup$ – user231101 Oct 27 '15 at 11:53
  • 1
    $\begingroup$ Ah, I see. $\Sigma \cup \Gamma \models \theta$ is qualitatively different from $M \models \theta$, because $M$ is a model whereas $\Sigma \cup \Gamma$ is not. $\endgroup$ – mrp Oct 27 '15 at 12:29
4
$\begingroup$

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.

$\endgroup$

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.