\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Algebra::Aluffi

Category. Definition.


A category \( \cat{C} \) consists of:

  • a class of objects, denoted as \( \catobj{C} \)
  • a set, denoted as \( \cathom{C}(A, B) \), for any objects \( A \) and \( B \) of \( \cat{C} \). The elements are called morphisms.

The set of morphisms must have the following properties:

For each object \( A \in \catobj{C} \), there exists (at least) one morphism \( 1_A \in \cathom{C}(A, A) \), called the identity on \( A\).
Morphisms can be composed: any two morphisms \( f \in \cathom{C}(A, B) \) and \( g \in \cathom{C}(B, C) \) determine the existance of another morphism \( gf \in \cathom{C}(A, C) \).
Associativity of composition
For any \( f \in \cathom{C}(A, B) \), \( g \in \cathom{C}(B, C) \) and \( h \in \cathom{C}(C, D) \), we have:
\[ (hg)f = h(gf). \]
Identity law
The identity morphisms are identities with respect to composition. For any \( f \in \cathom{C}(A, B) \), we have:
\[ f1_A = f, \quad 1_Bf = f\]
Morphism sets are disjoint
For any \( A, B, C, D \in \catobj{C} \), then \( \cathom{C}(A, B) \) and \( \cathom{C}(C, D) \) are disjoint unless \( A = C \) and \( B = D \).

Composition as the existance of a function

The statement of morphism composition above can be stated alternatively as the existance of a function.

For any \(A, B, C \in \catobj{C} \), there exists a function \( \cathom{C}(A, B) \times \cathom{C}(B, C) \to \cathom{C}(A, C) \) which is denoted as \( fg \).

The existance of a function imposes the requirement that for any element of the domain \( \cathom{C}(A, B) \times \cathom{C}(B, C) \) there must be an element in the co-domain \( \cathom{C}(A, C) \). The function existance requirement allows for an empty domain if one or both of \( \cathom{C}(A, B) \) or \( \cathom{C}(B, C) \) are empty.

Using functions to imply non-empty sets

I find the following bi-implication interesting:

Let \( S_a \) and \( S_b \) be sets. Then

\[ (S_a \neq \emptyset \implies S_b \neq \emptyset) \iff \exists f : S_a \to S_b \]

This bi-implication allows function existance to be used instead of the LHS. How does the nature of morphism composition change when the RHS is replaced with the LHS of the bi-implication above? Maybe this has an effect on what we view as the datum of a category.


Category of sets

There is a category whose objects are sets and whose morphisms are all the functions between sets. This set often is given special syntax, such as \( \mathrm{Set} \) or \( \mathcal{Set} \).

Category from relation

Let \( S \) be a set and \( \sim \) be a relation on \( S \) which is both reflexive and transitive. Then we can form a category like so:

  • The elements of \( S \) are the objects of the category.
  • For some \( a, b \in S \), let \( \cathom{}(a, b) = (a, b) \) iff \( a \sim b \), else let \( \cathom{}(a, b) = \emptyset \).

It's best to keep in mind the relation \( \sim \) as being represented by the graph \( \Gamma \subseteq S \times S \), where \( (a,b) \in \Gamma \) iff \( a \sim b \). The case where \( \sim \) is the equivalence relation '=' and thus all morphisms are identity morphisms, produces a category which is said to be discrete.

This example demonstrates the flexibility of the definition of morphisms: the morphisms do not need to be functions, they can be elements of a set (or any other type of object) as long as the requirements of the morphisms in the above definition are satisfied.


Aluffi, p19
Leinster, p11