Natural numbers object


In category theory, a natural numbers object is an object endowed with a recursive structure similar to natural numbers. More precisely, in a category E with a terminal object 1, an NNO N is given by:
  1. a global element z : 1 → N, and
  2. an arrow s : NN,
such that for any object A of E, global element q : 1 → A, and arrow f : AA, there exists a unique arrow u : NA such that:
  1. uz = q, and
  2. us = fu.
In other words, the triangle and square in the following diagram commute.

The pair is sometimes called the recursion data for u, given in the form of a recursive definition:
  1. u = q
  2. yE Nu = f
The above definition is the universal property of NNOs, meaning they are defined up to canonical isomorphism. If the arrow u as defined above merely has to exist, that is, uniqueness is not required, then N is called a weak NNO.

Equivalent definitions

NNOs in cartesian closed categories or topoi are sometimes defined in the following equivalent way : for every pair of arrows g : AB and f : BB, there is a unique h : N × AB such that the squares in the following diagram commute.

This same construction defines weak NNOs in cartesian categories that are not cartesian closed.
In a category with a terminal object 1 and binary coproducts, an NNO can be defined as the initial algebra of the endofunctor that acts on objects by and on arrows by.

Properties