The question with which I am struggling is the following,

Question. Let $\Gamma$ be a consistent set of wffs of propositional calculus (see the axioms and rule of inference below). Let $\alpha,\beta$ be two wffs. If $\Gamma\nvdash\alpha$ and $\Gamma\nvdash\beta$, is it possible to have $\Gamma\vdash\alpha\to\beta$?

The axioms and rules of inference are (here $P,Q$ and $S$ are arbitrary formulas),

$\color{crimson}{\text{Axiom 1.}}\ P\to (Q\to P)$

$\color{crimson}{\text{Axiom 2.}}\ (S\to (P\to Q))\to((S\to P)\to (S\to Q))$

$\color{crimson}{\text{Axiom 3.}}\ (\neg Q\to\neg P)\to(P\to Q)$

$\color{crimson}{\text{Rule of Inference.}}$ Modus Ponens.

My Attempt

I tried by assuming on the contrary that $\Gamma\nvdash\alpha\to\beta$ and then extending $\Gamma$ to a maximal consistent set $\Delta$ such that $\Delta\nvdash\alpha\to\beta$. I have also noted that $\Delta\vdash\alpha$ and $\Delta\nvdash\beta$ as well. But I can't find any contradiction.


Yes, it is possible to have $\Gamma \vdash \alpha \to \beta$, for suitable formulas $\alpha, \beta$.

Indeed, since $\Gamma$ is consistent, there exists a formula $\alpha$ such that $\Gamma \not\vdash \alpha$. Take $\beta = \alpha$. Thus, $\Gamma \not\vdash \beta$ but $\Gamma \vdash \alpha \to \beta$, as you can see here for a derivation in Hilbert system.

Note that the statement "if $\Gamma$ is consistent and $\alpha,\beta$ are formulas such that $\Gamma \not\vdash \alpha$ and $\Gamma \not\vdash \beta$, then $\Gamma \vdash \alpha \to \beta$" is false for arbitrary formulas $\alpha, \beta$ and arbitrary $\Gamma$. For instance, if $\alpha, \beta$ are two distinct propositional variables and $\Gamma$ is the empty set of formulas, then $\Gamma$ is consistent, $\Gamma \not\vdash \alpha$ and $\Gamma \not\vdash \beta$ but $\Gamma \not\vdash \alpha \to \beta$.

  • $\begingroup$ What properties of Γ would ensure that for arbitrary formulas $α,β$ that if $Γ⊬α$ and $Γ⊬β$ then $Γ\vdash α→β$ as well? $\endgroup$ – user170039 Mar 19 '20 at 4:47
  • $\begingroup$ I think if $\Gamma$ is maximal consistent then we have the required thing. $\endgroup$ – user170039 Mar 19 '20 at 5:58
  • $\begingroup$ @user170039 - Exactly! Do you have a proof? Hint: if $\Gamma$ is maximally consistent then it is complete (i.e. for every formula $\alpha$, either $\Gamma \vdash \alpha$ or $\Gamma \vdash \lnot \alpha$). $\endgroup$ – Taroccoesbrocco Mar 19 '20 at 7:53
  • 1
    $\begingroup$ Yep. I do have a proof. If $\Gamma$ is maximal consistent and $\Gamma\nvdash\alpha$ then we have $\alpha\notin\Gamma$. Hence $\Gamma\cup\{\alpha\}$ is inconsistent. Hence we have $\Gamma\cup\{\alpha\}\vdash\beta$. Applying DT $\Gamma\vdash\alpha\to\beta$. $\endgroup$ – user170039 Mar 19 '20 at 8:26
  • $\begingroup$ @user170039 - Perfect! $\endgroup$ – Taroccoesbrocco Mar 19 '20 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy