2

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?

E.E.
  • 123

1 Answers1

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

Arturo Magidin
  • 398,050
  • 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$?

     – E.E. Dec 06 '10 at 16:40
  • @E.E. Exactly. In general, when you prove an "if and only if" statement, splitting the two directions is the way to go. – Mark Reitblatt Dec 06 '10 at 16:51
  • 1
    @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). – Arturo Magidin Dec 06 '10 at 16:54
  • Ahh yes. One functions as the axiom, and you prove the second based on that one, right? Thanks! – E.E. Dec 06 '10 at 17:01
  • @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). – Arturo Magidin Dec 06 '10 at 17:04