How to prove the following property of implication?

121 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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