Deduction theorem

Inmathematical logic,adeduction theoremis ametatheoremthat justifies doingconditional proofsfrom a hypothesis in systems that do not explicitly axiomatize that hypothesis, i.e. to prove an implicationA→B,it is sufficient to assumeAas a hypothesis and then proceed to deriveB.Deduction theorems exist for bothpropositional logicandfirst-order logic.The deduction theorem is an important tool inHilbert-style deduction systemsbecause it permits one to write more comprehensible and usually much shorter proofs than would be possible without it. In certain other formal proof systems the same conveniency is provided by an explicit inference rule; for examplenatural deductioncalls itimplication introduction.

In more detail, the propositional logic deduction theorem states that if a formula$B$is deducible from a set of assumptions$\Delta \cup \{A\}$then the implication$A\to B$is deducible from$\Delta$;in symbols,$\Delta \cup \{A\}\vdash B$implies$\Delta \vdash A\to B$.In the special case where$\Delta$is theempty set,the deduction theorem claim can be more compactly written as:$A\vdash B$implies$\vdash A\to B$.The deduction theorem for predicate logic is similar, but comes with some extra constraints (that would for example be satisfied if$A$is aclosed formula). In general a deduction theorem needs to take into account all logical details of the theory under consideration, so each logical system technically needs its own deduction theorem, although the differences are usually minor.

The deduction theorem holds for all first-order theories with the usualdeductive systemsfor first-order logic.However, there are first-order systems in which new inference rules are added for which the deduction theorem fails.Most notably, the deduction theorem fails to hold inBirkhoff–von Neumannquantum logic,because thelinear subspacesof aHilbert spaceform anon-distributive lattice.

Examples of deduction

1. "Prove" axiom 1:P→(Q→P)

   • P1. hypothesis
     • Q2. hypothesis
     • P3. reiteration of 1
   • Q→P4. deduction from 2 to 3

   • P→(Q→P) 5. deduction from 1 to 4 QED
2. "Prove" axiom 2:

   • P→(Q→R) 1. hypothesis
     • P→Q2. hypothesis
       • P3. hypothesis
       • Q4. modus ponens 3,2
       • Q→R5. modus ponens 3,1
       • R6. modus ponens 4,5
     • P→R7. deduction from 3 to 6
   • (P→Q)→(P→R) 8. deduction from 2 to 7

   • (P→(Q→R))→((P→Q)→(P→R)) 9. deduction from 1 to 8 QED
3. Using axiom 1 to show ((P→(Q→P))→R)→R:

   • (P→(Q→P))→R1. hypothesis
   • P→(Q→P) 2. axiom 1
   • R3. modus ponens 2,1

   • ((P→(Q→P))→R)→R4. deduction from 1 to 3 QED

Virtual rules of inference

From the examples, you can see that we have added three virtual (or extra and temporary) rules of inference to our normal axiomatic logic. These are "hypothesis", "reiteration", and "deduction". The normal rules of inference (i.e. "modus ponens" and the various axioms) remain available.

1.Hypothesisis a step where one adds an additional premise to those already available. So, if your previous stepSwas deduced as:

$E_{1},E_{2},...,E_{n-1},E_{n}\vdash S,$

then one adds another premiseHand gets:

$E_{1},E_{2},...,E_{n-1},E_{n},H\vdash H.$

This is symbolized by moving from then-th level of indentation to then+1-th level and saying

• Sprevious step
  • Hhypothesis

2.Reiterationis a step where one re-uses a previous step. In practice, this is only necessary when one wants to take a hypothesis that is not the most recent hypothesis and use it as the final step before a deduction step.

3.Deductionis a step where one removes the most recent hypothesis (still available) and prefixes it to the previous step. This is shown by unindenting one level as follows:

• Hhypothesis
• ......... (other steps)
• C(conclusion drawn fromH)

• H→Cdeduction

Conversion from proof using the deduction meta-theorem to axiomatic proof

In axiomatic versions of propositional logic, one usually has among theaxiom schemas(whereP,Q,andRare replaced by any propositions):

• Axiom 1 is:P→(Q→P)
• Axiom 2 is: (P→(Q→R))→((P→Q)→(P→R))
• Modus ponens is: fromPandP→QinferQ

These axiom schemas are chosen to enable one to derive the deduction theorem from them easily. So it might seem that we are begging the question. However, they can be justified by checking that they aretautologiesusing truth tables and that modus ponens preserves truth.

From these axiom schemas one can quickly deduce the theorem schemaP→P(reflexivity of implication), which is used below:

1. (P→((Q→P)→P))→((P→(Q→P))→(P→P)) from axiom schema 2 withP,(Q→P),P
2. P→((Q→P)→P) from axiom schema 1 withP,(Q→P)
3. (P→(Q→P))→(P→P) from modus ponens applied to step 2 and step 1
4. P→(Q→P) from axiom schema 1 withP,Q
5. P→Pfrom modus ponens applied to step 4 and step 3

Suppose that we have that Γ andHtogether proveC,and we wish to show that Γ provesH→C.For each stepSin the deduction that is a premise in Γ (a reiteration step) or an axiom, we can apply modus ponens to the axiom 1,S→(H→S), to getH→S.If the step isHitself (a hypothesis step), we apply the theorem schema to getH→H.If the step is the result of applying modus ponens toAandA→S,we first make sure that these have been converted toH→AandH→(A→S) and then we take the axiom 2, (H→(A→S))→((H→A)→(H→S)), and apply modus ponens to get (H→A)→(H→S) and then again to getH→S.At the end of the proof we will haveH→Cas required, except that now it only depends on Γ, not onH.So the deduction step will disappear, consolidated into the previous step which was the conclusion derived fromH.

To minimize the complexity of the resulting proof, some preprocessing should be done before the conversion. Any steps (other than the conclusion) that do not actually depend onHshould be moved up before the hypothesis step and unindented one level. And any other unnecessary steps (which are not used to get the conclusion or can be bypassed), such as reiterations that are not the conclusion, should be eliminated.

During the conversion, it may be useful to put all the applications of modus ponens to axiom 1 at the beginning of the deduction (right after theH→Hstep).

When converting a modus ponens, ifAis outside the scope ofH,then it will be necessary to apply axiom 1,A→(H→A), and modus ponens to getH→A.Similarly, ifA→Sis outside the scope ofH,apply axiom 1, (A→S)→(H→(A→S)), and modus ponens to getH→(A→S). It should not be necessary to do both of these, unless the modus ponens step is the conclusion, because if both are outside the scope, then the modus ponens should have been moved up beforeHand thus be outside the scope also.

Under theCurry–Howard correspondence,the above conversion process for the deductionmeta-theoremis analogous to theconversion processfromlambda calculusterms to terms ofcombinatory logic,where axiom 1 corresponds to the K combinator, and axiom 2 corresponds to the S combinator. Note that the I combinator corresponds to the theorem schemaP→P.

Helpful theorems

If one intends to convert a complicated proof using the deduction theorem to a straight-line proof not using the deduction theorem, then it would probably be useful to prove these theorems once and for all at the beginning and then use them to help with the conversion:

$A\to A$

helps convert the hypothesis steps.

$(B\to C)\to ((A\to B)\to (A\to C))$

helps convert modus ponens when the major premise is not dependent on the hypothesis, replaces axiom 2 while avoiding a use of axiom 1.

$(A\to (B\to C))\to (B\to (A\to C))$

helps convert modus ponens when the minor premise is not dependent on the hypothesis, replaces axiom 2 while avoiding a use of axiom 1.

These two theorems jointly can be used in lieu of axiom 2, although the converted proof would be more complicated:

$(A\to B)\to ((B\to C)\to (A\to C))$

$(A\to (A\to C))\to (A\to C)$

Peirce's lawis not a consequence of the deduction theorem, but it can be used with the deduction theorem to prove things that one might not otherwise be able to prove.

$((A\to B)\to A)\to A$

It can also be used to get the second of the two theorems, which can be used in lieu of axiom 2.

Proof of the deduction theorem

We prove the deduction theorem in a Hilbert-style deductive system of propositional calculus.

Let$\Delta$be a set of formulas and$A$and$B$formulas, such that$\Delta \cup \{A\}\vdash B$.We want to prove that$\Delta \vdash A\to B$.

Since$\Delta \cup \{A\}\vdash B$,there is a proof of$B$from$\Delta \cup \{A\}$.We prove the theorem by induction on the proof lengthn;thus the induction hypothesis is that for any$\Delta$,$A$and$B$such that there is a proof of$B$from$\Delta \cup \{A\}$of length up ton,$\Delta \vdash A\to B$holds.

Ifn= 1 then$B$is member of the set of formulas$\Delta \cup \{A\}$.Thus either$B=A$,in which case$A\to B$is simply$A\to A$,which is derivable by substitution fromp→p,which is derivable from the axioms, and hence also$\Delta \vdash A\to B$,or$B$is in$\Delta$,in which case$\Delta \vdash B$;it follows from axiomp→ (q→p) with substitution that$\Delta \vdash B\to (A\to B)$and hence by modus ponens that$\Delta \vdash A\to B$.

Now let us assume the induction hypothesis for proofs of length up ton,and let$B$be a formula provable from$\Delta \cup \{A\}$with a proof of lengthn+1. Then there are two possibilities:

1. $B$is member of the set of formulas$\Delta \cup \{A\}$;in this case we proceed as forn=1.
2. $B$is arrived at by using modus ponens. Then there is a formulaCsuch that$\Delta \cup \{A\}$proves$C$and$C\to B$,and modus ponens is then used to prove$B$.The proofs of$C$and$C\to B$are with at mostnsteps, and by the induction hypothesis we have$\Delta \vdash A\to C$and$\Delta \vdash A\to (C\to B)$.By the axiom (p→ (q→r)) → ((p→q) → (p→r)) with substitution it follows that$\Delta \vdash (A\to (C\to B))\to ((A\to C)\to (A\to B))$,and by using modus ponens twice we have$\Delta \vdash A\to B$.

Thus in all cases the theorem holds also forn+1, and by induction the deduction theorem is proven.

The deduction theorem in predicate logic

The deduction theorem is also valid infirst-order logicin the following form:

• IfTis atheoryandF,Gare formulas withFclosed,and$T\cup \{F\}\vdash G$,then$T\vdash F\rightarrow G$.

Here, the symbol$\vdash$means "is a syntactical consequence of." We indicate below how the proof of this deduction theorem differs from that of the deduction theorem in propositional calculus.

In the most common versions of the notion of formal proof, there are, in addition to the axiom schemes of propositional calculus (or the understanding that all tautologies of propositional calculus are to be taken as axiom schemes in their own right),quantifier axioms,and in addition tomodus ponens,one additionalrule of inference,known as the rule ofgeneralization:"FromK,infer ∀vK."

In order to convert a proof ofGfromT∪{F} to one ofF→GfromT,one deals with steps of the proof ofGthat are axioms or result from application of modus ponens in the same way as for proofs in propositional logic. Steps that result from application of the rule of generalization are dealt with via the following quantifier axiom (valid whenever the variable vis not free in formulaH):

• (∀v(H→K))→(H→∀vK).

Since in our caseFis assumed to be closed, we can takeHto beF.This axiom allows one to deduceF→∀vKfromF→Kand generalization, which is just what is needed whenever the rule of generalization is applied to someKin the proof ofG.

In first-order logic, the restriction of that F be a closed formula can be relaxed given that the free variables in F has not been varied in the deduction of G from$T\cup \{F\}$.In the case that a free variable v in F has been varied in the deduction, we write$T\cup \{F\}\vdash ^{v}G$(the superscript in the turnstile indicating that v has been varied) and the corresponding form of the deduction theorem is$T\vdash (\forall vF)\rightarrow G$.

Example of conversion

To illustrate how one can convert a natural deduction to the axiomatic form of proof, we apply it to the tautologyQ→((Q→R)→R). In practice, it is usually enough to know that we could do this. We normally use the natural-deductive form in place of the much longer axiomatic proof.

First, we write a proof using a natural-deduction like method:

• Q1. hypothesis
  • Q→R2. hypothesis
  • R3. modus ponens 1,2
• (Q→R)→R4. deduction from 2 to 3

• Q→((Q→R)→R) 5. deduction from 1 to 4 QED

Second, we convert the inner deduction to an axiomatic proof:

• (Q→R)→(Q→R) 1. theorem schema (A→A)
• ((Q→R)→(Q→R))→(((Q→R)→Q)→((Q→R)→R)) 2. axiom 2
• ((Q→R)→Q)→((Q→R)→R) 3. modus ponens 1,2
• Q→((Q→R)→Q) 4. axiom 1
  • Q5. hypothesis
  • (Q→R)→Q6. modus ponens 5,4
  • (Q→R)→R7. modus ponens 6,3
• Q→((Q→R)→R) 8. deduction from 5 to 7 QED

Third, we convert the outer deduction to an axiomatic proof:

• (Q→R)→(Q→R) 1. theorem schema (A→A)
• ((Q→R)→(Q→R))→(((Q→R)→Q)→((Q→R)→R)) 2. axiom 2
• ((Q→R)→Q)→((Q→R)→R) 3. modus ponens 1,2
• Q→((Q→R)→Q) 4. axiom 1
• [((Q→R)→Q)→((Q→R)→R)]→[Q→(((Q→R)→Q)→((Q→R)→R))] 5. axiom 1
• Q→(((Q→R)→Q)→((Q→R)→R)) 6. modus ponens 3,5
• [Q→(((Q→R)→Q)→((Q→R)→R))]→([Q→((Q→R)→Q)]→[Q→((Q→R)→R))]) 7. axiom 2
• [Q→((Q→R)→Q)]→[Q→((Q→R)→R))] 8. modus ponens 6,7
• Q→((Q→R)→R)) 9. modus ponens 4,8 QED

These three steps can be stated succinctly using theCurry–Howard correspondence:

• first, in lambda calculus, the function f = λa. λb. b a has typeq→ (q→r) →r
• second, bylambda eliminationon b, f = λa. s i (k a)
• third, by lambda elimination on a, f = s (k (s i)) k

See also

• Cut-elimination theorem
• Conditional proof
• Currying
• Propositional calculus
• Peirce's law

References

• Carl Hewitt(2008), "ORGs for Scalable, Robust, Privacy-Friendly Client Cloud Computing",IEEE Internet Computing,12(5): 96–99,doi:10.1109/MIC.2008.107,S2CID27828219.September/October 2008
• Kohlenbach, Ulrich(2008),Applied proof theory: proof interpretations and their use in mathematics,Springer Monographs in Mathematics, Berlin, New York:Springer-Verlag,ISBN978-3-540-77532-4,MR2445721
• Kleene, Stephen Cole(2002) [1967],Mathematical logic,New York:Dover Publications,ISBN978-0-486-42533-7,MR1950307
• Rautenberg, Wolfgang(2010),A Concise Introduction to Mathematical Logic(3rd ed.),New York:Springer Science+Business Media,doi:10.1007/978-1-4419-1221-3,ISBN978-1-4419-1220-6.
• Shoenfield, Joseph R.(2001) [1967],Mathematical Logic(2nd ed.),A K Peters,ISBN978-1-56881-135-2

External links

• Introduction to Mathematical Logicby Vilnis Detlovs and Karlis Podnieksis a comprehensive tutorial. See Section 1.5.
• "Deduction Theorem"