# If $\Sigma \vdash \phi$ implies $\Sigma \vdash \varphi$ then $\Sigma \vdash \phi \to \varphi$ on propositional logic?

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

• 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 7: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 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.)
• @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