My main aim is to prove or disprove that if $\Sigma \vdash \phi$ implies $\Sigma \vdash \varphi$ then $\Sigma \vdash \phi \to \varphi$ where $\Sigma$ donotes a set of sentences in propositional logic.

$\Sigma \vdash \phi$ means there is a deduction from $\Sigma$ where the deduction is a sequence $( \alpha_0 , \dots , \alpha_n)$ with $a_i$ is either in $\Sigma$ or a consequence of MP (that is, for some $j,k<i$ $\alpha_k = \alpha_j \to \alpha_i$ and $\alpha_i$ follows from them) or a tautology.

I'm completely stuck now. I tried to prove it but have no idea on how to bring $\phi$ to a deduction sequence. And I also tried to make a counterexmaple but no simple one I could find.

Even in my mere intuition, I cannot clearly judge whether it is true or false.

(I also thought of employing Completeness and Soundness Thm..)

  • 2
    $\begingroup$ Have we some informations about the set of axioms and rules ? i.e.is the classical (Hilbert-style) system for propositional logic (like Mendelson's one) ? If we do not have these kind of information, I thin we are not licensed to use in the argument the concepts of tautology or completeness; we may only use the "general" properties of the derivation relation ($\vdash$). $\endgroup$ – Mauro ALLEGRANZA Mar 20 '14 at 7:31
  • $\begingroup$ it all depents on what is in $ \Sigma $ if s is just $ { P, Q} $ (two independent propositions) then you cannot really proof $ P \to Q $ because there is just nothing else to prove. but probably $ \Sigma $ contains also some axioms of axiomschemes, and then it depends on what the axiomschemes are $\endgroup$ – Willemien Mar 20 '14 at 19:07
  • $\begingroup$ @MauroALLEGRANZA But what if weakening ( $ \varphi \to (\phi \to \varphi ) $ ) is not an element of $ \Sigma $ ? (we have no reason to assume it is) but it looks the OP has abadomed this question so i guess we will never know. $\endgroup$ – Willemien Mar 21 '14 at 6:13

Take Σ here to be just the axioms of propositional logic, and take $\phi$ to be some propositional atom $p$. Then Σ ⊢ $\phi$ is false, and thus "Σ ⊢ $\phi$ implies Σ ⊢ $\varphi$" is true for any $\varphi$. Now take $\varphi$ to be some other atom $q$. $[p \rightarrow q]$ is not a tautology. If a formula is not a tautology, then it is not provable from Σ, because of the soundness metatheorem. So, Σ ⊢ $(\phi \rightarrow \varphi)$ is false. Thus, "if Σ ⊢ ϕ implies Σ ⊢ φ then Σ ⊢ $(\phi \rightarrow \varphi)$" is false in general.

(In fact $p,q$ need not be atoms; they can be taken to be any independent formulas. That is, formulas such that for each pair of truth values $(b_1,b_2)$, there is at least one valuation for which $p$ and $q$ take values $b_1$ and $b_2$ respectively.)

  • $\begingroup$ This is incorrect. $\endgroup$ – Andrés E. Caicedo Mar 19 '14 at 23:01
  • 1
    $\begingroup$ @AndresCaicedo: What is wrong with it (except for the implicit assumption that $\Sigma$ proves neither statement)? $\endgroup$ – hmakholm left over Monica Mar 19 '14 at 23:18
  • $\begingroup$ Ah, sorry, I read the problem incorrectly. Anyway, Doug, for clarity, you may want to indicate what your $\Sigma$ is (it could be empty, but something needs to be said). $\endgroup$ – Andrés E. Caicedo Mar 19 '14 at 23:52
  • $\begingroup$ If Σ ⊢ c, where c is any contingent proposition, then the soundness theorem fails. $\endgroup$ – Doug Spoonwood Mar 20 '14 at 1:58
  • $\begingroup$ @AndresCaicedo Σ almost surely can't be empty for this problem, because the only presumed rule is modus ponendo ponens "Here Σ⊢ϕ means there is a deduction from Σ where the deduction is a sequence (α0,…,αn) with ai is either in Σ or implication αj→αk or a consequence of MP," and it seems likely that we're talking about classical logic here. $\endgroup$ – Doug Spoonwood Mar 20 '14 at 2:03

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.