inductive type, higher inductive type
Recall that a topos is a category that behaves likes the category Set of sets.
A natural numbers object (NNO) in a topos is an object that behaves in that topos like the set of natural numbers does in Set; thus it provides a formulation of the “axiom of infinity” in structural set theory (such as ETCS). The definition is due to William Lawvere.
A natural numbers object in a topos (or any cartesian closed category) with terminal object is
an object in
equipped with
a morphism from the terminal object ;
a morphism (successor);
such that
for every other diagram
there is a unique morphism such that
All this may be summed up by saying that a natural numbers object is an initial algebra for the endofunctor . Equivalently, it is an initial algebra for the endo-profunctor .
By the universal property, the natural numbers object is unique up to isomorphism.
Note that this definition actually makes sense in any category having finite products. However, if is not cartesian closed, then it is better to explicitly assume a stronger version of this definition “with parameters” (which follows automatically when is cartesian closed, such as when is a topos). What this amounts to is demanding that not only be a natural numbers object (in the above, unparametrized sense) in , but that also, for each object , this is preserved by the free coalgebra functor into the Kleisli category of the comonad (which may be thought of as the category of maps parametrized by ). (Put another way, the finite product structure of gives rise to a canonical self-indexing, and we are demanding the existence of an (unparametrized) NNO within this indexed category, rather than just within the base ).
The functions which are constructable out of the structure of a category with finite products and such a “parametrized NNO” are precisely the primitive recursive? ones. Specifically, the unique structure-preserving functor from the free such category into Set yields a bijection between and the actual natural numbers, as well as surjections from onto the primitive recursive functions of arity for each finite . With cartesian closure, however, this identification no longer holds, since non-primitive recursive functions (such as the Ackermann function?) become definable as well.
For the moment see at inductive type the section Examples - Natural numbers
In a topos, the natural numbers object is uniquely characterized by the following colimit conditions due to Peter Freyd: a triple is a natural numbers object if and only if
The morphism is an isomorphism;
The diagram
is a coequalizer.
The necessity of the first condition holds in any category with binary coproducts and a terminal object, and the necessity of the second holds in any category whatsoever.
For a category with binary coproducts and 1, the natural numbers object can be equivalently described as an initial algebra structure for the endofunctor defined on . Then condition 1 is a special case of Lambek's theorem, that the algebra structure map of an initial algebra is an isomorphism.
As for condition 2, given such that , the claim is that factors as
for some unique , in fact for . Uniqueness is clear since , being a retraction for , is epic. On the other hand, substituting either or for in the diagram
this diagram commutes, so that by the uniqueness clause in the universal property for .
We give a brief outline, referring to (Johnstone), section D.5.1, for full details. Let be an object satisfying the two colimit conditions of Freyd. One first shows that has no nontrivial -subalgebras. Next, let be any -algebra, and let be the intersection of all -subalgebras of . One shows that is an (-algebra) isomorphism. Thus we have an -algebra map . If is any -algebra map, then the equalizer of and is an -subalgebra of , and therefore itself, which means .
In any Grothendieck topos the natural numbers object is given by the constant sheaf on the set of ordinary natural numbers, i.e. by the sheafification of the presheaf that is constant on the set .
There are interesting cases in which such sheaf toposes contain objects that look like they ought to be natural numbers objects but do not satisfy the above axioms: for instance some of the models described at Models for Smooth Infinitesimal Analysis are sheaf toposes that contain besides the standard natural number object a larger object of smooth natural numbers that has generalized elements which are “infinite natural numbers” in the sense of nonstandard analysis.
Natural number objects are preserved by inverse images:
let be a geometric morphism of toposes. If is a natural numbers object, then its inverse image is a natural numbers object in .
If is a sheaf topos, then there is a unique geometric morphism , the global section geometric morphism, with the inverse image being the locally constant sheaf functor, it follows that
with the evident successor and constant , is the natural nunbers object in .
If is a topos and an object, then the slice topos sits by an etale geometric morphism over
where the inverse image form the product with . Hence for a natural numbers object, the projection is a natural numbers object in .
Given a natural numbers object in a pretopos, we can construct an integers object as follows. Let be the kernel pair of the addition map , and let be the product projections. We define to be the coequalizer of the congruence . A similar construction yields a rational numbers object .
For a real numbers object, rather more care is needed; see real numbers object.