natural deduction metalanguage, practical foundations
type theory (dependent, intensional, observational type theory, homotopy type theory)
computational trinitarianism =
propositions as types +programs as proofs +relation type theory/category theory
In type theory the empty type is the type with no term.
In a model by categorical semantics (cf. relation between type theory and category theory), this is an initial object. In set theory, it is an empty set. In logic, especially via the propositions as types interpretation of type theory, it represents falsehood; and constructing a term of an empty type represents a contradiction; thus functions into the empty type are regarded as the negation of their domain proposition.
Like all type constructors in type theory, to characterize the empty type we must specify how to build it, how to construct elements of it, how to use such elements, and the computation rules.
To start with, since the empty type is not dependent, its type formation rule just says that it exists:
The empty type is most naturally presented as a positive type, so that the constructor rules are primary. However, since the empty type is supposed to contain no elements, there are no constructor rules.
In fact one may understand the positively defined empty type as that inductive type which is given by no constructors.
Therefore, in programming languages supporting a calculus of constructions, such as Coq, the empty type may be defined by the following syntax for inductive data types using literally an empty string of constructors on the right:
Inductive empty : Type :=
We start by considering the recursion principle of the empty type, hence its un-dependent elimination rule:
The eliminator rules are derived from the constructor rules in the usual way: to use a term $x \,\colon\, \varnothing$, given any $D \,\colon\, Type$, it suffices to specify what should be done for all the ways that $x \,\colon\, \varnothing$ could have been constructed. But for the empty type there are no such ways and hence – assuming $x \,\colon\, \varnothing$ – we obtain a term of any type $D$ under no further conditions:
Some ways to read this recursion principle:
What is not manifest from the above rule is the (essential) uniqueness of these morphisms; on that point see also the eta conversion rule, below.
In dependent type theory the elimination rule of an inductive type is a dependent induction principle which involves any $\varnothing$-dependent type.
Applying the general rules for inductive types to the case of no generators, one obtains the following inference rules:
Notice that the induction principle entails the recursion principle above (cf. e.g. MHE, §2.6), as for any inductive type:
Notice that there is no beta-reduction rule for the positive empty type, since there are no constructors to compose with the eliminator.
However, one may consider an eta-conversion rule, which says that for any term $e \,\colon\, \varnothing \;\;\vdash\;\; c \,\colon\, C$ in a context including a term of type $\emptyset$, we have
As with the $\eta$-conversion rule for the negative presentation of the unit type, this is ill-defined as a reduction (since we cannot determine $c$ from $abort_C(e)$), but makes sense as an expansion. . Notice that Coq implements the beta reduction rule, but not the eta conversion (although eta equivalence is provable for the inductively defined identity types, using the dependent eliminator mentioned above).
As for binary sum types, it is possible to present the empty type as a negative type as well, but only if we allow sequents with multiple conclusions. This is common in sequent calculus presentations of classical logic, but not as common in type theory and almost unheard of in dependent type theory.
The two definitions are provably equivalent, but only using the contraction rule and the weakening rule. Thus, in linear logic they become distinct; the positive empty type is “zero” $\mathbf{0}$ and the negative one is “bottom” $\bot$.
Univalent Foundations Project, §1.7 and §A.28 in: Homotopy Type Theory – Univalent Foundations of Mathematics (2013) [web, pdf]
Egbert Rijke, Def. 3.2.1 in: Inductive types and the universe, Lecture 3 in: Introduction to Homotopy Type Theory 2018 [pdf]
In Agda:
See also:
Last revised on January 26, 2023 at 08:47:39. See the history of this page for a list of all contributions to it.