I'm currently reading Artificial Intelligence, by Russel & Norvig. They state that:

A) A sentence is valid if it is true in all models

B) The deduction theorem: "For any sentences $\alpha$ and $\beta$, $\alpha \models \beta$ if and only if ($\alpha \implies \beta$) is valid.

My mental blockage consists of the fact that implication is False if $\alpha = T$ and $\beta = F$ -- thus resulting in one model that is not true. But, in order for ($\alpha \implies \beta$) to be valid, it has to be true for all models.

What is it I'm missing?


1 Answer 1


In order for $\alpha\Rightarrow\beta$ to be valid, it must hold in all models; for $\alpha\Rightarrow\beta$ to not be valid, there must be a model where it is false. If there is a model where it is false, then there is a model in which $\alpha$ is true but $\beta$ is false, which means that $\alpha\models\beta$ does not hold.

Remember: you are proving an implication. You are trying to prove that if $\alpha\models\beta$, then $\alpha\Longrightarrow \beta$ is valid. You are not trying to prove that $\alpha\Longrightarrow\beta$ is valid in all cases.

(Of course, you also need to prove the converse: if $\alpha\Longrightarrow\beta$ is valid, so that it holds in all models, then you need to show that $\alpha\models\beta$ holds).

  • $\begingroup$ Thanks for the reply! I'm almost there. So, I need to divide the proof into two parts? One that shows that for the models where $\alpha \models \beta$ then $\alpha \implies \beta$ is valid? And one that shows that if $\alpha \implies \beta$ is valid for all models (for example if $\beta = \alpha$), then $\alpha \models \beta$? $\endgroup$
    – E.E.
    Dec 6, 2010 at 16:40
  • $\begingroup$ @E.E. Exactly. In general, when you prove an "if and only if" statement, splitting the two directions is the way to go. $\endgroup$ Dec 6, 2010 at 16:51
  • 1
    $\begingroup$ @E.E. Two things: Generally, yes; as Mark Reitblatt says, proving an "if and only if" is usually easiest by splitting it into two implications, one going each way, and establishing each separately (though on some occassions one can do the two implications "at the same time" if each step in the chain of reasoning is reversible). But you are not quite correct: it's not "for the models where $\alpha\models\beta$". Remember the meaning of $\alpha\models\beta$. You will assume that $\alpha\models\beta$ is true (so that in every model in which $\alpha$ holds, $\beta$ necessarily holds). $\endgroup$ Dec 6, 2010 at 16:54
  • $\begingroup$ Ahh yes. One functions as the axiom, and you prove the second based on that one, right? Thanks! $\endgroup$
    – E.E.
    Dec 6, 2010 at 17:01
  • $\begingroup$ @E.E.: Essentially yes, though one calls it the "premise", not "the axiom". It's really an application of the rule that tells you that $P\vdash Q$ if and only if (there is it again!) $\vdash P\rightarrow Q$. Douglas Hofstadter calls it "the Fantasy Rule" in Gödel, Escher, Bach: an Eternal Golden Braid, because instead of having to prove $P\rightarrow Q$ from nothing, you can "fantasize" that you know $P$ is true and prove $Q$ from that instead (which is usually easier, because you have more to play with). $\endgroup$ Dec 6, 2010 at 17:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .