2
$\begingroup$

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 Answers 1

2

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

  • 0
    @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).2010-12-06