Deduction Theorem Proof Explanation

Question

I can't comprehend what our Professor has wrote on the proof of Deduction Theorem.The Theorem: $$\Sigma \models \phi \rightarrow\psi\space\space\space iff\space\space\space\Sigma\cup\{\phi\}\models \psi $$

Proof:$(\Rightarrow)$ Suppose that $ I \models \Sigma \cup \{\phi\}$. we want to prove that $ I \models \psi$. By assumption $ I \models\phi\rightarrow\psi.$ Since $I\models \phi$, it follows that $I\models\psi$

Proof:$(\Leftarrow)$Suppose that $ I \models \Sigma $. we want to prove that $ I \models\phi\rightarrow\psi$. To show this, we need to show that if $I\models\phi$, then $I\models\psi$.So, assume that $I\models\phi$. In this case, we have $I\models\Sigma\cup\{\phi\} $, and so, by assumption, we have $I\models\psi$.

i know this might seem obvious to you, but we only learned about two sentences on the definition of entailment,and he refused to suggest a book, and i am stupid. (what we learned is this) Picture 1 Picture 2 Picture 3

Where i got stuck:

1)now in the $\Rightarrow$ direction. if i am understanding correctly the whole left side is assumed to be correct and the assumption is 1)if $I\models\Sigma$ then $I\models\phi\rightarrow\psi$, then he added an extra assumption that 2) $ I \models \Sigma \cup \{\phi\}$ and from assumption 2) he concluded that 3)$I\models\phi$ . why was he able to add assumption 2 on the same Model from what was assumed to be true? and what did he do next?

2)the $\Leftarrow$ direction. "we want to prove that $ I \models\phi\rightarrow\psi$. To show this, we need to show that if$I\models\phi$, then $I\models\psi$." where did this come from and why? He also said that "we have $I\models\Sigma\cup\{\phi\}$"where did this come from?

i feel like i am missing tons of information can someone organize the assumptions and where they come from and what entailment properties(we didn't learn any) where used?

Answer 1

Let me rehash some definitions here.

• For some set of sentences $\Sigma$ and an interpretation $I$, we say $I\models \Sigma$ if each sentence in $\Sigma$ is true in $I.$ Similarly for a sentence $\phi,$ $I\models \phi$ means $\phi$ is true in $I$.
• If $\Sigma$ is a set of sentences and $\phi$ is a sentence, then we say $\Sigma\models \phi$ if for any interpretation $I$ such that $I\models \Sigma,$ we have $I\models \phi$ (In english: if an interpretation satisfies $\Sigma$ then it must also satisfy $\phi.$) Notice this is an "if x, then y" statement, so to prove it you need to assume $x$ holds and then prove $y$. In other words we must assume $I\models \Sigma$ and then prove that $I\models \phi.$
• (Inductive definition of truth for implication). We have $I\models \phi\to \psi$ if either $I\not\models \phi$ or $I\models \psi.$

Now with that in mind:

1) The LHS we are assuming says that $\Sigma\models \phi\to \psi.$ Per our definition this means that for any $I$ such that $I\models\Sigma,$ we have $I\models \phi\to \psi.$ The RHS that we are to prove says $\Sigma\cup\{\phi\}\models \psi,$ which means that for any interpretation $I$ such that $I\models\Sigma\cup\{\phi\}$, we also have $I\models \psi.$ To prove this we need to assume $I\models\Sigma\cup\{\phi\}$ and then show on that assumption, that $I\models \psi.$

Here is the reasoning: Since $I\models \Sigma\cup\{\phi\},$ we have $I\models \Sigma.$ By our assumption on the LHS, this means $I\models \phi\to \psi,$ which means either $I\not\models\phi$ or $I\models \psi.$ However, since $I\models \Sigma\cup\{\phi\},$ $I\models \psi,$ so it can't be the case that $I\not\models \phi,$ and thus we have $I\models \psi.$

To make sure I directly answer to your question, he added the assumption because, as I alluded to above, what he was trying to show was an "if x then y" statement, and to show one of these, you assume x and then prove y.

2) "If $I\models \phi$ then $I\models \psi$" is just a way of saying that either $I\not\models \phi$ or $I\models \psi,$ which is the definition of truth of an implication. We have $I\models \Sigma\cup\{\phi\}$ since we have separately the assumption that $I \models \Sigma$ and that $I\models\phi,$ which together mean that $I\models \Sigma\cup\{\phi\}.$

Answer 2

In the $(\Rightarrow)$ direction, we assume that $\Sigma \models \phi\to\psi$ to be true, that is, we assume that every interpretation $I$ satisfying $\Sigma$, also satisfies $\phi\to\psi$.

Now, with this information, we need to prove that $\Sigma\cup\{\phi\}\models\psi$, that is, we need to prove that every interpretation $I$ that satisfies $\Sigma\cup\{\phi\}$ also satisfies $\psi$.

So, let $I$ be any interpretation such that $I(\alpha) = 1$ for every $\alpha$ in $\Sigma\cup\{\phi\}$. Then, since $\phi$ is in $\Sigma\cup\{\phi\}$, we have $I(\phi) = 1$ and since $I$ satisfies any other formula in $\Sigma$, by assumption, $I$ must be satisfies $\phi\to\psi$, i.e. $I(\phi\to\psi) = 1$.

Now, it is clear that $I(\phi) = 1$ and $I(\phi\to\psi) = 1$ implies that $I(\psi) = 1$, as desired.