0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ One usually uses $\to$ in that place instead of $\implies$. $\endgroup$ – Kenny Lau Dec 29 '17 at 1:03
  • 1
    $\begingroup$ 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. $\endgroup$ – DanielV Dec 29 '17 at 6:22
  • 1
    $\begingroup$ Note that it only meaningful when $S$ is finite, so it's not just "for the sake of the argument". =) $\endgroup$ – user21820 Dec 29 '17 at 6:40
  • 1
    $\begingroup$ Not necessarily; see Raul Hakli & Sara Negri, Does the deduction theorem fail for modal logic ? (2012) $\endgroup$ – Mauro ALLEGRANZA Dec 29 '17 at 8:26
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)]
$\endgroup$
  • $\begingroup$ You may want to edit to clarify what "n+1-2n-1" means. Is it just "−2n"? =) $\endgroup$ – user21820 Dec 29 '17 at 6:39
0
$\begingroup$

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

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

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.