Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
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 6 '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 6 '10 at 16:51
@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 6 '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 6 '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 6 '10 at 17:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.