|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-level 1-type/h-prop|
|classical type theory?||internal logic||classical type theory?, logic programming?|
|cut elimination?||counit||beta reduction|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator monad||modal type theory, monad (in computer science)|
The framework of natural deduction describes a particular class of deductive systems which formalize “natural” deductive reasoning or reasoning from assumptions. It is used particularly to describe the syntax of formal logic and type theory.
The phrase “natural deduction” is not always used to mean the same thing. Some people use it semi-informally to refer to a “sort of reasoning” that involves making assumptions, perhaps formalized using hypothetical judgments. Other people take it to refer specifically to deductive systems which are presented using introduction and elimination rules, which is the meaning we adopt on this page. There is significant overlap between the two meanings, but they are not identical.
A system of natural deduction is a deductive system containing a class of judgments generated by some “constructor” operations, and for which each constructor comes with two relevant classes of rules:
Introduction rules, which allow us to conclude a judgment built using the constructor from simpler judgments; and
Elimination rules, which allow us to conclude some other judgment by using a judgment involving the constructor.
while its elimination rules might be
The introduction and elimination rules must fit together in an appropriate way, sometimes referred to as “harmony”.
Similarly, in a system of type theory, the relevant judgments are typing judgments of the form , meaning that the term belongs to the type . In this case, an analogous constructor might be the cartesian product type, whose rules are analogous, but keeping track of the specific terms involved (see propositions as types):
In natural deduction systems for type theory, there are usually two other classes of rules:
Computation rules or conversion rules, which constrain the result of combining term introduction with term elimination.
These two rules refer to different classes of judgments than the introduction and elimination rules: judgments that a certain thing is a type for the formation rules, and judgments that one term reduces to, or converts with, another, for the computation rules.
For instance, the cartesian product type would come with a formation rule
and computation rules such as beta-reduction
(and possibly eta-conversion).
Technically, the propositional logic system could also come with a formation rule involving a judgment “is a proposition”:
But it would not have a computation rule, as there are no terms inhabiting its propositions. (It could, however, be embedded into a type theory via propositions as types, where there would be terms inhabiting its propositions regarded as types).
On the other hand, in type theories that have a type of types, there may be no need for a separate judgment ””, as it can be replaced by a typing judgment ”” that belongs to a type of types.
Natural deduction also generally involves hypothetical judgments or reasoning from assumptions. For instance, the introduction rule for implication in a system of propositional logic says that if, assuming ””, we can derive ””, then we can derive ””. This is sometimes written as
(We now follow the common practice of writing the judgment ”” as simply ””.) Here the indicate an arbitrary derivation tree, while the brackets around indicate that this assumption has been “discharged” and is no longer an assumption in the conclusion . To be precise, we should annotate each bracket somehow to indicate which rule discharged that assumption.
Another way to indicate hypothetical reasoning (which also allows it to fit once again within the general notion of deductive system) is to indicate in each judgment the hypotheses on which it depends. Thus, we might write ”” to mean a hypothetical judgment of assuming . With this notation, the introduction rule for can be written as:
Here we have prefixed the entire derivation in (1) by ”” to indicate that it is all performed with as an assumption, and the discharge of that assumption is indicated by removing this prefix from the final conclusion. We also begin the deduction with the axiom (the identity rule?).
To be fully precise, we should now allow all rules to take place under arbitrary additional hypotheses; thus the introduction rule of should really be
where denotes an arbitrary list of hypothesis truth judgments. However, often this unchanged ambient context is unstated, but implicitly assumed to be present.
Hypothetical judgments of this sort are very similar to the sequents which appear in sequent calculus, and are (as is evident) written with very similar notation. However, the rules of natural deduction are different from the rules of sequent calculus, as are its formal properties.
This treatment of hypothetical judgments applies also to type theories, where the individual judgments are typing judgments. In this case, the assumed judgments on the left of the are generally restricted to be of the form with a variable (rather than an arbitrary term), and these assumed judgments are referred to as the context. When the judgment on the right of the may involve variables that occur to its left, one speaks of generic judgments rather than “hypothetical” ones. Thus, a generic judgment is of the form
to be read as
In a context where we have a term of a type , there is a term of type .
Thus, for instance, the introduction rule for the function type is
In natural deduction for dependent type theory, we can also have type judgments with hypotheses, such as
to be read as
In a type theory with a type of types, this judgment could be written as .
So far, we have been considering hypothetical judgments such as and generic judgments such as to be “atomic” judgments in a particular deductive system. In particular, the turnstile symbol has been simply another symbol that we use to build judgments according to a particular syntax, analogous to the colon . As remarked at deductive system, this usage of is a priori completely unrelated to its use to indicate provability of theorems in a particular deductive system (such as a system of natural deduction), and therefore perhaps ought to be denoted by a different symbol.
However, it is also possible to incorporate some “knowledge” about the meaning of hypothetical and generic judgments into the deductive system, and thereby bring the two meanings of back into alignment. See logical framework for a development of this idea.
The four classes of rules of natural deduction are close to being specifications of universal constructions in category theory. In categorical semantics one considers categories which are such that their objects are regarded as types and their generalized elements as terms, then the rules of natural deductions describe the possible construction of morphisms in that category.
A formalization of the general logical framework of natural deduction is discussed in section 3 of
A good account is at