In
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, a natural numbers object (NNO) is an object endowed with a
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
structure
A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
similar to
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s. More precisely, in a
category
Category, plural categories, may refer to:
Philosophy and general uses
* Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
* ...
E with a
terminal object
In category theory, a branch of mathematics, an initial object of a category is an object in such that for every object in , there exists precisely one morphism .
The dual notion is that of a terminal object (also called terminal element): ...
1, an NNO ''N'' is given by:
# a
global element ''z'' : 1 → ''N'', and
# an
arrow
An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers c ...
''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''.
In other words, the triangle and square in the following diagram commute.
The pair (''q'', ''f'') is sometimes called the ''recursion data'' for ''u'', given in the form of a
recursive definition
In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set ( Aczel 1977:740ff). Some examples of recursively-definable objects include facto ...
:
# ⊢ ''u'' (''z'') = ''q''
# ''y'' ∈
E ''N'' ⊢ ''u'' (''s'' ''y'') = ''f'' (''u'' (''y''))
The above definition is the
universal property
In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fro ...
of NNOs, meaning they are defined
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
canonical
The adjective canonical is applied in many contexts to mean "according to the canon" the standard, rule or primary source that is accepted as authoritative for the body of knowledge or literature in that context. In mathematics, "canonical example ...
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
. 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
In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in ma ...
(CCCs) or
topoi
In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a noti ...
are sometimes defined in the following equivalent way (due to
Lawvere
Francis William Lawvere (; born February 9, 1937) is a mathematician known for his work in category theory, topos theory and the philosophy of mathematics.
Biography
Lawvere studied continuum mechanics as an undergraduate with Clifford Truesd ...
): 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.
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
In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprodu ...
s (denoted by +), an NNO can be defined as the
initial algebra
In mathematics, an initial algebra is an initial object in the category of -algebras for a given endofunctor . This initiality provides a general framework for induction and recursion.
Examples
Functor
Consider the endofunctor sending t ...
of the
endofunctor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ma ...
that acts on objects by and on arrows by .
Properties
* Every NNO is an initial object of the category of
diagrams
A diagram is a symbolic representation of information using visualization techniques. Diagrams have been used since prehistoric times on walls of caves, but became more prevalent during the Enlightenment. Sometimes, the technique uses a three- ...
of the form
::
* If a cartesian closed category has weak NNOs, then every
slice of it also has a weak NNO.
* NNOs can be used for
non-standard model In model theory, a discipline within mathematical logic, a non-standard model is a model of a theory that is not isomorphic to the intended model (or standard model).Roman Kossak, 2004 ''Nonstandard Models of Arithmetic and Set Theory'' American Ma ...
s of
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
in a way analogous to non-standard models of analysis. Such categories (or topoi) tend to have "infinitely many" non-standard natural numbers. (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.)
*
Freyd showed that ''z'' and ''s'' form a
coproduct
In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprodu ...
diagram for NNOs; also, !
''N'' : ''N'' → 1 is a
coequalizer
In category theory, a coequalizer (or coequaliser) is a generalization of a quotient by an equivalence relation to objects in an arbitrary category. It is the categorical construction dual to the equalizer.
Definition
A coequalizer is a co ...
of ''s'' and 1
''N'', ''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
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition of m ...
, the standard natural numbers are an NNO. A terminal object in Set is a
singleton
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...
, and a function out of a singleton picks out a single
element of a set. The natural numbers 𝐍 are an NNO where is a function from a singleton to 𝐍 whose
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
is zero, and is the
successor function
In mathematics, the successor function or successor operation sends a natural number to the next one. The successor function is denoted by ''S'', so ''S''(''n'') = ''n'' +1. For example, ''S''(1) = 2 and ''S''(2) = 3. The successor functio ...
. (We could actually allow 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
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
.
* In the category of types of
Martin-Löf type theory
Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative Foundations of mathematics, foundation of mathematics.
Intuitionistic type theory was created by Per Martin-Löf, a ...
(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
is a
Grothendieck topos
In mathematics, a topos (, ; plural topoi or , or toposes) is a category (mathematics), category that behaves like the category of Sheaf (mathematics), sheaves of Set (mathematics), sets on a topological space (or more generally: on a Site (math ...
with terminal object
and that
for some
Grothendieck topology In category theory, a branch of mathematics, a Grothendieck topology is a structure on a category ''C'' that makes the objects of ''C'' act like the open sets of a topological space. A category together with a choice of Grothendieck topology is ca ...
on the category
. Then if
is the constant presheaf on
, then the NNO in
is the sheafification of
and may be shown to take the form
See also
*
Peano's axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
of
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
*
Categorical logic
__NOTOC__
Categorical logic is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic. It is also notable for its connections to theoretical computer science.
In broad terms, categ ...
References
*
*
External links
* Lecture notes from
Robert Harper Robert or Bob Harper may refer to:
* Robert Almer Harper (1862–1946), American botanist
* Robert Goodloe Harper (1765–1825), US senator from Maryland
* Robert Harper (fl. 1734–1761), founder of Harpers Ferry, West Virginia
* Robert Harper (a ...
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 -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
Philip Lee Wadler (born April 8, 1956) is an American computer scientist known for his contributions to programming language design and type theory. He is the chair of Theoretical Computer Science at the Laboratory for Foundations of Computer S ...
: 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
Objects (category theory)
Topos theory
Categorical logic