8

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

le4m
  • 3,006
  • 2
    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$). – Mauro ALLEGRANZA Mar 20 '14 at 07:31
  • 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 – Willemien Mar 20 '14 at 19:07
  • @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. – Willemien Mar 21 '14 at 06:13

1 Answers1

7

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

Peter LeFanu Lumsdaine
  • 9,434
Doug Spoonwood
  • 11,211
  • This is incorrect. – Andrés E. Caicedo Mar 19 '14 at 23:01
  • 1
    @AndresCaicedo: What is wrong with it (except for the implicit assumption that $\Sigma$ proves neither statement)? – hmakholm left over Monica Mar 19 '14 at 23:18
  • 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). – Andrés E. Caicedo Mar 19 '14 at 23:52
  • If Σ ⊢ c, where c is any contingent proposition, then the soundness theorem fails. – Doug Spoonwood Mar 20 '14 at 01:58
  • @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. – Doug Spoonwood Mar 20 '14 at 02:03
  • @DougSpoonwood Yes, you are right. I suspect that's a typo and the OP forgot to include that each $\alpha_i$ could also be an instance of a propositional axiom. Thanks for clarifying, though. – Andrés E. Caicedo Mar 20 '14 at 02:06
  • Sorry about that. $\alpha_i$ can definitely be a tautology. – le4m Mar 20 '14 at 05:29
  • A question. For your solution to work I guess $\Sigma$ should be empty? – le4m Mar 20 '14 at 05:40
  • @julypraise No, Σ doesn't have to not have any members. Suppose Σ to be {CCpqCCqrCpr, CCNppp, CpCNpq} (which is an axiom set for C-N... conditional-negation classical logic in Polish notation... the argument will work for any axiom set for classical logic). This argument will still work. – Doug Spoonwood Mar 20 '14 at 15:46
  • @MauroALLEGRANZA I'm not sure I follow you. I was thinking about the lines of using ϕ→(ψ→ϕ) at first also, but we want Σ⊢ϕ→φ to fail here. So, we do NOT want φ as a tautology. – Doug Spoonwood Mar 20 '14 at 15:48
  • 1
    @DougSpoonwood: I have heavily edited your answer — I hope you don’t mind. Partly for a minor correction (it isn’t enough just for $p$ and $q$ to each be contingent, they also need to be independent of each other) but mainly for style, since from comments it looks like I wasn’t the only one who found your original answer a bit unclear to read. The essential content of the counterexample is unchanged, though. – Peter LeFanu Lumsdaine Mar 20 '14 at 22:00