nLab
empty type

Context

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism = propositions as types +programs as proofs +relation type theory/category theory

logiccategory theorytype theory
trueterminal object/(-2)-truncated objecth-level 0-type/unit type

falseinitial objectempty type

proposition(-1)-truncated objecth-proposition, mere proposition

proofgeneralized elementprogram

cut rulecomposition of classifying morphisms / pullback of display mapssubstitution

cut elimination for implicationcounit for hom-tensor adjunctionbeta reduction

introduction rule for implicationunit for hom-tensor adjunctioneta conversion

logical conjunctionproductproduct type

disjunctioncoproduct ((-1)-truncation of)sum type (bracket type of)

implicationinternal homfunction type

negationinternal hom into initial objectfunction type into empty type

universal quantificationdependent productdependent product type

existential quantificationdependent sum ((-1)-truncation of)dependent sum type (bracket type of)

equivalencepath space objectidentity type

equivalence classquotientquotient type

inductioncolimitinductive type, W-type, M-type

higher inductionhigher colimithigher inductive type

completely presented setdiscrete object/0-truncated objecth-level 2-type/preset/h-set

setinternal 0-groupoidBishop set/setoid

universeobject classifiertype of types

modalityclosure operator, (idemponent) monadmodal type theory, monad (in computer science)

linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation

proof netstring diagramquantum circuit

(absence of) contraction rule(absence of) diagonalno-cloning theorem

synthetic mathematicsdomain specific embedded programming language

</table>

homotopy levels

semantics

Contents

Idea

In type theory the empty type is the type with no term.

In a model by categorical semantics, this is an initial object. In set theory, it is an empty set.

Definition

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.

The way to build the empty type is trivial: it exists.

:Type\frac{ }{\emptyset\colon Type}

As a positive type

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.

The eliminator rules are derived from the constructor rules in the usual way: to use a term e:e\colon \emptyset, it suffices to specify what should be done for all the (zero) ways that ee could have been constructed. Thus, we don’t need any hypotheses:

e:abort C(e):C\frac{ }{e\colon \emptyset \vdash abort_C(e)\colon C}

That is, given an element of \emptyset, we can construct an element of any type CC. In dependent type theory, we must generalize the eliminator to allow CC to depend on \emptyset.

There is no ∞-reduction rule, since there are no constructors to compose with the eliminator. However, there is an ∞-conversion rule, which says that for any term e:c:Ce\colon \emptyset\vdash c\colon C in a context including a term of type \emptyset, we have

abort C(e) ηc. abort_C(e) \;\leftrightarrow_\eta\; c.

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 cc from abort C(e)abort_C(e)), but makes sense as an expansion.

The positive presentation of the empty type can be regarded as a particular sort of inductive type. In Coq syntax:

Inductive empty : Type :=
.

Coq implements the beta reduction rule, but not the eta (although eta equivalence is provable for the inductively defined identity types, using the dependent eliminator mentioned above).

As a negative type

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” 0\mathbf{0} and the negative one is “bottom” \bot.

Last revised on April 21, 2017 at 10:53:57. See the history of this page for a list of all contributions to it.