\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{category}

\begin{quote}%
This page is about the concept in [[mathematics]]. For the concept of the same name in [[philosophy]] see at \emph{[[category (philosophy)]]}.


\end{quote}
\hypertarget{context}{}\subsubsection*{{Context}}\label{context}

\hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory}

[[!include category theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak
\noindent\hyperlink{OneCollectionOfMorphisms}{With one collection of morphisms}\dotfill \pageref*{OneCollectionOfMorphisms} \linebreak
\noindent\hyperlink{AFamilyOfCollectionsOfMorphisms}{With a family of collections of morphisms}\dotfill \pageref*{AFamilyOfCollectionsOfMorphisms} \linebreak
\noindent\hyperlink{equivalence_between_the_two_definitions}{Equivalence between the two definitions}\dotfill \pageref*{equivalence_between_the_two_definitions} \linebreak
\noindent\hyperlink{size}{Size issues}\dotfill \pageref*{size} \linebreak
\noindent\hyperlink{alternative_definitions}{Alternative definitions}\dotfill \pageref*{alternative_definitions} \linebreak
\noindent\hyperlink{EquivalenceDefinitions}{Equivalent definitions}\dotfill \pageref*{EquivalenceDefinitions} \linebreak
\noindent\hyperlink{generalizations}{Generalizations}\dotfill \pageref*{generalizations} \linebreak
\noindent\hyperlink{internal_categories}{Internal categories}\dotfill \pageref*{internal_categories} \linebreak
\noindent\hyperlink{enriched_categories}{Enriched categories}\dotfill \pageref*{enriched_categories} \linebreak
\noindent\hyperlink{indexed_categories}{Indexed categories}\dotfill \pageref*{indexed_categories} \linebreak
\noindent\hyperlink{multicategories_etc}{Multicategories etc.}\dotfill \pageref*{multicategories_etc} \linebreak
\noindent\hyperlink{higher_categories}{Higher categories}\dotfill \pageref*{higher_categories} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{basic_notions}{Basic notions}\dotfill \pageref*{basic_notions} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

\begin{itemize}%
\item A category consists of a collection of things and binary relationships (or transitions) between them, such that these relationships can be combined and include the ``identity'' relationship ``is the same as.''


\item A category is a [[quiver]] (a [[directed graph]] with multiple edges) with a rule saying how to \emph{compose} two edges that fit together to get a new edge. Furthermore, each vertex has an edge starting and ending at that vertex, which acts as an identity for this composition.


\item A category is a combinatorial model for a [[directed space]] -- a ``directed [[homotopy 1-type]]'' in some sense. It has ``points'', called \emph{objects}, and also directed ``paths'', or ``processes'' connecting these points, called \emph{morphisms}. There is a rule for how to compose paths; and for each object there is an identity path that starts and ends there.


\item More precisely, a category consists of a collections of [[object|objects]] and a collection of [[morphism|morphisms]]. Every morphism has a [[source]] object and a [[target]] object. If $f$ is a morphism with $x$ as its source and $y$ as its target, we write

\begin{displaymath}
f : x \to y
\end{displaymath}
and we say that $f$ is a morphism from $x$ to $y$. In a category, we can [[composition|compose]] a morphism $g : x \to y$ and a morphism $f : y \to z$ to get a morphism $f \circ g : x \to z$. Composition is associative and satisfies the left and right unit laws.



\end{itemize}
A good example to keep in mind is the category [[Set]], in which the objects are sets and a morphism $f : x \to y$ is a function from the set $x$ to the set $y$. Here composition is the usual composition of functions.

For more background on and context for categories see

\begin{itemize}%
\item [[category theory]].

\end{itemize}
\hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions}

There are two broad ways to write down the definition of category; in the usual [[foundations of mathematics]], these two definitions are equivalent. It is good to know both, for several reasons:

\begin{itemize}%
\item Each introduces its own system of notation, both of which are useful in other parts of category theory, so one should know them.
\item One definition generalises quite nicely to the notion of [[internal category]], while the other generalises quite nicely to the notion of [[enriched category]]; these are both important concepts.
\item When examining alternative foundations, sometimes one definition or the other may be more appropriate; in any case, one will want to examine the question of their equivalence.

\end{itemize}
The two definitions may be distinguished by whether they use a single collection of all [[morphisms]] or several collections of morphisms, a [[family of sets|family of collections]] indexed by pairs of [[objects]].

\hypertarget{OneCollectionOfMorphisms}{}\subsubsection*{{With one collection of morphisms}}\label{OneCollectionOfMorphisms}

A \textbf{category} $C$ consists of

\begin{itemize}%
\item a [[collection]] (see \hyperlink{size}{Size issues}) $C_0$ of \textbf{[[objects]]};


\item a collection $C_1$ of \textbf{[[morphisms]]} (or \textbf{arrows});


\item two [[functions]] $s, t\colon C_1 \to C_0$ which assign, to every morphism, its \textbf{[[source]]} (or \textbf{domain}) and \textbf{[[target]]} (or \textbf{codomain});


\item a [[partial function]] $\circ\colon C_1 \times C_1 \to C_1$ which assigns, to any pair of morphisms $f, g$ such that $t(f) = s(g)$, their \textbf{[[composite]]} morphism $g \circ f \in C_1$ (also written $g f$ or sometimes $f;g$--- see [[diagrammatic order]]);


\item a function $id\colon C_0 \to C_1$ which assigns to each object $x$ a morphism $id_x$ or $1_x$, the \textbf{[[identity morphism]]} on $x$;


\item such that the following properties are satisfied:

\begin{itemize}%
\item source and target are respected by composition: $s(g \circ f) = s(f)$ and $t(g\circ f) = t(g)$;


\item source and target are respected by identities: $s(1_x) = x$ and $t(1_x) = x$;


\item composition is [[associative]]: $(h \circ g)\circ f = h\circ (g \circ f)$ whenever $t(f) = s(g)$ and $t(g) = s(h)$;


\item composition satisfies the [[unit law|left and right unit laws]]: if $s(f) = x$ and $t(f) = y$, then $1_y \circ f = f = f \circ 1_x$.



\end{itemize}


\end{itemize}
People also often write $x \in C$ instead of $x \in C_0$ as a short way to indicate that $x$ is an object of $C$. Also, some people write $Ob(C)$ and $Mor(C)$ instead of $C_0$ and $C_1$. One usually writes $f\colon x \to y$ if $f \in C_1$ to state that $s(f) = x$ and $t(f) = y$. Finally, people often write $hom(x,y)$, $hom_C(x,y)$, or $C(x,y)$ for the collection of morphisms $f\colon x \to y$.

If the [[identity]]-assigning map and its axiom is omitted, then one speaks of a \emph{[[semicategory]]}.

\hypertarget{AFamilyOfCollectionsOfMorphisms}{}\subsubsection*{{With a family of collections of morphisms}}\label{AFamilyOfCollectionsOfMorphisms}

A \textbf{category} $C$ consists of

\begin{itemize}%
\item a [[collection]] (see \hyperlink{size}{Size issues}) $C_0$ of \textbf{[[objects]]};


\item for each pair $x,y$ of objects, a collection $C_1(x,y)$ of \textbf{[[morphisms]] from $x$ to $y$};


\item for each triple $x,y,z$ of objects, a [[function]] $\circ\colon C_1(y,z) \times C_1(x,y) \to C_1(x,z)$ which assigns, to any appropriate pair of morphisms $f, g$, their \textbf{[[composite]]} morphism $g \circ f$ (also written $g f$ or sometimes $f;g$--- see [[diagrammatic order]]);


\item for each object $x$, an [[element]] $id_x$ or $1_x$ of $C_1(x,x)$, the \textbf{[[identity morphism]]} on $x$;


\item such that the following properties are satisfied:

\begin{itemize}%
\item composition is [[associative]]: for each quadruple $w,x,y,z$ of objects, if $f \in C_1(y,z)$, $g \in C_1(x,y)$, and $h \in C_1(w,x)$, then $(f \circ g)\circ h = f\circ (g \circ h)$;


\item composition satisfies the [[unit law|left and right unit laws]]: for each pair $x,y$ of objects, if $f \in C_1(x,y)$, then $1_y \circ f = f = f \circ 1_x$.



\end{itemize}


\end{itemize}
People also often write $x \in C$ instead of $x \in C_0$ as a short way to indicate that $x$ is an object of $C$. Also, some people write $Ob(C)$ instead of $C_0$ and $hom(x,y)$, $hom_C(x,y)$, or $C(x,y)$ instead of $C_1(x,y)$. One usually writes $f\colon x \to y$ to state that $f \in C_1(x,y)$. Finally, people often write $C_1$ or $Mor(C)$ for the [[disjoint union]] $\biguplus_{x \in C_0} \biguplus_{y \in C_0} C_1(x,y)$.

\hypertarget{equivalence_between_the_two_definitions}{}\subsubsection*{{Equivalence between the two definitions}}\label{equivalence_between_the_two_definitions}

Given a one-collection-of-morphisms category $C_1\rightrightarrows C_0$, we define a family-of-collections-of-morphisms category by taking $C_1(x,y)$ to be the [[preimage]] of $(x,y)$ under the function $(s,t):C_1 \to C_0\times C_0$. Conversely, given a family-of-collections-of-morphisms category we define a one-collection-of-morphisms category by taking $C_1$ to be the [[disjoint union]] of the families of morphisms $C_1 = \coprod_{x,y\in C_0} C_1(x,y)$. With the straightforward definitions of [[functor]] and [[natural transformation]] in both cases, this sets up a strict [[2-equivalence]] of [[2-categories]].

Note, though, that this 2-equivalence is not an \emph{isomorphism} of 2-categories, because the disjoint union operation has to ``tag'' each morphism with its domain and codomain. It seems that the strongest thing that can be said is that, in a [[material set theory]], if a family-of-collections-of-morphisms category $C$ has the property that sets $C_1(x,y)$ are all disjoint, then there is a one-collection-of-morphisms category with $C_1 = \bigcup_{x,y\in C_0} C_1(x,y)$ (the \emph{non}-disjoint union) that gives rise to $C$ on the nose. The notion of [[protocategory]] is a way to formalize a family-of-collections-of-morphisms category together with the information about how its hom-sets ``overlap''.

In ordinary category theory one rarely specifies which of the two definitions is being used, although often language implicitly suggests that it is the latter, e.g. when defining a category one first specifies the objects and then specifies what ``the morphisms from $X$ to $Y$ are'' rather than specifying what ``a morphism'' is and then what the domain and codomain of each morphism are. Indeed, when defining a category in this way, one rarely worries about whether the hom-sets are disjoint, meaning that it must be the second definition in use. Even for the prototypical category [[Set]], if constructed in a material-set-theoretic foundation like [[ZFC]], the natural definition ``a morphism from $X$ to $Y$ is a function, i.e. a subset of $X\times Y$ that is total and functional'', produces hom-sets that are not disjoint, since a total and functional set of ordered pairs can have any codomain that is a superset of its range. Moreover, categorical constructions do not ``naturally'' preserve disjointness of homsets, e.g. in the [[category of elements]] $el(P)$ of a functor $P:C\to Set$ a given morphism in $C$ can ``be'' a morphism between many different elements of $P$, and similarly for a [[slice category]] and so on.

\hypertarget{size}{}\subsubsection*{{Size issues}}\label{size}

We said a category has a `collection' of objects and `collection'(s) of morphisms. A category is said to be [[small category|small]] if these collections are all [[sets]] --- as opposed to [[proper class|proper classes]], for example. (The alternatives depend on ones [[foundations|foundations for mathematics]].)

Similarly, a category is [[locally small category|locally small]] if $C_1(x,y)$ is a set for every pair of objects $x,y$ in that category. The most common motivating examples of categories (such as [[Set]]) are all locally small but not small (unless one restricts their objects in some way).

\hypertarget{alternative_definitions}{}\subsubsection*{{Alternative definitions}}\label{alternative_definitions}

For some purposes it is useful or necessary to vary the way the ordinary definition of category is expressed. See

\begin{itemize}%
\item [[single-sorted definition of a category]] -- a variant of the first definition, with only \emph{one} collection at all ($C_1$, no $C_0$). This is sometimes convenient for technical reasons.


\item [[type-theoretic definition of category]] -- a variant of the second definition, interpreted explicitly in [[dependent type theory]].


\item [[protocategory]] -- a sort of mixture of the two definitions, in which all the hom-sets $C_1(x,y)$ are subsets of a single set $C_1$, but not necessarily disjoint.



\end{itemize}
\hypertarget{EquivalenceDefinitions}{}\subsubsection*{{Equivalent definitions}}\label{EquivalenceDefinitions}

A [[category]] is equivalently

\begin{itemize}%
\item a [[monad]] in the [[2-category]] of [[spans]] of [[sets]];


\item a [[monoid]] in the [[monoidal category]] of endospans on the set of objects;


\item a [[simplicial set]] which satisfies the [[Segal conditions]];


\item a [[simplicial set]] which satisfies the [[weak Kan complex]] conditions strictly:


\item hence a [[directed homotopy type theory|directed homotopy type]] which is ``1-truncated'';


\item 

\end{itemize}
\hypertarget{generalizations}{}\subsubsection*{{Generalizations}}\label{generalizations}

\hypertarget{internal_categories}{}\paragraph*{{Internal categories}}\label{internal_categories}

The first definition, with a single collection $C_1$ of morphisms, generalises to the notion of [[internal category]]. Essentially, we define a category internal to (some other category) $D$ as above, with `collection' interpreted as an object of $D$ and `function' interpreted as a morphism of $D$. In particular, a category internal to [[Set]] is the same thing as a small category.

\hypertarget{enriched_categories}{}\paragraph*{{Enriched categories}}\label{enriched_categories}

The second definition of a category, as a family $C_1(x,y)$ of collections of morphisms, generalises to the notion of [[enriched category]]: we define a category enriched over (some other category) $D$ as above, with the collection of objects still a `collection' as before, but with objects of $D$ in place of the collections of morphisms and morphisms of $D$ in place of the various functions. In particular, a category enriched over [[Set]] is the same thing as a locally small category.

\hypertarget{indexed_categories}{}\paragraph*{{Indexed categories}}\label{indexed_categories}

The notion of [[indexed category]] captures the idea of woking ``over a base'' other than [[Set]].

\hypertarget{multicategories_etc}{}\paragraph*{{Multicategories etc.}}\label{multicategories_etc}

There is a generalization of the notion of catgeory where one allows a morphism to go from several objects to a single object. This is called a [[multicategory]] or [[operad]]. If we additionally allow a morphism to go \emph{to} several objects, we obtain a \emph{[[polycategory]]} or \emph{[[PROP]]}.

\hypertarget{higher_categories}{}\paragraph*{{Higher categories}}\label{higher_categories}

See [[higher category theory]].

\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

There is the beginning of a [[database of categories]] listing well-known categories (with links to articles on these categories, if such articles exist) and some of their properties.

The classic example of a category is [[Set]], the category with [[set]]s as objects and [[function]]s as morphisms, and the usual composition of functions as composition. Here are some other famous examples, which arise as variations on this theme:

\begin{itemize}%
\item [[Vect]] - [[vector space]]s as objects, linear maps as morphisms.


\item [[Grp]] - [[group]]s as objects, homomorphisms as morphisms.


\item [[Top]] - [[topological space]]s as objects, continuous functions as morphisms.


\item [[Diff]] - smooth [[manifold]]s as objects, smooth maps as morphisms.


\item [[Ring]] - [[ring]]s as objects, ring homomorphisms as morphisms.



\end{itemize}
Note that in all these cases the morphisms are actually special sorts of functions. these are [[concrete categories]]. That need not be the case in general!

These classic examples are the original motivation for the term ``category'': all of the above categories encapsulate one ``kind of mathematical structure''. These are often called ``concrete'' categories (that term also has a [[concrete category|technical definition]] that these examples all satisfy). But just as widespread in applications as these categorization examples of categories are are other categories (often ``[[small category|small]]'' ones) which, roughly, model something like \emph{states} and \emph{processes} of some system.

\begin{itemize}%
\item \textbf{Poset} A [[partial order|poset]] can be thought of as a category with its elements as objects and one morphism in each $hom(x,y)$ if $x$ is less than or equal to $y$, but none otherwise.


\item \textbf{Group} A [[group]] is just a category where there's one object and all the morphisms have inverses - we call the morphisms ``elements'' of the group. This may seem weird, but it's actually a very useful viewpoint. Here's another way to say it: \emph{A group is a [[groupoid]] with a single object}.


\item \textbf{Monoid} More generally, a [[monoid]] is a category with a single object. In fact, this is one way to motivate the concept of categories: categories are the [[horizontal categorification|many object version]] of monoids.


\item \textbf{Groupoid} A [[groupoid]] is a category in which all morphisms are [[isomorphism]]s.


\item \textbf{Quiver} A [[quiver]] may be identified with the [[free category]] on its [[directed graph]]. Given a directed graph $G$ with collection of vertices $G_0$ and collection of edges $G_1$, there is the \emph{[[free functor|free]] category} $F(G)$ on the graph whose collection of objects coincides with the collection of vertices, and whose collection of morphisms consists of finite sequences of edges in $G_1$ that fit together head-to-tail. The composition operation in this free category is the concatenation of sequences of edges.


\item \textbf{Universal structure} A category bearing a structure making it [[initial object|initial]] (or 2-initial) in some [[doctrine]]. Examples include the [[permutation category]] as the free symmetric monoidal category generated by a single object, or the [[simplex category]] which is initial among monoidal categories equipped with a monoid.



\end{itemize}
\hypertarget{basic_notions}{}\subsection*{{Basic notions}}\label{basic_notions}

A homomorphism between categories is a [[functor]].

This way [[small categories]] themselves form a category, the category [[Cat]] whose objects are small categories and whose morphisms are functors. This naturally enhances to a [[2-category]] whose [[2-morphism]]s are [[natural transformation]]s between functors.

An [[equivalence of categories]] is an equivalence in [[Cat]], hence a pair of functors going back and forth, that are each others inverse up to [[natural isomorphism]].

Weaker than the notion of a pair of functors exhibiting an equivalence is the notion of a pair of [[adjoint functor]]s.

Other standard operations on categories include

\begin{itemize}%
\item [[opposite category]]


\item [[localization]]


\item [[geometric realization of categories]]



\end{itemize}
\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[enriched category]]

\begin{itemize}%
\item [[continuous category]]

\end{itemize}

\item [[EI-category]]


\item [[0-category]], [[(0,1)-category]]


\item \textbf{category}

[[semicategory]]


\item [[2-category]]


\item [[3-category]]


\item [[n-category]]


\item [[(∞,0)-category]]


\item [[(n,1)-category]]


\item [[(∞,1)-category]]


\item [[(∞,2)-category]]


\item [[(∞,n)-category]]


\item [[(n,r)-category]]



\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

(See also the references at \emph{[[category theory]]}.)

The concept originates in

\begin{itemize}%
\item [[Samuel Eilenberg]], [[Saunders MacLane]], \emph{General Theory of Natural Equivalences}, Transactions of the American Mathematical Society Vol. 58, No. 2 (Sep., 1945), pp. 231-294 (\href{http://www.jstor.org/stable/1990284}{JSTOR})

\end{itemize}
The standard textbook is

\begin{itemize}%
\item [[Saunders MacLane]], \emph{[[Categories Work|Categories for the working mathematician]]}

\end{itemize}
Expositions include

\begin{itemize}%
\item Jaap van Oosten, \href{http://www.math.uu.nl/people/jvoosten/syllabi/catsmoeder.pdf}{Basic category theory}.


\item Andrea Schalk and H. Simmons, \href{http://www.cs.man.ac.uk/~hsimmons/BOOKS/CatTheory.pdf}{An introduction to category theory in four easy movements}, notes for a course offered as part of the MSc. in Mathematical Logic, Manchester University.


\item Daniele Turim, \href{http://www.dcs.ed.ac.uk/home/dt/CT/categories.pdf}{Category theory lecture notes}, 1996-2001. Based on Mac Lane's book (1998).


\item A. Martini, H. Ehrig, and D. Nunes, \href{http://citeseer.ist.psu.edu/martini96element.html}{Elements of basic category theory}, Technical Report 96-5, Technical University Berlin.



\end{itemize}
A textbook that introduces categories by examples arising in [[mathematical physics]] is

\begin{itemize}%
\item [[Robert Geroch]], \emph{Mathematical Physics}, Chicago 1985

\end{itemize}
A textbook with an eye towards the theory of [[categories of sheaves]] and their application in [[homological algebra]] is

\begin{itemize}%
\item Kashiwara, Shapira, \emph{[[Categories and Sheaves]]}

\end{itemize}
The definition of categories in the [[foundations]] of [[homotopy type theory]] (see at \emph{[[internal category in homotopy type theory]]}) is discussed in

\begin{itemize}%
\item [[Benedikt Ahrens]], [[Chris Kapulkin]], [[Michael Shulman]], \emph{Univalent categories and the Rezk completion}, Mathematical Structures in Computer Science 25.5 (2015): 1010-1039 (\href{http://arxiv.org/abs/1303.0584}{arXiv:1303.0584})


\item [[Paolo Capriotti]], [[Nicolai Kraus]], \emph{Univalent Higher Categories via Complete Semi-Segal Types} (\href{https://arxiv.org/abs/1707.03693}{arXiv:1707.03693})


\item [[Jason Gross]], [[Adam Chlipala]], [[David Spivak]], \emph{Experience Implementing a Performant Category-Theory Library in Coq} (\href{http://arxiv.org/abs/1401.7694}{arXiv:1401.7694})



\end{itemize}
For more references see [[category theory]].

[[!redirects category]] [[!redirects categories]] [[!redirects Category]] [[!redirects Categories]]



\end{document}