# Provability vs. implication?

For any logic we have an is provable from relation denoted by $S \vdash \phi$ where $S$ is a (for the sake of the argument lets say) finite set of sentences and $\phi$ is a sentence.

Is the following “meta-theorem” valid?

$S\vdash \phi\quad \text{ iff } \quad \emptyset \vdash \left(\bigwedge S \implies \phi\right)$ where $\bigwedge S$ is the conjunction of all sentences in $S$.

(Assume that the logic in question has the deductive system capable of handling the conjunction and the implication in the usual way.)

• One usually uses $\to$ in that place instead of $\implies$. – Kenny Lau Dec 29 '17 at 1:03
• That is more or less called the deduction theorem. Most logics either have that an axiom or are specifically designed to make that statement true. – DanielV Dec 29 '17 at 6:22
• Note that it only meaningful when $S$ is finite, so it's not just "for the sake of the argument". =) – user21820 Dec 29 '17 at 6:40
• Not necessarily; see Raul Hakli & Sara Negri, Does the deduction theorem fail for modal logic ? (2012) – Mauro ALLEGRANZA Dec 29 '17 at 8:26

I think so.

Given $S \vdash \phi$, we prove $\bigwedge S \Rightarrow \phi$ by using a law of implication introduction / conditional proof by assuming $\bigwedge S$, deriving the sentences in $S$, then using $S \vdash \phi$ to get $\phi$, and finally applying the law of implication introduction (with the details depending on the particular logical system).

Conversely, given $\emptyset \vdash (\bigwedge S \Rightarrow \phi)$, we assume $S$, conjoin the sentences to derive $\bigwedge S$, also derive $\bigwedge S \Rightarrow \phi$ (for free), and then use modus ponens to derive $\phi$.

Assume $S \vdash \phi$.

Now, I claim that $\varnothing \vdash \bigwedge S \to \phi$, because I can create the following proof:

    1.      ⋀S   [assumption]
2-n.    (decomposes the wedge)
??.     ϕ
??+1. ⋀S→ϕ [→intro]


Assume $\varnothing \vdash \bigwedge S \to \phi$.

Now, I claim that $S \vdash \phi$, because I can create the following proof:

1-n.      (restatement of the premises)
n+1-2n-1. (conjunction of the restatements into ⋀S)
2n.       ⋀S
2n+1-???. (copy the proof of ⋀S→ϕ)
???.      ⋀S→ϕ
???+1.    ϕ   [modus ponens (aka →elim)]

• You may want to edit to clarify what "n+1-2n-1" means. Is it just "−2n"? =) – user21820 Dec 29 '17 at 6:39

This is clear from the Soundness and Completeness theorems. (Since it's more or less obvious that $S\models \phi$ if and only if $\models \bigwedge S\implies \phi$.)

• But your proof requires the theory to be that of a first-order. – Kenny Lau Dec 29 '17 at 1:16
• @KennyLau Well, yes - I assumed that was what we were talking about. – David C. Ullrich Dec 29 '17 at 13:28