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 question is that many texts 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
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 \vdash Q \quad\text{iff}\quad T\vdash P \rightarrow Q $$
The single turnstile symbol "$\vdash$" 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\rightarrow 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.
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.
In the spirit of Kenny's observation, note also that we can formulate classical logic using a Peircian inference rule (equivalent to the usual theory in the presence of ex falso quodlibet) which clearly modifies the inferential properties of implication:
${{{A \rightarrow B} \atop \vdots} \atop A } \over A$
but in an odd way: is it an introduction rule? But there is no logical structure in the conclusion. Is it an elimination rule? But the implication above the rule appears among the assumptions to the subderivation, not the conclusion. It seems to be something like an implication elimination-eliminating rule, a kind of structurally double-negative introduction rule, where you can introduce logical structure by discharging it in the assumptions.
All the rules for adding classical-strength inference to the usual, well-behaved intuitionistic natural deduction involve inference rules that are eccentric in some way or another. Parigot's lambda-mu calculus shows how the fundamental structural glue of (through a classical Curry-Howard correspondence) natural deduction can be tweaked to make it as good a fit for classical logic as the sequent calculus.
In chapter 3 of my DPhil dissertation (Stewart 2000), I give what I think is a successful reconstruction of Prawitz's inversion principle for the lambda-mu-based natural deduction, and show how this provides the basis for something we might call "classical constructivism", where the principle of the excluded middle is admitted as having constructive content by being a principle that provides a constructive, dialectical mediation between proofs and refutations.
Ref. Stewart (2000) On the formulae-as-types correspondence for classical logic.
