# Proving a logic statement using valuations.

Let $\Phi \subseteq L_{\Sigma}$ where $\Sigma$ is the set of all propositional symbols $p, q, r,\dots$ and $L_{\Sigma}$ de set of well formed formulas formed from $\Sigma$. Show that $\Phi \cup \{ \varphi_1,\dots, \varphi_n\} \models \psi$ implies $\Phi \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$

I tried to prove it using induction on $n$ but I got a little confused. Here is what I did:

Take a valuation $v$ such that $v \models \Phi$. What I want to see is that $v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$ also holds. If $n = 1$, then we have only two cases:

In the first one, $v \not \models \varphi_1$, so $v \models \varphi_1 \rightarrow \psi$ and we are done. The other possible case is where $v \models \varphi_1$. But then $v \models \Phi$ and $v \models \varphi_1$, so $v \models \Phi \cup \{ \varphi_1 \}$, and by hypothesis, then $v \models \psi$, so $v \models \varphi$ and $v \models \psi$, therefore, $v \models \varphi_1 \rightarrow \psi$.

Now this is where I got stuck. I don't know how to proceed from there. I tried to do the same thing distinguishing cases but I think it is wrong. Like before, there can be two cases: $v \models \varphi_{n+1}$ or $v \not \models \varphi_{n+1}$.

If the case is the latter, then $v \models \varphi_{n+1} \rightarrow \psi$, but can I use the induction hypothesis to conclude that $$v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \varphi_{n+1} \rightarrow \psi?$$ And again, if $v \models \varphi_{n+1}$ and having that $v \models \varphi_1 \rightarrow \dots \rightarrow \varphi_n \rightarrow \psi$, can I conclude that $$v \models \varphi_1\rightarrow \dots \rightarrow \varphi_n \rightarrow \varphi_{n+1} \rightarrow\psi?$$ Thank you very much for your help!

Minor edit I'm assuming that the conditional $\rightarrow$ associates to the right, that is, $\varphi_1 \rightarrow \varphi_2 \rightarrow \varphi_3 \equiv \varphi_1 \rightarrow\left( \varphi_2 \rightarrow \varphi_3 \right)$ and so on.

There is really no need to use induction for this!

Also, I'll prove that the implication goes both ways:

$\Phi \cup \{ \varphi_1,\dots, \varphi_n\} \models \psi$

iff (by definition of $\vDash$)

For any valuation $v$: If $v(\phi)=True$ for any $\phi \in \Phi$, and $v(\varphi_i)=True$ for any $1 \le i \le n$, then $v(\psi)=True$

iff (by pure logic)

For any valuation $v$: If $v(\phi)=True$ for any $\phi \in \Phi$, and if $v(\varphi_1) = True$, then if $v(\varphi_2) = True$, then if ..., then if $v(\varphi_n) = True$, then $v(\psi)=True$

iff (by semantics of $\rightarrow$)

For any valuation $v$: If $v(\phi)=True$ for any $\phi \in \Phi$, then $v(\varphi_1 \rightarrow (\varphi_2 \rightarrow\dots \rightarrow (\varphi_n \rightarrow \psi)))..)))) = True$

iff (by definition of $\vDash$)

$\Phi \models \varphi_1 \rightarrow (\varphi_2 \rightarrow\dots \rightarrow (\varphi_n \rightarrow \psi)))..)))$

• Sorry for the delay in accepting this and thank you very much for your answer! – user313212 Jun 18 '17 at 16:24
• @user313212 Glad I could help! :) – Bram28 Jun 18 '17 at 18:31

Note that the connective sequence $a\to b\to c\to d$ is implicily nested as $a\to\big(b\to(c\to d)\big)$.

Then your inductive step would be to equivate, for any $S,T$, these sequents: $$\begin{array}{rcl}S\cup \{\varphi_k\}&\models& T\\ S&\models&\big(\varphi_k\to T\big)\end{array}$$

So if you can prove that those two are semantically equivalent, then you will have proven the following iterations are all also equivalencies. \begin{align}\mathbf\Phi\cup\{\varphi_1\ldots\varphi_n\}~&\models~ \psi \\ \mathbf\Phi\cup\{\varphi_1\ldots\varphi_{n-1}\}~&\models~ (\varphi_n\to\psi) \\ &~~\vdots\\ \mathbf\Phi\cup\{\varphi_1\ldots\varphi_k\}~&\models~\Big(\varphi_{k+1}\to\big(\ldots(\varphi_n\to\psi)\!\!\!\cdots\!\!\!\big)\Big) \\ &~~\vdots\\ \mathbf\Phi~&\models~\Big(\varphi_1\to\big(\ldots(\varphi_n\to \psi)\!\!\!\cdots\!\!\!\big)\Big)\end{align}