Proof in propositional logic involving deduction rule

Question

I want to prove the following:

Let $\gamma_1,\gamma_2,...,\gamma_n$ be finitely many formulas and $\phi$ a formula. Show that $\gamma_1,\gamma_2,...,\gamma_n\vDash\phi$ if and only if $\vDash((\gamma_1\wedge\gamma_2\wedge...\wedge\gamma_n)\to\phi)$.

I think I will have to use the deduction rule to do this, but I cannot see a way of using it with the statement as is.

Answer 1

Hint for forward direction:

We note the following:

$$(\phi\to(\psi\to\theta))\equiv((\phi\wedge\psi)\to\theta)$$

The proof will follow by induction on finitely many applications of the deduction rule.

Hint for reverse direction:

This is easier. Note the following two things:

1. We have, $\gamma_1,\gamma_2,...,\gamma_n\vDash(\gamma_1\wedge\gamma_2\wedge...\wedge\gamma_n)$.
2. Also, if $\Gamma\vDash\phi$ and $\phi\vDash\psi$, then $\Gamma\vDash\psi$.

The proof follows naturally.

Answer 2

If by 'deduction rule' you mean the Deduction Theorem ... I would try to avoid that if you can.

First of all, the Deduction Theorem is really about provability (it says: if $\gamma_1,\gamma_2,...,\gamma_{n-1},\gamma_n\vdash\phi$, then $\gamma_1,\gamma_2,...,\gamma_{n-1} \vdash \gamma_n \rightarrow \phi$), rather than about logical entailment. Of course, for sound and complete systems we have that $\Sigma \vDash \phi$ iff $\Sigma \vdash \phi$, but still .. the result you have to prove is about $\vDash$, not $\vdash$

Second, as @quanticbolt points out: if you do use the Deduction Theorem, you'd need to use the Deduction Theorem multiple times ... and even then you'd need to exploit a logical equivalence

Third, by doing a direct proof that uses the very notion of entailment, you can 'iff' the whole way through. Here's a start:

$\gamma_1,\gamma_2,...,\gamma_{n-1},\gamma_n\vDash\phi$

iff (by defiition of $\vDash$)

it is impossible for all of $\gamma_1,\gamma_2,...,\gamma_{n-1},\gamma_n$ to be true, and $\phi$ to be false

iff (by semantics of $\land$)

it is impossible for all of $\gamma_1 \land \gamma_2 \land ...\land \gamma_{n-1} \land \gamma_n$ to be true, and $\phi$ to be false

iff ... (two more steps ... use semantics of $\rightarrow$, and use definition of $\vDash$)