nLab empty type

Redirected from "bottom type".
Contents

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

logicset theory (internal logic of)category theorytype theory
propositionsetobjecttype
predicatefamily of setsdisplay morphismdependent type
proofelementgeneralized elementterm/program
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
introduction rule for implicationcounit for hom-tensor adjunctionlambda
elimination rule for implicationunit for hom-tensor adjunctionapplication
cut elimination for implicationone of the zigzag identities for hom-tensor adjunctionbeta reduction
identity elimination for implicationthe other zigzag identity for hom-tensor adjunctioneta conversion
truesingletonterminal object/(-2)-truncated objecth-level 0-type/unit type
falseempty setinitial objectempty type
proposition, truth valuesubsingletonsubterminal object/(-1)-truncated objecth-proposition, mere proposition
logical conjunctioncartesian productproductproduct type
disjunctiondisjoint union (support of)coproduct ((-1)-truncation of)sum type (bracket type of)
implicationfunction set (into subsingleton)internal hom (into subterminal object)function type (into h-proposition)
negationfunction set into empty setinternal hom into initial objectfunction type into empty type
universal quantificationindexed cartesian product (of family of subsingletons)dependent product (of family of subterminal objects)dependent product type (of family of h-propositions)
existential quantificationindexed disjoint union (support of)dependent sum ((-1)-truncation of)dependent sum type (bracket type of)
logical equivalencebijection setobject of isomorphismsequivalence type
support setsupport object/(-1)-truncationpropositional truncation/bracket type
n-image of morphism into terminal object/n-truncationn-truncation modality
equalitydiagonal function/diagonal subset/diagonal relationpath space objectidentity type/path type
completely presented setsetdiscrete object/0-truncated objecth-level 2-type/set/h-set
setset with equivalence relationinternal 0-groupoidBishop set/setoid with its pseudo-equivalence relation an actual equivalence relation
equivalence class/quotient setquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
-0-truncated higher colimitquotient inductive type
coinductionlimitcoinductive type
presettype without identity types
set of truth valuessubobject classifiertype of propositions
domain of discourseuniverseobject classifiertype universe
modalityclosure operator, (idempotent) 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

homotopy levels

semantics

Contents

Idea

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.

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.

To start with, since the empty type is not dependent, its type formation rule just says that 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.

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 :=

Recursion principle

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:x \,\colon\, \varnothing, given any D:TypeD \,\colon\, Type, it suffices to specify what should be done for all the ways that x:x \,\colon\, \varnothing could have been constructed. But for the empty type there are no such ways and hence – assuming x:x \,\colon\, \varnothing – we obtain a term of any type DD under no further conditions:

D:Typex:ind D(x):D \frac{ D \,\colon\, Type } { x \,\colon\, \varnothing \;\; \vdash \;\; ind_D(x) \,\colon\, D }

Some ways to read this recursion principle:

FalseD. False \;\Rightarrow\; D \,.
D. \varnothing \xrightarrow{\exists} D \,.

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.

Induction principle

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:

type formation rule:

| |:Type \frac{ }{ \mathclap{\phantom{\vert^{\vert}}} \varnothing \,\colon\, Type }


term introduction rule:

--- none --- \text{--- none ---}


term elimination rule:

x:D(x):Type| |ind (D):x:D(x) \frac{ x \,\colon\, \varnothing \;\vdash\;\; D(x) \,:\, Type }{ \mathclap{\phantom{\vert^{\vert}}} ind_{(D)} \,\colon\, \underset{x \colon \varnothing}{\prod} D(x) }


computation rule:

--- none --- \text{--- none ---}

Notice that the induction principle entails the recursion principle above (cf. e.g. MHE, §2.6), as for any inductive type:

D:Type((x:)D):(Type)ind (xD):(x:)D \frac{ \frac{ D \,\colon\, Type } { \big( (x \,\colon\, \varnothing) \mapsto D \big) \,\colon\, (\varnothing \to Type) } }{ ind_{ (x \mapsto D) } \,\colon\, (x \colon \varnothing) \to D }

Eta-conversion

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:c:Ce \,\colon\, \varnothing \;\;\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. . 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 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.

Using a type of propositions

Suppose that the dependent type theory has a type of propositions Prop\mathrm{Prop}, such as the one derived from a type universe UU - A:UisProp(A)\sum_{A:U} \mathrm{isProp}(A). Then the empty type is defined as the dependent function type

P:PropP\emptyset \equiv \prod_{P:\mathrm{Prop}} P

whose elements are witnesses that all propositions are pointed types (and thus contractible types).

By weak function extensionality, the empty type is a proposition, and if it has an element, then every proposition in Prop\mathrm{Prop} has an element and is contractible.

Properties

Equivalence of the definitions of the empty type

Theorem

The inductive definition of the empty type and the definition of the empty type in terms of dependent product types and the type of propositions are equivalent to each other.

Proof

Since the empty type is a proposition, it is equivalent to its own propositional truncation []\emptyset \simeq [\emptyset].

Meanwhile, the propositional truncation of a type AA is equivalent to the dependent product type

[A] P:Prop(AP)P[A] \simeq \prod_{P:\mathrm{Prop}} (A \to P) \to P

Substituting the empty type for AA, we have

[] P:Prop(P)P[\emptyset] \simeq \prod_{P:\mathrm{Prop}} (\emptyset \to P) \to P

By the recursion principle of the empty type, for every type PP, the type P\emptyset \to P is contractible, and for every contractible type II, the type IPI \to P is equivalent to PP. Thus, we have equivalences of types

[]( P:Prop(P)P)( P:PropP)\emptyset \simeq [\emptyset] \simeq \left(\prod_{P:\mathrm{Prop}} (\emptyset \to P) \to P\right) \simeq \left(\prod_{P:\mathrm{Prop}} P\right)

References

The definition of the empty type from the type of propositions and dependent product types can be found in:

  • Madeleine Birchfield, Constructing coproduct types and boolean types from universes, MathOverflow (web)

In Agda:

See also:

Last revised on April 30, 2024 at 01:49:13. See the history of this page for a list of all contributions to it.