Assumption discharge 2026-10-25
Assumption discharge closes a designated temporary assumption together with its dependent subproof. Implication introduction rule turns a logical derivation of under into outside that temporary scope. Negation introduction rule turns a logical derivation of logical falsity under into . Disjunction elimination rule discharges its separate case assumptions while retaining any surrounding premises.
Implication creation rule 2026-10-25
From a logical derivation of , infer under the same surrounding assumptions. To derive the rule, temporarily assume , retain the available , and discharge by the implication introduction rule. Its being unused is allowed.
From infer . Assume , then assume . Implication elimination rule gives and , hence . Discharge and then by the implication introduction rule. The original premise and any surrounding assumptions remain available.
Lambda abstraction Created 2026-10-06 Updated 2026-10-14
A lambda abstraction binds the variable in the lambda term . In the simply typed lambda calculus, if under , the abstraction has type ; this is the implication introduction rule under the Curry-Howard correspondence.
Logical implication Created 2026-09-28 Updated 2026-10-25
Logical implication forms the proposition , read “if , then ”. In classical propositional logic, it is false exactly when is true and is false. Equivalently, it has the same truth table as , using logical negation and logical disjunction. A false hypothesis makes the logical implication true regardless of its conclusion; thus it asserts neither the hypothesis nor a causal connection.
For example, for every natural number , divisibility by four implies that is an even number: . At , both statements are true. At , the hypothesis is false and the conclusion true; at , both are false. The only forbidden case is a multiple of four that is not an even number.
In Intuitionistic propositional logic, a proof of consists of a construction transforming any proof of into a proof of . The implication introduction rule proves under a temporary assumption ; the modus ponens rule applies the result when is available. The classical identification with is not generally intuitionistically valid.
In the simply typed lambda calculus, types are generated from atomic types by the arrow constructor . A typed lambda term is a lambda term equipped with a derivation of a judgement , where the context assigns types to its free variables. The basic typing rules are
The Implicational Curry-Howard correspondence reads atomic types as propositions and as logical implication. A typed variable is an assumption, abstraction is the implication introduction rule discharging that assumption, and application is the implication elimination rule. Consequently a typed lambda term is a proof in implicational Intuitionistic propositional logic, and a natural deduction proof recursively supplies such a term. For example, expresses implication reflexivity. Products, sums, and the empty type extend the correspondence to conjunction, disjunction, and falsity; pure arrow types give precisely the implicational fragment. Beta reduction removes an introduction followed immediately by its elimination, matching proof simplification.
A Church numeral is
where means repetitions of application. At base type , it has type . The following Church numeral arithmetic terms use left-associated application:
Their concise conclusions are
For successor, the initial adds one application. For addition, the inner supplies applications and supplies more. For multiplication, the repeated operation applies times, and repetitions give . For exponentiation, iterates the operation on : each iteration replaces a function by its -fold iterate, yielding . Zero iterations give , so this encoding takes , including . The explicit outer abstractions make the result the standard Church numeral even at exponent zero, without needing eta equivalence.
Successor, addition, and multiplication operate on the same . The displayed exponentiation term has type : its exponent iterates an operation on functions. Thus the numeral syntax admits several type instances; one should not force every occurrence into one fixed monomorphic Church type.
The Y combinator is the fixed-point combinator
For , beta reduction gives . Since , we obtain . This allows a recursive program body to receive a representation of itself.
Here the computation is in the untyped lambda calculus. The self-application would require a simple type satisfying , impossible for finite simple types. Accordingly is not a typed lambda term of the simply typed system. The Strong normalization theorem for simply typed lambda calculus also rules out a universal divergent fixed-point operator there.
To obtain a lambda representation of partial computable functions, encode machine configurations as finite data using Church numerals, Church pairs, and Church Booleans. Initial configuration, one transition, the halting test, and output extraction are primitive recursive functions, represented by lambda terms through the initial functions, composition, and lambda definition of primitive recursion by pair iteration. If these representations are , , , and , define
Use normal-order beta reduction so the Church Boolean halting test selects one branch without evaluating the unused recursive branch. A halting computation follows finitely many transitions and returns the Church numeral of the output. A nonhalting computation forces successive tests forever and has no head normal form; by normal-order normalization theorem, it cannot be beta equivalent to a Church numeral. Thus every partial computable function is represented, with divergence preserved; every total computable function is the halting special case. This explains the role of in computational universality while keeping the typed proof interpretation precise.
Write and . The displayed formula is . A proof of logical implication may use its temporary assumption more than once; this is ordinary natural deduction, not a linear proof system.
Assume , then , then , then . The identity weakening rule derives from the hypotheses and . Discharging by the implication introduction rule gives . Applying by the implication elimination rule gives . Discharge to obtain . Applying gives an ; discharge to obtain a ; apply once more to obtain , and finally discharge .
Here is the complete decorated natural deduction derivation, split at its intermediate conclusion to keep the tree readable. Superscript labels mark which assumption occurrences are discharged; both occurrences labelled are discharged together.
To avoid an excessively wide final tree, continue the same derivation as follows, using the right-hand derived premise above:
followed by
Thus the concise lambda term, with bound-variable types determined by the displayed tree, is
Under the Curry-Howard correspondence, implication introduction rules correspond to lambda abstractions, implication elimination rules to applications, and the identity weakening rule retains the first term while allowing an unused second hypothesis. No other inference rule or classical axiom is required.
The conjunction introduction rule combines derivations of and into a derivation of . Both conclusions must be available under the current assumptions.
The disjunction elimination rule is reasoning by cases: from , a subproof deriving the same conclusion under , and another subproof deriving under , conclude . It discharges the two case assumptions, not any surrounding premises.
The implication introduction rule derives by temporarily assuming and deriving ; it then discharges that occurrence of the assumption .
Thus
A conclusion inside a box cannot simply be reused outside it without an appropriate inference rule. Any other undischarged assumptions continue to constrain the result. These are exactly the rules printed in Figure 1.[ref]
The conjunction introduction rule derives from proofs of and in the current context. The disjunction elimination rule derives a common conclusion from , a subproof of under temporary assumption , and a subproof of under temporary assumption . The implication introduction rule derives by temporarily assuming and proving .
The rectangular boxes delimit subproofs and the scope of their temporary assumptions. The disjunction elimination rule discharges the two case assumptions; the implication introduction rule discharges its antecedent assumption. Formulas depending on a boxed assumption cannot simply escape that box. Other undischarged assumptions remain in force, and nested boxes can access the assumptions of enclosing boxes.
Under , the first assumption yields , while the second yields . Apply the implication elimination rule once more to obtain , and discharge the three temporary assumptions:
LineContextFormulaJustification
1Temporary assumption
2Temporary assumption
3Temporary assumption
4implication elimination rule on 1, 3
5implication elimination rule on 2, 3
6implication elimination rule on 4, 5
7implication introduction rule on 6; discharge 3
8implication introduction rule on 7; discharge 2
9implication introduction rule on 8; discharge 1
The two uses of are permitted in ordinary natural deduction. Therefore
Introduce the three logical implications from the outside in. Under assumptions , , and , apply the implication elimination rule twice, then use assumption discharge in reverse order:
LineContextFormulaJustification
1Temporary assumption
2Temporary assumption
3Temporary assumption
4implication elimination rule on 1, 3
5implication elimination rule on 2, 4
6implication introduction rule on 5; discharge 3
7implication introduction rule on 6; discharge 2
8implication introduction rule on 7; discharge 1
Thus
Eliminate the existential premise with fresh witness . Its first conjunct gives and its second gives . For a fresh arbitrary , one direction of the desired logical biconditional follows by universal elimination. For the other, must be reversed before transporting to using the supplied oriented equality elimination rule.
LineContextFormulaJustification
1Premise
2Temporary assumption
3conjunction elimination rule on 2
4conjunction elimination rule on 2
5universal elimination on 4; instantiate at
6Temporary assumption
7equality introduction rule
8equality elimination rule on 6, 7
9equality elimination rule on 8, 3
10implication introduction rule on 9; discharge 6
11biconditional introduction rule on 5, 10
12universal introduction on 11; fresh
13existential quantifier introduction rule on 12; witness
14existential quantifier elimination rule on 1, 13; discharge 2; fresh
Here is absent from every open assumption when line 12 uses universal introduction. In line 13 the existential quantifier binds the witness position occupied by ; the conclusion then has no free , allowing line 14 to close its witness subproof. Hence
The premise says an object satisfying exists and every object satisfying equals it. The logical biconditional adds the converse explicitly: every object equal to that witness also satisfies .
In natural deduction, conjunction introduction combines derivations of and under the available assumptions into . Disjunction elimination takes and two subproofs of the same conclusion , one assuming and the other assuming , and concludes . Implication introduction takes a subproof deriving from a temporary assumption , and concludes .
The rectangular boxes mark the scopes of temporary assumptions. The disjunction elimination rule discharges its two case assumptions, while the implication introduction rule discharges the antecedent assumption. Other surrounding assumptions remain in force; intermediate results depending on the boxed assumptions cannot be exported arbitrarily. Schematically,
Here the square brackets designate the assumptions discharged by the corresponding inference rule.
Use conjunction elimination to extract the three inputs, then apply the implication elimination rule three times:
The implication introduction rule closes the only subproof, giving
Read chained logical implications as right-associative. Use the following natural deduction derivation; indentation bars mark nested subproofs and the last column records rules and discharged line ranges:
Each application of the implication introduction rule discharges only its matching temporary assumption. Thus
The implication introduction rule opens a subproof under a temporary assumption , derives , then performs assumption discharge to conclude . The negation introduction rule instead derives logical falsity under a temporary assumption , discharges it, and concludes :
The rectangular boxes delimit these subproofs and the scope of their temporary assumptions. A line depending on the boxed temporary assumption cannot simply be used outside the box. The relevant introduction rule exports the indicated logical implication or negation; other surrounding assumptions stay in force.
First obtain by a double-negation elimination, then obtain by the negation introduction rule. The following natural deduction proof uses only the printed rules, with denoting the logical falsity elimination rule:
Reiteration only reuses an available line within its scope. In particular, the unused temporary assumption on line 11 is legitimately discharged by the implication introduction rule.
Put and . Use the printed implication elimination rule, negation elimination rule, negation introduction rule, double-negation elimination and implication introduction rule:
Line 1 is the given premise; the argument actually establishes the conclusion without needing it, since line 2 supplies its own copy of . Introducing and discharging this separate temporary assumption preserves the exact printed conclusion.
The implication introduction rule opens a subproof with a temporary assumption , derives , and discharges that assumption to conclude . The negation introduction rule opens a subproof with a temporary assumption , derives logical falsity , and discharges it to conclude .
The boxes record the scopes and dependencies of the temporary assumptions. A result derived inside a box cannot be used outside it without the appropriate discharge rule; it may depend on the boxed assumption. Other, surrounding assumptions remain in force. This is how the natural deduction rules distinguish a conditional derivation from an unconditional assertion.
Use the two derived inference rules whose complete proofs were supplied in (d). The following logical derivation has no nested hypothetical subproofs:
1  P → Q                           premise
2  Q → R                           premise
3  P → (Q → R)                     → creation from 2
4  (P → Q) → (P → R)               → distribution from 3
5  P → R                           →-elim, 1 and 4
The creation instance takes and . The distribution instance takes . The metarules are justified in (d); this requested flat use does not secretly invoke implication introduction rule in one of its own lines.