Could not include topos theory - contents
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 $\mathbb{N}$ 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) $E$ with terminal object $1$ is
an object $\mathbb{N}$ in $E$
equipped with
a morphism $z :1 \to \mathbb{N}$ from the terminal object $1$;
a morphism $s : \mathbb{N} \to \mathbb{N}$ (successor);
such that
for every other diagram $1 \stackrel{q}{\to}A \stackrel{f}{\to} A$
there is a unique morphism $u : \mathbb{N} \to A$ such that
All this may be summed up by saying that a natural numbers object is an initial algebra for the endofunctor $X \mapsto 1 + X$ (the functor underlying the “maybe monad”). Equivalently, it is an initial algebra for the endo-profunctor $Hom_E(1,=) \times Hom_E(-,=)$.
By the universal property, the natural numbers object is unique up to isomorphism.
Note that this definition actually makes sense in any category $E$ having finite products. However, if $E$ is not cartesian closed, then it is better to explicitly assume a stronger version of this definition “with parameters” (which follows automatically when $E$ is cartesian closed, such as when $E$ is a topos). What this amounts to is demanding that $(\mathbb{N}, z, s)$ not only be a natural numbers object (in the above, unparametrized sense) in $E$, but that also, for each object $A$, this is preserved by the cofree coalgebra functor into the Kleisli category of the comonad $X \mapsto A \times X$ (which may be thought of as the category of maps parametrized by $A$). (Put another way, the finite product structure of $E$ 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 $E$).
To be explicit:
In a category with finite products, a parametrized natural numbers object is an object $N$ together with maps $z: 1 \to N$, $s: N \to N$ such that given any objects $A$, $X$ and maps $f: A \to X$, $g: X \to X$, there is a unique map $\phi_{f, g}: A \times N \to X$ making the following diagram commute:
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 $F$ into Set yields a bijection between $Hom_F(1, \mathbb{N})$ and the actual natural numbers, as well as surjections from $Hom_F(\mathbb{N}^m, \mathbb{N})$ onto the primitive recursive functions of arity $m$ for each finite $m$. 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 $\mathbb{N}$ is uniquely characterized by the following colimit conditions due to Peter Freyd:
In a topos, a triple $(\mathbb{N}, 0: 1 \to \mathbb{N}, s: \mathbb{N} \to \mathbb{N})$ is a natural numbers object if and only if
The morphism $(0, s): 1 + \mathbb{N} \to \mathbb{N}$ 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 $C$ with binary coproducts and 1, the natural numbers object can be equivalently described as an initial algebra structure $(0, s): 1 + \mathbb{N} \to \mathbb{N}$ for the endofunctor $F(c) = 1 + c$ defined on $C$. 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 $f: \mathbb{N} \to X$ such that $f = f \circ s$, the claim is that $f$ factors as
for some unique $x$, in fact for $x = f(0)$. Uniqueness is clear since $!: \mathbb{N} \to 1$, being a retraction for $0: 1 \to \mathbb{N}$, is epic. On the other hand, substituting either $f$ or $f(0) \circ !$ for $g$ in the diagram
this diagram commutes, so that $f = f(0) \circ !$ by the uniqueness clause in the universal property for $\mathbb{N}$.
Here we just give an outline, referring to (Johnstone), section D.5.1, for full details. Let $N$ be an object satisfying the two colimit conditions of Freyd. First one shows (see the lemma 1 below) that $N$ has no nontrivial $F$-subalgebras. Next, let $A$ be any $F$-algebra, and let $i: B \to N \times A$ be the intersection of all $F$-subalgebras of $N \times A$. One shows that $\pi_1 \circ i: B \to N$ is an ($F$-algebra) isomorphism. Thus we have an $F$-algebra map $f: N \to A$. If $g: N \to A$ is any $F$-algebra map, then the equalizer of $f$ and $g$ is an $F$-subalgebra of $N$, and therefore $N$ itself, which means $f = g$.
Let $F$ be the endofunctor $F(X) = 1+X$. If $N$ satisfies Freyd’s colimit conditions, then any $F$-subalgebra of $N$ is the entirety of $N$.
Following (Johnstone), we may as well show that the smallest $F$-subalgebra $N'$ of $N$ (the internal intersection of all $F$-subalgebras) is all of $N$. Let $S \hookrightarrow N \times N$ be the union of the relation $R = \langle 1, s \rangle: N \to N \times N$ and its opposite, so that $S$ is a symmetric relation. Working in the Mitchell-Bénabou language, one may check directly that the following formula is satisfied:
Let us say a term $w$ of type $P N$ is $S$-closed if the formula
is satisfied. Now define a relation $T$ on $N$ by the subobject
Observe that $T$ is an equivalence relation that contains $S$ and therefore $R$. It therefore contains the kernel pair of the coequalizer of $1$ and $s$; since this coequalizer is by assumption $N \to 1$, the kernel pair is all of $N \times N$. Also observe that since $N'$ is $S$-closed by definition, it is $T$-closed as well, and we now conclude
so that, putting $y = 0: 1 \to N'$, we conclude that $x \in N \Rightarrow x \in N'$, i.e., that $N'$ is all of $N$.
A slightly alternative proof of sufficiency uses the theory of well-founded coalgebras, as given here. If $N$ is a fixpoint of the functor $F(X) = 1+X$, regarded as an $F$-coalgebra, then the internal union of well-founded subcoalgebras of $N$ is a natural numbers object $\mathbb{N}$. Then the subobject $\mathbb{N} \hookrightarrow N$ can also be regarded as a subalgebra; by the lemma, it is all of $N$. Thus $N$ is a natural numbers object.
In any Grothendieck topos $E = Sh(C)$ 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 $C^{op} \to Set$ that is constant on the set $\mathbb{N}$.
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 $f = (f^* \dashv f_*) : \mathcal{E} \underoverset{f_*}{f^*}{\leftrightarrows} \mathcal{F}$ be a geometric morphism of toposes. If $\mathbb{N} \in \mathcal{F}$ is a natural numbers object, then its inverse image $f^* \mathbb{N}$ is a natural numbers object in $\mathcal{E}$.
(Johnstone, lemma A.4.1.14). Of course, by the finite colimit characterization, we need only the fact that inverse images, being left adjoints, preserve finite colimits.
If $\mathcal{E}$ is a sheaf topos, then there is a unique geometric morphism $(\Delta \dashv \Gamma): \mathcal{E} \underoverset{\Gamma}{\Delta}{\leftrightarrows} Set$, the global section geometric morphism, with the inverse image being the locally constant sheaf functor, it follows that
with the evident successor and constant $0$, is the natural nunbers object in $\mathcal{E}$.
If $\mathcal{E}$ is a topos and $X \in \mathcal{E}$ an object, then the slice topos sits by an etale geometric morphism over $\mathcal{E}$
where the inverse image form the product with $X$. Hence for $\mathbb{N} \in \mathcal{E}$ a natural numbers object, the projection $(X \times \mathbb{N} \to X)$ is a natural numbers object in $\mathcal{E}_{/X}$.
Given a natural numbers object $\mathbb{N}$ in a pretopos, we can construct an integers object as follows. Let $a, b\colon E \to \mathbb{N} \times \mathbb{N}$ be the kernel pair of the addition map ${+}\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, and let $\pi_1, \pi_2\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ be the product projections. We define $\mathbb{Z}$ to be the coequalizer of the congruence $(\pi_1 \circ a, \pi_2 \circ b), (\pi_2 \circ a, \pi_1 \circ b)\colon E \to \mathbb{N} \times \mathbb{N}$. A similar construction yields a rational numbers object $\mathbb{Q}$.
For a real numbers object, rather more care is needed; see real numbers object.