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.
Implication distribution rule 2026-10-25
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.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 20 4 Solution Created 2026-10-03 Updated 2026-10-07
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 areThe 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 iswhere means repetitions of application. At base type , it has type . The following Church numeral arithmetic terms use left-associated application:Their concise conclusions areFor 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 combinatorFor , 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 , defineUse 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.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 21 4 ii Solution Created 2026-10-03 Updated 2026-10-06
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 byThus the concise lambda term, with bound-variable types determined by the displayed tree, isUnder 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 .
ThusA 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:
| Line | Context | Formula | Justification |
|---|---|---|---|
| 1 | Temporary assumption | ||
| 2 | Temporary assumption | ||
| 3 | Temporary assumption | ||
| 4 | implication elimination rule on 1, 3 | ||
| 5 | implication elimination rule on 2, 3 | ||
| 6 | implication elimination rule on 4, 5 | ||
| 7 | implication introduction rule on 6; discharge 3 | ||
| 8 | implication introduction rule on 7; discharge 2 | ||
| 9 | implication introduction rule on 8; discharge 1 |
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:
| Line | Context | Formula | Justification |
|---|---|---|---|
| 1 | Temporary assumption | ||
| 2 | Temporary assumption | ||
| 3 | Temporary assumption | ||
| 4 | implication elimination rule on 1, 3 | ||
| 5 | implication elimination rule on 2, 4 | ||
| 6 | implication introduction rule on 5; discharge 3 | ||
| 7 | implication introduction rule on 6; discharge 2 | ||
| 8 | implication 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.
| Line | Context | Formula | Justification |
|---|---|---|---|
| 1 | Premise | ||
| 2 | Temporary assumption | ||
| 3 | conjunction elimination rule on 2 | ||
| 4 | conjunction elimination rule on 2 | ||
| 5 | universal elimination on 4; instantiate at | ||
| 6 | Temporary assumption | ||
| 7 | equality introduction rule | ||
| 8 | equality elimination rule on 6, 7 | ||
| 9 | equality elimination rule on 8, 3 | ||
| 10 | implication introduction rule on 9; discharge 6 | ||
| 11 | biconditional introduction rule on 5, 10 | ||
| 12 | universal introduction on 11; fresh | ||
| 13 | existential quantifier introduction rule on 12; witness | ||
| 14 | existential 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. HenceThe 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 4The 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.