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

homotopy levels





In informal mathematical speech and writing, a numeral refers to any notation or terms which denotes a natural number directly. Usually, in mathematics, this refers to base ten place-value notation, so that for instance 00, 22, 1313, and 890890 are numerals.

In the more formal world of logic and type theory, a numeral generally means (e.g. Martin-Löf 73) a term whose type is a natural numbers type and which is of canonical form. The meaning of “canonical form” may vary with the formal theory, but with the usual presentation of the natural numbers as an inductive type generated by zero 00 and the successor operation ss, the numerals are the terms of the form

s(s(s(s(0)))). s(s(\cdots s(s(0))\cdots )).

Often, the numeral representing the natural number nn — which is to say, the term with ss applied nn times to 00 — is denoted by n̲\underline{n}. Thus, for instance, 2̲\underline{2} means s(s(0))s(s(0)). It is important to note that 2̲\underline{2} is not (usually) a term inside the formal system being considered; it is a “meta-notation” which stands for the term s(s(0))s(s(0)). (One might say that the underline converts informal numerals to formal ones.) In particular, any statement which quantifies over a natural number nn that occurs in a term n̲\underline{n} can only be expressed in the metatheory?.


Not every term of natural number type \mathbb{N} is a numeral; consider for instance 2̲+2̲\underline{2}+\underline{2}. However, good formal systems have the property of canonicity, which in this context means that every term of type \mathbb{N} computes to, or is provably equal to, a numeral. In our example, if ++ is defined by recursion, there is a sequence of beta-reduction steps leading from 2̲+2̲\underline{2}+\underline{2} to 4̲\underline{4}. (Canonicity is about terms in the empty context?; in a context with free variables of type \mathbb{N}, then of course there will be more terms of type \mathbb{N}, built out of these variables.)

If we add to such a formal system an axiom using an existential statement, then this is equivalent to adding to the language an additional term for a natural number that is not (and may not provably be equal to) any canonical numeral. For example, in PA+¬Con(PA)PA + \neg{Con(PA)} (Peano arithmetic plus the axiom that Peano arithmetic is inconsistent?), we have the axiom

n,(n PA), \exists n, (n \vdash_{PA} \bot) ,

stating the existence of a number nn that is the Gödel number? of a proof in PAPA of a falsehood. If we instead extend the language of PAPA with a new symbol ※ and add the axiom

PA, ※ \vdash_{PA} \bot ,

then (assuming that PAPA and so PA+¬Con(PA)PA + \neg{Con(PA)} is in fact consistent) one can prove

n̲ \underline{n} \neq ※

in this system for every natural number nn, but one cannot prove

n,n \forall n,\, n \neq ※

(which is actually trivially refutable).



  • Per Martin-Löf, An intuitionistic theory of types: predicative part, (1973)

it says

A closed normal term with type symbol NN, which obviously must have the form s(s(...s(0)...))s(s(...s(0)...)), is called a numeral.

Revised on May 24, 2017 10:20:32 by Urs Schreiber (