3
$\begingroup$

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What I'm trying to show is the case where $\Phi=\emptyset$, i.e. that if $\alpha$ is a proof then it must be a tautology, but without applying the soundness theorem directly.

A proof for the soundness theorem could go like this: let $\Phi\vdash\phi$, then there is a deduction $\phi_1,\ldots,\phi_n$ from $\Phi$ of $\alpha=\phi_n$. Each $\phi_k$ of the deduction is either a tautology, a member of $\Phi$ or the result of Modus Ponens of two previous $\phi_i$ and $\phi_j$. We can then show by strong induction on $k$ that $\Phi\vDash\phi_k$.

However, I don't quite see how we could apply this scheme to the case $\Phi=\emptyset$. Any idea? Or another way of showing it?

$\endgroup$
  • 3
    $\begingroup$ $\vdash \phi$ means that : there is a sequence of formulae such that the last formula is $\phi$ and that each formula in the sequence is a logical axiom or is derived from previous formulae in the sequence by modus ponens. So you have to apply induction on the derivation proving that (i) every log ax is a tautology and (ii) an application of mp preserves "tautologuesness". $\endgroup$ – Mauro ALLEGRANZA May 10 '15 at 9:34
  • $\begingroup$ Thanks @MauroALLEGRANZA, that answers my question - if you type it up as answer, you'll get my vote :) As I said in my comment to Bruno below, I'm aware of the abbreviation you mention, and of the so-called "weak soundness" theorem. I was just wondering if we could apply the same sketch of proof as for the "strong" soundness theorem, and you cleared that up for me. Thanks! $\endgroup$ – Demosthene May 10 '15 at 23:27
4
$\begingroup$

If we agree that "to have a proof of $\alpha$", i.e. $\vdash \alpha$, means :

there is a sequence of formulae $\phi_1, \ldots, \phi_n$ such that $\alpha=\phi_n$ and that formula in the sequence is a logical axiom or is derived from previous formulae in the sequence by modus ponens,

this amounts to the "special case" of derivation from assumptions : $\Phi \vdash \alpha$ with $\Phi=\emptyset$.

So, to prove the desired result, we have to apply induction on the derivation showing that :

(i) every logical axioms is a tautology, and

(ii) an application of modus ponens preserves "tautologuesness".

In conclusion, the proof is basically the same we have for the general case : we have only to "skip" from the induction the part : "... or is a member of $\Phi$".

$\endgroup$

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.