topos theory

# Natural numbers object

## Idea

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.

## Definition

### In a topos or cartesian closed category

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

$\array{ 1 &\stackrel{z}{\to}& \mathbb{N} &\stackrel{s}{\to}& \mathbb{N} \\ & {}_q\searrow & \downarrow^{u} && \downarrow^{u} \\ && A &\stackrel{f}{\to} & A }$

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.

### In a general category with finite products

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:

###### Definition

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:

$\array{ A & \stackrel{\langle z \circ !, 1_A\rangle}{\to} & N \times A & \stackrel{s \times 1_A}{\leftarrow} & N \times A \\ & \mathllap{f} \searrow & \downarrow \mathrlap{\phi_{f, g}} & & \downarrow \mathrlap{\phi_{f, g}} \\ & & X & \underset{g}{\leftarrow} & X }$

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.

### In type theory

For the moment see at inductive type the section Examples - Natural numbers

## Finite colimit characterization

In a topos, the natural numbers object $\mathbb{N}$ is uniquely characterized by the following colimit conditions due to Peter Freyd:

###### Theorem

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

1. The morphism $(0, s): 1 + \mathbb{N} \to \mathbb{N}$ is an isomorphism;

2. The diagram

$\mathbb{N} \stackrel{\overset{s}{\to}}{\underset{1}{\to}} \mathbb{N} \to 1$

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.

###### Proof of theorem 1: necessity

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

$\mathbb{N} \overset{!}{\to} 1 \overset{x}{\to} X$

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

$\array{ 1 & \overset{0}{\to} & \mathbb{N} & \overset{s}{\to} & \mathbb{N} \\ & ^\mathllap{f(0)} \searrow & \downarrow ^g & & \downarrow ^g \\ & & X & \underset{1_X}{\to} & X }$

this diagram commutes, so that $f = f(0) \circ !$ by the uniqueness clause in the universal property for $\mathbb{N}$.

###### Proof of theorem 1: sufficiency

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$.

###### Lemma

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$.

###### Proof

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:

$\forall x, y: N (\langle x, y \rangle \in S) \Rightarrow ((x \in N') \Leftrightarrow (y \in N'))$

Let us say a term $w$ of type $P N$ is $S$-closed if the formula

$\forall x, y: N (\langle x, y \rangle \in S) \Rightarrow ((x \in [w]) \Leftrightarrow (y \in [w]))$

is satisfied. Now define a relation $T$ on $N$ by the subobject

$\{\langle x, y \rangle \in N \times N: \forall w: P N (w \; is \; S closed) \Rightarrow ((x \in [w]) \Leftrightarrow (y \in [w])).$

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

$\forall x, y \in N: (x \in N') \Leftrightarrow (y \in N')$

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$.

###### Remark

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.

## Examples

### In a sheaf topos

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.

## Properties

### Transfer along inverse images

###### Proposition

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.

###### Example

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

$\Delta(\mathbb{N}) \cong \Delta(\sum_{n: \mathbb{N}} 1) \cong \sum_{n: N} \Delta 1 \cong \sum_{n: \mathbb{N}} 1,$

with the evident successor and constant $0$, is the natural nunbers object in $\mathcal{E}$.

###### Example

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}$

$\mathcal{E}_{/X} \stackrel{\overset{X^*}{\leftarrow}}{\underset{X_*}{\to}} \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}$.

### Relation to object of integers

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.

## References

Revised on November 28, 2014 08:15:21 by Urs Schreiber (82.224.164.72)