Natural numbers object

Last updated

In category theory, a natural numbers object (NNO) 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:

Contents

  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. [1] [2] [3]

In other words, the triangle and square in the following diagram commute.

Natural numbers object definition.svg

The pair (q, f) is sometimes called the recursion data for u, given in the form of a recursive definition:

  1. u (z) = q
  2. yENu (sy) = f (u (y))

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 (CCCs) or topoi are sometimes defined in the following equivalent way (due to Lawvere): 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. [4]

NNO definition alt.png

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 (denoted by +), an NNO can be defined as the initial algebra of the endofunctor that acts on objects by X ↦ 1 + X and on arrows by f ↦ id1 + f. [5]

Properties

Examples

See also

References

  1. Johnstone 2002, A2.5.1.
  2. Lawvere 2005, p. 14.
  3. Leinster, Tom (2014). "Rethinking set theory". American Mathematical Monthly. 121 (5): 403–415. arXiv: 1212.6543 . Bibcode:2012arXiv1212.6543L. doi:10.4169/amer.math.monthly.121.05.403. S2CID   5732995.
  4. Johnstone 2002, A2.5.2.
  5. Barr, Michael; Wells, Charles (1990). Category theory for computing science. New York: Prentice Hall. p. 358. ISBN   0131204866. OCLC   19126000.
  6. Johnstone 2002, p. 108.