Editing Natural numbers object

In [[category theory]], a '''natural numbers object''' ('''NNO''') is an object endowed with a [[Recursion (computer science)|recursive]] [[Mathematical structure|structure]] similar to [[natural number]]s. More precisely, in a [[Category (mathematics)|category]] '''E''' with a [[terminal object]] 1, an NNO ''N'' is given by:

# a [[global element]] ''z'' : 1 → ''N'', and
# an [[morphism|arrow]] ''s'' : ''N'' → ''N'',

such that for any object ''A'' of '''E''', global element ''q'' : 1 → ''A'', and arrow ''f'' : ''A'' → ''A'', there exists a unique arrow ''u'' : ''N'' → ''A'' such that:

# ''u'' ∘ ''z'' = ''q'', and
# ''u'' ∘ ''s'' = ''f'' ∘ ''u''.{{sfn|Johnstone|2002|loc=A2.5.1}}{{sfn|Lawvere|2005|p=14}}<ref>{{Cite journal|last=Leinster|first=Tom|date=2014|title=Rethinking set theory|journal=American Mathematical Monthly |volume=121|issue=5|pages=403–415|arxiv=1212.6543|bibcode=2012arXiv1212.6543L|doi=10.4169/amer.math.monthly.121.05.403|s2cid=5732995 }}</ref>

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

<div style="margin-left: 2em">[[Image:Natural numbers object definition.svg|250px|A commutative diagram expressing the equations in the definition of an NNO]]</div>

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

# ⊢ ''u'' (''z'') = ''q''
# ''y'' ∈<sub>'''E'''</sub> ''N'' ⊢ ''u'' (''s'' ''y'') = ''f'' (''u'' (''y''))

The above definition is the [[universal property]] of NNOs, meaning they are defined [[up to]] [[List of mathematical jargon#canonical|canonical]] [[morphism|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 category|cartesian closed categories]] (CCCs) or [[Topos|topoi]] are sometimes defined in the following equivalent way (due to [[Lawvere]]): for every pair of arrows ''g'' : ''A'' → ''B'' and ''f'' : ''B'' → ''B'', there is a unique ''h'' : ''N'' × ''A'' → ''B'' such that the squares in the following diagram commute.{{sfn|Johnstone|2002|loc=A2.5.2}}

<div style="margin-left: 2em">[[Image:NNO definition alt.png|alternate NNO definition]]</div>

This same construction defines weak NNOs in cartesian categories that are not cartesian closed.

In a category with a terminal object 1 and binary [[coproduct]]s (denoted by +), an NNO can be defined as the [[initial algebra]] of the [[endofunctor]] that acts on objects by {{math|{{var|X}} ↦ 1 + {{var|X}}}} and on arrows by {{math|{{var|f}} ↦ id<sub>1</sub> + {{var|f}}}}.<ref>{{Cite book|title=Category theory for computing science|last1=Barr|first1=Michael|last2=Wells|first2=Charles|date=1990|publisher=Prentice Hall|isbn=0131204866|location=New York|oclc=19126000|page=358}}</ref>

== Properties ==

* Every NNO is an initial object of the category of [[Diagram (category theory)|diagrams]] of the form
::<math displaystyle="block">1 \xrightarrow{~ \quad q \quad ~} A \xrightarrow{~ \quad f \quad ~} A</math>

* If a cartesian closed category has weak NNOs, then every [[slice category|slice]] of it also has a weak NNO.
* NNOs can be used for [[non-standard model]]s of [[type theory]] in a way analogous to non-standard models of analysis. Such categories (or topoi) tend to have "infinitely many" non-standard natural numbers.{{clarify|date=December 2017}} (Like always, there are simple ways to get non-standard NNOs; for example, if ''z'' = ''s z'', in which case the category or topos '''E''' is trivial.)
* [[Peter Freyd|Freyd]] showed that ''z'' and ''s'' form a [[coproduct]] diagram for NNOs; also, !<sub>''N''</sub> : ''N'' → 1 is a [[coequalizer]] of ''s'' and 1<sub>''N''</sub>, ''i.e.'', every pair of global elements of ''N'' are connected by means of ''s''; furthermore, this pair of facts characterize all NNOs.

== Examples ==

* In '''Set''', the [[category of sets]], the standard natural numbers are an NNO.{{sfn|Johnstone|2002|p=108}} A terminal object in '''Set''' is a [[Singleton (mathematics)|singleton]], and a function out of a singleton picks out a single [[Element (set theory)|element]] of a set. The natural numbers 𝐍 are an NNO where {{var|z}} is a function from a singleton to 𝐍 whose [[Image (mathematics)|image]] is zero, and {{var|s}} is the [[successor function]]. (We could actually allow {{var|z}} to pick out ''any'' element of 𝐍, and the resulting NNO would be isomorphic to this one.) One can prove that the diagram in the definition commutes using [[mathematical induction]].
* In the category of types of [[Martin-Löf type theory]] (with types as objects and functions as arrows), the standard natural numbers type '''nat''' is an NNO. One can use the recursor for '''nat''' to show that the appropriate diagram commutes.
* Assume that <math> \mathcal{E} </math> is a [[Grothendieck topos]] with terminal object <math> \top </math> and that <math> \mathcal{E} \simeq \mathbf{Shv}(\mathfrak{C},J) </math> for some [[Grothendieck topology]] <math> J </math> on the category <math> \mathfrak{C} </math>. Then if <math> \Gamma_{\mathbb{N}} </math> is the constant presheaf on <math> \mathfrak{C} </math>, then the NNO in <math> \mathcal{E} </math> is the sheafification of <math> \Gamma_{\mathbb{N}} </math> and may be shown to take the form <math display="block"> \mathbb{N}_{\mathcal{E}} \cong \left(\Gamma_{\mathbb{N}}\right)^{++} \cong \coprod_{n \in \mathbb{N}} \top. </math>

==See also==

* [[Peano's axioms]] of [[arithmetic]]
* [[Categorical logic]]

== References ==
{{Reflist}}
* {{Cite book|title=Sketches of an Elephant: a Topos Theory Compendium|last=Johnstone|first=Peter T.|date=2002|publisher=Oxford University Press|isbn=0198534256|location=Oxford|oclc=50164783}}
* {{Cite journal|last=Lawvere|first=William|date=2005|orig-year=1964|title=An elementary theory of the category of sets (long version) with commentary|url=http://www.tac.mta.ca/tac/reprints/articles/11/tr11abs.html|journal=Reprints in Theory and Applications of Categories|volume=11|pages=1–35}}

== External links ==
* Lecture notes from [[Robert Harper (computer scientist)|Robert Harper]] which discuss NNOs in Section 2.2: https://www.cs.cmu.edu/~rwh/courses/hott/notes/notes_week3.pdf
* A blog post by Clive Newstead on the {{var|n}}-Category Cafe: https://golem.ph.utexas.edu/category/2014/01/an_elementary_theory_of_the_ca.html
* Notes on datatypes as algebras for endofunctors by computer scientist [[Philip Wadler]]: http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt
* Notes on the [[nLab]]: https://ncatlab.org/nlab/show/ETCS

{{Category theory}}

[[Category:Objects (category theory)]]
[[Category:Topos theory]]
[[Category:Categorical logic]]