Provability vs. implication?

134 Views Asked by At

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

3

There are 3 best solutions below

0
On

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

1
On

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)
    n+1-??. adjoin the proof given
    ??.     ϕ
??+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)]
2
On

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