0

I know the mechanism of discharge of assumption in propositional logic. However, I wonder this kind of assumptions could be discharged: $$\begin{array}{llll} \text{Used premises}&\text{Line}&\text{Proposition}&\text{Used rule}\\\hline Pr_2,Pr_3&(10)&\varphi&\text{by some rule}\\ \vdots&\vdots&\vdots\\ Pr_1,Pr_2,Pr_3,Pr_4&(16)&\psi&\text{by some rule}\\ Pr_1,Pr_4(\star)&(17)&\varphi\rightarrow\psi&\text{CP(10)-(16)}\end{array}$$ (where in $\star$ we removed the premises which are $\varphi$'s). I think this kind of discharge would make something wrong. But I can't find an easy counterexample. Also, I'm curious if there is a quite intuitive explanation that this rule is misused.

Eric
  • 4,517
  • 1
  • 18
  • 36
  • See what happens if you require that the order of premiss introduced gets noted. – Doug Spoonwood May 28 '17 at 01:06
  • I think not; in line (16), by soundness, we have that $\psi$ is logical cons of $Pr_1, \ldots, Pr_4$. We may have that $Pr_2$ and $Pr_3$ are "necessary" in the sense taht removing them it is no longer true that $\psi$ is log cons of $Pr_1$ and $Pr_4$ alone. Thus, we may imagine a "scenario" with only $Pr_1$ and $Pr_4$ as premises where $\varphi$ is true while $\psi$ is false. – Mauro ALLEGRANZA May 31 '17 at 11:18
  • Counter-example: $Q,R \vdash Q$ (line 10); $P,Q,R,S \vdash P \land Q$ (line 16); $P,S \vdash P \to P \land Q$ (line 17). – Mauro ALLEGRANZA May 31 '17 at 11:25
  • @MauroALLEGRANZA I think I understand the spirit of your counterexample. But I just come up with a question that I also thought of before posting: I know the artificial step like "$Q,R \vdash Q$" is sound. However, can it happen that we "naturally" derive something like "$Q,R \vdash Q$" in a step among a proof? Since the premise $R$ wasn't made use. In other words, by sequences of natural deduction rules, would it naturally occur something like "$Q,R \vdash Q$" during a step of a concrete proof? – Eric May 31 '17 at 12:49
  • What does it mean "naturally" ? Logic is formal and a rule is valid when it licenses true conclusion from true premises "under all circumstances" (i.e. with respect to every interpretations). – Mauro ALLEGRANZA May 31 '17 at 13:07

1 Answers1

0

I don't know what precisely your notation means, but I imagine it can be settled by noting the key property of implication is

$A,B \vdash C$ if and only if $A \vdash B \to C $

So, for example, if you show that

$$ P_1, P_2, P_3, P_4 \vdash \psi $$

you can indeed infer

$$ P_1, P_4 \vdash (P_2 \wedge P_3) \to \psi \qquad \qquad (\star)$$

However, if you have also shown

$$ P_2, P_3 \vdash \varphi $$

then you cannot, in general, continue on to infer

$$ P_1, P_4 \vdash \varphi \to \psi $$

The other way around is fine though: if you instead had shown

$$ \varphi \vdash P_2 \wedge P_3 $$

then $\varphi \to (P_2 \wedge P_3)$ is a tautology, and together with $\star$ you can infer

$$ P_1, P_4 \vdash \varphi \to \psi $$