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

  • $\begingroup$ Sorry for the delay in accepting this and thank you very much for your answer! $\endgroup$ – user313212 Jun 18 '17 at 16:24
  • $\begingroup$ @user313212 Glad I could help! :) $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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