Are $A, B, C \vdash D$ and $A, B\vdash C \rightarrow D$ interchangeable?

Question

For an assignment we have to make a proof in the Hilbert system. And my proof hinges on the following operation being allowed:

$A, B, C \vdash D\tag 1$

Becomming:

$A, B\vdash C \rightarrow D\tag 2$

Intuitively this makes sense, because $A$ is an assumption, so moving it to the right of the turnstile still requires it to hold.

Note: $A$ is not the only assumption made.

Answer 1

Yes, they are interchangeable in Hilbert's system (and indeed for any proof system that is sound and complete).

From

$A, B\vdash C \rightarrow D\tag 2$

to

$A, B, C \vdash D\tag 1$

is trivial: Start the proof with $A,B$, and $C$ as premises. Given (1), you can derive $C \rightarrow D$ from $A$ and $B$. And then do Modus Ponens using $C$ to get D.

From

$A, B, C \vdash D\tag 1$

to

$A, B\vdash C \rightarrow D\tag 2$

is of course much more interesting and challenging, but it always works.

The Deduction Theorem says that for any set of statements $\Gamma$, and statements $\varphi$ and $\psi$: if $\Gamma \cup \{ \varphi \} \vdash \psi$, then $\Gamma \vdash \varphi \rightarrow \psi$.

I would recommend looking up the Deduction Theorem, and a proof thereof. But the basic idea is to transform the derivation $\Gamma \cup \{ \varphi \} \vdash \psi$ into one that starts with just $\Gamma$ as its premises, and then for every statement $\chi$ that occurs in the derivation $\Gamma \cup \{ \varphi \} \vdash \psi$ will derive $\varphi \rightarrow \chi$ ... using induction you can show that you can always do this. And since the last line of the first derivation is $\psi$, the last line of the transformed derivation becomes $\varphi \rightarrow \psi$, and hence you're done.

Simple example:

Original derivation of $\{ P\rightarrow Q, Q \rightarrow R, P \} \vdash R$:

1. $P\rightarrow Q$ Premise

2. $Q\rightarrow R$ Premise

3. $P$ Premise

4. $Q$ MP 1,3

5. $R$ MP 2,4

Transform to $\{ P\rightarrow Q, Q \rightarrow R \} \vdash P \rightarrow R$:

1. $P\rightarrow Q$ Premise

2. $(P\rightarrow Q) \rightarrow (P \rightarrow (P\rightarrow Q))$ Axiom 1

3. $P \rightarrow (P\rightarrow Q)$ MP 1,2 ('Conditionalized' 1 from original derivation)

4. $Q\rightarrow R$ Premise

5. $(Q\rightarrow R) \rightarrow (P \rightarrow (Q\rightarrow R))$ Axiom 1

6. $P \rightarrow (Q\rightarrow R)$ ('Conditionalized' 2 from original derivation)

...

11. $P \rightarrow P$ (this takes a few steps to derive, but you've probably seen that proof. This is the conditionalized form of line 3 from original derivation)

12. $(P \rightarrow (P\rightarrow Q)) \rightarrow ((P \rightarrow P) \rightarrow (P \rightarrow Q))$ Axiom 2

13. $(P \rightarrow P) \rightarrow (P \rightarrow Q)$ MP 3,12

14. $P \rightarrow Q$ MP 11, 13 (all that work and we're actually back to premise 1 ... hey, no one said this process was the most efficient one! I just wanted to show you how this works in general ... and please note that now we have the conditionalized form of line 4 of the original derivation)

15. $(P \rightarrow (Q\rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow (P \rightarrow R))$ Axiom 2

16. $(P \rightarrow Q) \rightarrow (P \rightarrow R)$ MP 6,15

17. $P \rightarrow R$ MP 14, 16 (conditionalized form of line 5 of the original derivation)

So yeah, keep using Axioms 1 to conditionalize all premises and axioms, and axiom 2 to emulate all the inferences in the original derivation but where you infer the conditionalized form.