|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-proposition, mere proposition|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|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)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
A W-type is a set or type which is defined inductively in a well-founded way – an inductive type. In most set theories, W-types can be proven to exist, but in predicative mathematics or type theory, where this is not the case, they are often assumed explicitly to exist. In particular W-types can be used to provide a constructive counterpart of the classical notion of a well-ordering and to uniformly define a variety of inductive types.
The terms/elements of a W-type can be considered to be “rooted well-founded trees” with a certain branching type; different W-types are distinguished by their branching signatures. A branching signature is represented essentially by a family of sets which can be interpreted as requiring that each node of the tree is labeled with an element of the set , and that if a node is labeled by then it has exactly outgoing edges, each labeled by an element of . From a more computational point of view, the W-type can be viewed as a data type, where indexes the set of constructors and is the arity of the constructor .
(1) The most basic W-type is the natural numbers. Here there are two constructors:
(2) Similarly, if is any set, then the W-type of lists of elements of has constructors:
Actually, there are two slightly different formulations of W-types.
Here we describe a W-type as the initial algebra for an endofunctor. The family can be thought of as a morphism in some category (the fiber over being ), and the endofunctor in question is the composite
Such a composite is called a polynomial endofunctor.
This definition makes sense in any locally cartesian closed category, although the W-type (the initial algebra) may or may not exist in any given such category. (A non-elementary construction of them is given by the transfinite construction of free algebras.)
This definition is most useful when the category is not just locally cartesian closed but is a Π-pretopos, since often we want to use at least coproducts in constructing and . For example, a natural numbers object is a W-type specified by one of the coproduct inclusions , and the list object is a W-type specified by . More generally, endofunctors that look like polynomials in the traditional sense:
can be constructed as polynomial endofunctors in the above sense in any -pretopos. A -pretopos in which all W-types exist is called a ΠW-pretopos.
In a topos with a natural numbers object (NNO), W-types for any polynomial endofunctor can be constructed as certain sets of well-founded trees; thus every topos with a NNO is a ΠW-pretopos. This applies in particular in the topos Set (unless one is a predicativist, in which case is not a topos and W-types in it must be postulated explicitly).
given a diagram of the form
there is the dependent polynomial functor
This reduces to the above for the terminal object. Notice that we do not necessarily have , so this is not just simply a polynomial endofunctor of considered as a lccc in its own right.
In type theory, W-types are introduced by giving explicit constructors and destructors, a.k.a. term introduction and term elimination rules. If the type theory is extensional, i.e. identities have unique proofs and (dependent) function types are extensional ( if and only if for all ), then this is more or less equivalent to the categorical version given above. The type theories that are the internal logic of familiar kinds of categories are all extensional in this sense.
The rules for -types in extensional type theory are the following:
(1) -formation rule
In the following we will sometimes abbreviate by .
(2) -introduction rule
(3) -elimination rule
(4) -computation rule
The main distinction from the naive categorical theory above is that the map (from the lines above the rules) must be assumed to be a display map, i.e. to exhibit as a dependent type over , in order that the dependent product be defined. In the case of dependent polynomial functors, must also be a display map in order to define . (Actually, using adjointness, one can still define the W-type even if is not a display map, but its properties are not as good. This extra generality is important, however. For example, identity types arise as this more general kind of W-type; see this blog post.)
Mike Shulman: Is the term “W-type” still used in this generality? Or are they just called “inductive types”?
Note also that in intensional type theory, a W-type is only an initial algebra with respect to propositional equality, not definitional equality. In particular, the constructors are injective only propositionally, not definitionally. This applies already for the natural numbers.
The original definition in type theory is due to
The categorical semantics of W-types by initial algebras of polynomial endofunctors is due to
Dependent W-type were introduced in