# Discharging assumptions

When constructing proofs using natural deduction what does it mean to say that an assumption or premise is discharged? In what circumstances would I want to, or need to, use such a mechanism?

The reason I'm asking this questions is that many text on logic use this term as understood by the reader and don't take the time to adequately explain the technical sense in which they are using it.

-

As I understand it, to discharging a premise or assumption is the opposite of introducing it: you absorb it (for example) into the antecedent of an implication --- this means that it is no longer an assumption. A trivial example:

P 1. Assume P

__

P 2. From 1

__

P->P 3. Discharging 1

Thus I have concluded that P->P without any assumptions (iow |- P->P). If we didn't discharge the assumption, we would have P|-P

-
Thanks for this answer Apollo. One way of describing the purpose of discharging assumptions which I liked when I was reading up about this was that it's like introducing a temporary variable in programming - i.e. the scope is limited between the point where it's used in a rule and upwards to where it's discahrged; for example in inductive proofs the induction step requires you to assume P(n=k), showing P(n=k+1) and in doing so discharging P(n=k). (Btw, it's a bit nit-picky I know, but you can only discharge an assumption, not a premise (except when an assumption actually becomes an premise).) –  axiomsofchoice Nov 30 '09 at 16:00
@axiomsofchoice It's more like the argument to a function. If you write a block of code that assumes you have something of type A and ends by returning something of type B then you can discharge the assumption by making the block into a function that takes an argument of type A and returns a result of type B. It's not just 'like' - the correspondence can be made precise with Curry-Howard. –  Dan Piponi Apr 12 '10 at 17:03

Note that the standard natural deduction systems also have a premise introduced and then discharged in the negation-introduction rule.

For systems that explicitly track sub-proofs within the larger proof, a "discharge" step is just the end of a subproof, where you come to a conclusion that no longer depends on the additional assumption used in starting the subproof.

-

Apollo is correct. A slightly more technical way of putting it is that "discharging" is an application of a theorem of metalogic called the deduction theorem:

T,P|-Q iff T|-P->Q

The single turnstile symbol "|-" stands for the syntactic consequences relation. The deduction theorem basically says "Q is derivable from T and P iff if P then Q is derivable from T alone". T may, of course, be an empty class of statements, in which case P->Q is tautologous.

Many systems of natural deduction introduce conditional proof as a primitive rule, but there are simpler systems that are just as powerful in which the deduction theorem is proved and conditional proof is a derived rule supported by the deduction theorem. The deduction theorem is important because it shows you don't need conditional proof as a primitive rule, and this makes the proof of other theorems in metalogic a whole lot simpler. Basically, if you have as few rules as possible it gives you fewer cases to check. For practical purposes, however, it's a whole lot easier to teach and use a system that introduces lots and lots of primitive rules as opposed to one that uses as few rules as possible.

Mathematicians use conditional proof all the time, by the way. For example, in a proof of Q by cases you get conditionals P1->Q, P2->Q, etc. by for each case supposing the antecedents, deriving Q from the supposition, then "discharging" the supposition. Then you show the disjunction of the antecedents is exhaustive.

-
${{{A \rightarrow B} \atop \vdots} \atop A } \over A$