View source for Category (mathematics)

{{Short description|Mathematical object that generalizes the standard notions of sets and functions}}

[[File:Category_SVG.svg|thumbnail|This is a category with a collection of objects A, B, C and collection of morphisms denoted f, g, {{nowrap|g ∘ f}}, and the loops are the identity arrows. This category is typically denoted by a boldface '''3'''.]]

In [[Mathematics|mathematics]], a '''category''' (sometimes called an '''abstract category''' to distinguish it from a [[Concrete category|concrete category]]) is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object.  A simple example is the [[Category of sets|category of sets]], whose objects are [[Set (mathematics)|sets]] and whose arrows are [[Function (mathematics)|functions]].

''[[Category theory]]'' is a branch of mathematics that seeks to generalize all of mathematics in terms of categories, independent of what their objects and arrows represent.  Virtually every branch of modern mathematics can be described in terms of categories, and doing so often reveals deep insights and similarities between seemingly different areas of mathematics.  As such, category theory provides an alternative foundation for mathematics to [[Set theory|set theory]] and other proposed axiomatic foundations.  In general, the objects and arrows may be abstract entities of any kind, and the notion of category provides a fundamental and abstract way to describe mathematical entities and their relationships.

In addition to formalizing mathematics, category theory is also used to formalize many other systems in computer science, such as the semantics of programming languages.

Two categories are the same if they have the same collection of objects, the same collection of arrows, and the same associative method of composing any pair of arrows. Two ''different'' categories may also be considered "[[Equivalence of categories|equivalent]]" for purposes of category theory, even if they do not have precisely the same structure.

Well-known categories are denoted by a short capitalized word or abbreviation in bold or italics:  examples include '''[[Category of sets|Set]]''', the category of [[Set (mathematics)|sets]] and [[Function (mathematics)|set functions]]; '''[[Category of rings|Ring]]''', the category of [[Ring (mathematics)|rings]] and [[Ring homomorphism|ring homomorphism]]s; and '''[[Category of topological spaces|Top]]''', the category of [[Topological space|topological space]]s and continuous maps. All of the preceding categories have the [[Identity function|identity map]] as identity arrows and [[Function composition|composition]] as the associative operation on arrows.

The classic and still much used text on category theory is ''[[Categories for the Working Mathematician]]'' by [[Biography:Saunders Mac Lane|Saunders Mac Lane]]. Other references are given in the References below. The basic definitions in this article are contained within the first few chapters of any of these books.
{{Group-like structures}}
Any [[Monoid|monoid]] can be understood as a special sort of category (with a single object whose self-morphisms are represented by the elements of the monoid), and so can any [[Preorder|preorder]].

==Definition==
There are many equivalent definitions of a category.<ref>{{harvnb|Barr|Wells|2005|loc=Chapter 1}}</ref> One commonly used definition is as follows.  A '''category''' ''C'' consists of
* a [[Class (set theory)|class]] ob(''C'') of '''[[Philosophy:Mathematical object|object]]s''',
* a class mor(''C'') of '''[[Morphism|morphism]]s''' or '''arrows''',
*a '''domain''' or '''source''' class function dom: mor(C) → ob(C),
*a '''codomain''' or '''target''' class function cod: mor(C) → ob(C),
* for every three objects ''a'', ''b'' and ''c'', a binary operation hom(''a'', ''b'') × hom(''b'', ''c'') → hom(''a'', ''c'') called '''composition of morphisms'''. Here hom(''a'', ''b'') denotes the subclass of morphisms ''f'' in  mor(''C'') such that dom(f) = ''a'' and cod(f) = ''b''.  Morphisms in this subclass are written ''f'' : ''a'' → ''b'', and the composite of ''f'' : ''a'' → ''b'' and ''g'' : ''b'' → ''c'' is often written as ''g'' ∘ ''f'' or ''gf''. 
such that the following axioms hold:
* the ''associative law''': if ''f'' : ''a'' → ''b'', ''g'' : ''b'' → ''c'' and ''h'' : ''c'' → ''d'' then ''h'' ∘ (''g'' ∘ ''f'') = (''h'' ∘ ''g'') ∘ ''f'', and
* the '''([[Identity (mathematics)|left and right unit laws]])''': for every object ''x'', there exists a morphism 1<sub>''x''</sub> : ''x'' → ''x'' (some authors write ''id''<sub>''x''</sub>) called the ''identity morphism for x'', such that every morphism ''f'' : ''a'' → ''x'' satisfies 1<sub>''x''</sub> ∘ ''f'' = ''f'', and every morphism ''g'' : ''x'' → ''b'' satisfies ''g'' ∘ 1<sub>''x''</sub> = ''g''.

We write ''f'': ''a'' → ''b'', and we say "''f'' is a morphism from ''a'' to ''b''". We write hom(''a'', ''b'') (or hom<sub>''C''</sub>(''a'', ''b'') when there may be confusion about to which category hom(''a'', ''b'') refers) to denote the '''hom-class''' of all morphisms from ''a'' to ''b''.<ref>Some authors write Mor(''a'', ''b'') or simply ''C''(''a'', ''b'') instead.</ref> 

Some authors write the composite of morphisms in "diagrammatic order", writing ''f;g'' or ''fg'' instead of ''g'' ∘ ''f''.

From these axioms, one can prove that there is exactly one identity morphism for every object.  Often the map assigning each object its identity morphism is treated as an extra part of the structure of a category, namely a class function i: ob(C) → mor(C).  
Some authors use a slight variant of the definition in which each object is identified with the corresponding identity morphism. This stems from the idea that the fundamental data of categories are morphisms and not objects. In fact, categories can be defined without reference to objects at all using a partial binary operation with additional properties.

==Small and large categories==

A category ''C'' is called '''small''' if both ob(''C'') and hom(''C'') are actually [[Set (mathematics)|sets]] and not proper classes, and '''large''' otherwise. A '''locally small category''' is a category such that for all objects ''a'' and ''b'', the hom-class hom(''a'', ''b'') is a set, called a '''homset'''. Many important categories in mathematics (such as the category of sets), although not small, are at least locally small.  Since, in small categories, the objects form a set, a small category can be viewed as an [[Algebraic structure|algebraic structure]] similar to a [[Monoid|monoid]] but without requiring [[Closure (mathematics)|closure]] properties.  Large categories on the other hand can be used to create "structures" of algebraic structures.

==Examples==
The [[Class (set theory)|class]] of all sets (as objects) together with all [[Function (mathematics)|function]]s between them (as morphisms), where the composition of morphisms is the usual [[Function composition|function composition]], forms a large category, '''[[Category of sets|Set]]'''. It is the most basic and the most commonly used category in mathematics. The category '''[[Category of relations|Rel]]''' consists of all [[Set (mathematics)|sets]] (as objects) with [[Binary relation|binary relation]]s between them (as morphisms).  Abstracting from [[Relation (mathematics)|relations]] instead of functions yields [[Allegory (category theory)|allegories]], a special class of categories.

Any class can be viewed as a category whose only morphisms are the identity morphisms. Such categories are called discrete. For any given [[Set (mathematics)|set]] ''I'', the ''discrete category on I'' is the small category that has the elements of ''I'' as objects and only the identity morphisms as morphisms. Discrete categories are the simplest kind of category.

Any [[Preorder|preordered set]] (''P'', ≤) forms a small category, where the objects are the members of ''P'', the morphisms are arrows pointing from ''x'' to ''y'' when ''x'' ≤ ''y''. Furthermore, if ''≤'' is [[Antisymmetric relation|antisymmetric]], there can be at most one morphism between any two objects. The existence of identity morphisms and the composability of the morphisms are guaranteed by the [[Reflexive relation|reflexivity]] and the [[Transitive relation|transitivity]] of the preorder. By the same argument, any [[Partially ordered set|partially ordered set]] and any [[Equivalence relation|equivalence relation]] can be seen as a small category. Any [[Ordinal number|ordinal number]] can be seen as a category when viewed as an [[Total order|ordered set]].

Any [[Monoid|monoid]] (any [[Algebraic structure|algebraic structure]] with a single associative [[Binary operation|binary operation]] and an [[Identity element|identity element]]) forms a small category with a single object ''x''. (Here, ''x'' is any fixed set.) The morphisms from ''x'' to ''x'' are precisely the elements of the monoid, the identity morphism of ''x'' is the identity of the monoid, and the categorical composition of morphisms is given by the monoid operation.  Several definitions and theorems about monoids may be generalized for categories.

Similarly any [[Group (mathematics)|group]] can be seen as a category with a single object in which every morphism is ''invertible'', that is, for every morphism ''f'' there is a morphism ''g'' that is both [[Morphism#Some specific morphisms|left and right inverse]] to ''f'' under composition. A morphism that is invertible in this sense is called an [[Isomorphism|isomorphism]].

A [[Groupoid|groupoid]] is a category in which every morphism is an isomorphism. Groupoids are generalizations of groups, [[Group action (mathematics)|group action]]s and [[Equivalence relation|equivalence relation]]s. Actually, in the view of category the only difference between groupoid and group is that a groupoid may have more than one object but the group must have only one. Consider a topological space ''X'' and fix a base point <math>x_0</math> of ''X'', then <math>\pi_1(X,x_0)</math> is the [[Fundamental group|fundamental group]] of the topological space ''X'' and the base point <math>x_0</math>, and as a set it has the structure of group; if then let the base point <math>x_0</math> runs over all points of ''X'', and take the union of all <math>\pi_1(X,x_0)</math>, then the set we get has only the structure of groupoid (which is called as the [[Fundamental groupoid|fundamental groupoid]] of ''X''): two loops (under equivalence relation of homotopy) may not have the same base point so they cannot multiply with each other. In the language of category, this means here two morphisms may not have the same source object (or target object, because in this case for any morphism the source object and the target object are same: the base point) so they can not compose with each other.

[[File:Directed.svg|125px|thumb|A directed graph.]]
Any [[Directed graph|directed graph]] generates a small category: the objects are the [[Vertex (graph theory)|vertices]] of the graph, and the morphisms are the paths in the graph (augmented with [[Loop (graph theory)|loop]]s as needed) where composition of morphisms is concatenation of paths. Such a category is called the ''[[Free category|free category]]'' generated by the graph.

The class of all preordered sets with [[Monotonic function|monotonic function]]s as morphisms forms a category, '''Ord'''. It is a [[Concrete category|concrete category]], i.e. a category obtained by adding some type of structure onto '''Set''', and requiring that morphisms are functions that respect this added structure.

The class of all groups with [[Group homomorphism|group homomorphism]]s as [[Morphism|morphism]]s and [[Function composition|function composition]] as the composition operation forms a large category, '''[[Category of groups|Grp]]'''. Like '''Ord''', '''Grp''' is a concrete category. The category '''[[Category of abelian groups|Ab]]''', consisting of all [[Abelian group|abelian group]]s and their group homomorphisms, is a full subcategory of '''Grp''', and the prototype of an [[Abelian category|abelian category]]. Other examples of concrete categories are given by the following table.

{| class="wikitable"
!Category
!Objects
!Morphisms
|-
|'''[[Category of groups|Grp]]'''
|[[Group (mathematics)|group]]s
|[[Group homomorphism|group homomorphism]]s
|-
|'''Mag'''
|[[Magma (algebra)|magma]]s
|[[Magma (algebra)#Morphism of magmas|magma homomorphisms]]
|-
|[[Category of manifolds|'''Man'''<sup>''p''</sup>]]
|smooth manifolds
|''p''-times continuously differentiable maps
|-
|'''[[Category of metric spaces|Met]]'''
|[[Metric space|metric space]]s
|short maps
|-
|'''[[Category of modules|''R''-Mod]]'''
|[[Module (mathematics)|''R''-modules]], where ''R'' is a ring
|[[Module homomorphism|''R''-module homomorphisms]]
|-
|'''Mon'''
|monoids
|[[Monoid#Monoid homomorphisms|monoid homomorphisms]]
|-
|'''[[Category of rings|Ring]]'''
|[[Ring (mathematics)|ring]]s
|[[Ring homomorphism|ring homomorphism]]s
|-
|'''[[Category of sets|Set]]'''
|[[Set (mathematics)|set]]s
|[[Function (mathematics)|function]]s
|-
|'''[[Category of topological spaces|Top]]'''
|[[Topological space|topological space]]s
|continuous functions
|-
|'''Uni'''
|[[Uniform space|uniform space]]s
|uniformly continuous functions
|-
|'''Vect'''<sub>''K''</sub>
|[[Vector space|vector space]]s over the [[Field (mathematics)|field]] ''K''
|''K''-[[Linear map|linear map]]s
|}

Fiber bundles with [[Bundle map|bundle map]]s between them form a concrete category.

The category '''Cat''' consists of all small categories, with [[Functor|functor]]s between them as morphisms.

== Construction of new categories ==

=== Dual category ===
Any category ''C'' can itself be considered as a new category in a different way: the objects are the same as those in the original category but the arrows are those of the original category reversed. This is called the [[Opposite category|''dual'' or ''opposite category'']] and is denoted ''C''<sup>op</sup>.

=== Product categories ===
If ''C'' and ''D'' are categories, one can form the ''product category'' ''C'' × ''D'': the objects are pairs consisting of one object from ''C'' and one from ''D'', and the morphisms are also pairs, consisting of one morphism in ''C'' and one in ''D''. Such pairs can be composed componentwise.

==Types of morphisms==
A [[Morphism|morphism]] ''f'' : ''a'' → ''b'' is called
* a ''[[Monomorphism|monomorphism]]'' (or ''monic'') if it is left-cancellable, i.e. ''fg<sub>1</sub>'' = ''fg<sub>2</sub>'' implies ''g<sub>1</sub>'' = ''g<sub>2</sub>'' for all morphisms ''g''<sub>1</sub>, ''g<sub>2</sub>'' : ''x'' → ''a''.
* an ''[[Epimorphism|epimorphism]]'' (or ''epic'') if it is right-cancellable, i.e. ''g<sub>1</sub>f'' = ''g<sub>2</sub>f'' implies ''g<sub>1</sub>'' = ''g<sub>2</sub>'' for all morphisms ''g<sub>1</sub>'', ''g<sub>2</sub>'' : ''b'' → ''x''.
* a ''bimorphism'' if it is both a monomorphism and an epimorphism.
* a ''retraction'' if it has a right inverse, i.e. if there exists a morphism ''g'' : ''b'' → ''a'' with ''fg'' = 1<sub>''b''</sub>.
* a ''[[Section (category theory)|section]]'' if it has a left inverse, i.e. if there exists a morphism ''g'' : ''b'' → ''a'' with ''gf'' = 1<sub>''a''</sub>.
* an ''[[Isomorphism|isomorphism]]'' if it has an inverse, i.e. if there exists a morphism ''g'' : ''b'' → ''a'' with ''fg'' = 1<sub>''b''</sub> and ''gf'' = 1<sub>''a''</sub>.
* an ''[[Endomorphism|endomorphism]]'' if ''a'' = ''b''. The class of endomorphisms of ''a'' is denoted end(''a'').
* an ''[[Automorphism|automorphism]]'' if ''f'' is both an endomorphism and an isomorphism. The class of automorphisms of ''a'' is denoted aut(''a'').

Every retraction is an epimorphism. Every section is a monomorphism. The following three statements are equivalent:
* ''f'' is a monomorphism and a retraction;
* ''f'' is an epimorphism and a section;
* ''f'' is an isomorphism.

Relations among morphisms (such as ''fg'' = ''h'') can most conveniently be represented with [[Commutative diagram|commutative diagram]]s, where the objects are represented as points and the morphisms as arrows.

==Types of categories==
* In many categories, e.g. '''[[Category of abelian groups|Ab]]''' or '''Vect'''<sub>''K''</sub>, the hom-sets hom(''a'', ''b'') are not just sets but actually [[Abelian group|abelian group]]s, and the composition of morphisms is compatible with these group structures; i.e. is [[Bilinear form|bilinear]]. Such a category is called preadditive. If, furthermore, the category has all finite [[Product (category theory)|products]] and [[Coproduct|coproduct]]s, it is called an additive category. If all morphisms have a [[Kernel (category theory)|kernel]] and a [[Cokernel|cokernel]], and all epimorphisms are cokernels and all monomorphisms are kernels, then we speak of an [[Abelian category|abelian category]]. A typical example of an abelian category is the category of abelian groups.
* A category is called [[Complete category|complete]] if all small [[Limit (category theory)|limits]] exist in it. The categories of sets, abelian groups and topological spaces are complete.
* A category is called [[Cartesian closed category|cartesian closed]] if it has finite direct products and a morphism defined on a finite product can always be represented by a morphism defined on just one of the factors. Examples include '''[[Category of sets|Set]]''' and '''CPO''', the category of [[Complete partial order|complete partial order]]s with [[Scott continuity|Scott-continuous functions]].
* A [[Topos|topos]] is a certain type of cartesian closed category in which all of mathematics can be formulated (just like classically all of mathematics is formulated in the category of sets). A topos can also be used to represent a logical theory.

==See also==
* [[Enriched category]]
* [[Higher category theory]]
* [[Quantaloid]]
* Table of mathematical symbols

==Notes==
{{Reflist}}

==References==
* {{Citation| last1=Adámek |first1=Jiří |last2=Herrlich |first2=Horst |last3=Strecker |first3=George E. |year=1990 |title=Abstract and Concrete Categories |publisher=Wiley  |isbn=0-471-60922-6|url=http://katmat.math.uni-bremen.de/acc/acc.pdf}} (now free on-line edition, [[Software:GNU Free Documentation License|GNU FDL]]).
* {{Citation| last1=Asperti| first1=Andrea| last2=Longo| first2=Giuseppe| year=1991| title=Categories, Types and Structures| publisher=MIT Press| url=https://archive.org/details/categoriestypess00aspe_0| isbn=0-262-01125-5| url-access=registration}}.
* {{Citation| last1=Awodey | first1=Steve | year=2006| title=Category theory| volume=49| series=Oxford logic guides| publisher=Oxford University Press| isbn = 978-0-19-856861-2}}.
*{{citation
 | edition = revised
 | series = Reprints in Theory and Applications of Categories
 | mr = 2178101
 | title = Toposes, Triples and Theories
 | url = http://www.tac.mta.ca/tac/reprints/articles/12/tr12abs.html
 | volume = 12
 | year = 2005}}. 
* {{Citation| last=Borceux| first=Francis| year=1994| chapter=Handbook of Categorical Algebra| title=Encyclopedia of Mathematics and its Applications| location=Cambridge |publisher=Cambridge University Press| volume=50–52| isbn=0-521-06119-9}}.
* {{springer|title=Category|id=p/c020740}}
* {{Citation| last1= Herrlich |first1= Horst |last2=Strecker |first2=George E. |year=2007 |title=Category Theory |publisher= Heldermann Verlag |isbn = 978-3-88538-001-6}}.
* {{Citation| last=Jacobson| first=Nathan|  year=2009| title=Basic algebra| edition=2nd| publisher=Dover| isbn = 978-0-486-47187-7}}.
* {{Citation| last1=Lawvere| first1=William|  last2=Schanuel| first2=Steve| year=1997| title=Conceptual Mathematics: A First Introduction to Categories | publisher=Cambridge University Press| isbn=0-521-47249-0}}.
* {{Citation| last=Mac Lane| first=Saunders|  year=1998| title=[[Categories for the Working Mathematician]]| edition=2nd| series=Graduate Texts in Mathematics |volume=5| publisher=Springer-Verlag| isbn = 0-387-98403-8}}.
* {{Citation| last=Marquis| first=Jean-Pierre| contribution=Category Theory| editor-last=Zalta| editor-first=Edward N.| title=[[Stanford Encyclopedia of Philosophy]]| year=2006| contribution-url=http://plato.stanford.edu/entries/category-theory/}}.
* {{Citation| last1=Sica| first1=Giandomenico | year=2006| title=What is category theory?| volume=3| series=Advanced studies in mathematics and logic| publisher=Polimetrica| isbn = 978-88-7699-031-1}}.
*{{nlab|id=category}}

{{Category theory}}

[[Category:Category theory|*]]
[[Category:Algebraic structures]]

{{Sourceattribution|Category (mathematics)}}