Category Theory

Table of Contents

MEGA resource:

Notation

Definition

A category $C$ consists of the three mathematical entities:

  1. A class $\text{Ob}(C)$, whose elements are the objects
  2. A class $\text{Hom}(C)$, whose elements are called morphisms or maps or arrows. Each morphism $f$ has a source object $A$ and target object $B$

  3. A binary operation $\circ$, called composition of morphisms, such that for any three objects $A$, $B$, and $C$, we have

    \begin{equation*} \text{Hom}(A, B) \times \text{Hom}(B, C) \to \text{Hom}(A, B) \end{equation*}

    The composition of $f: A \to B$ and $g: B \to C$ is governed by two axioms:

    1. Associativity:

      \begin{equation*} h \circ \big( g \circ f \big) = \big( h \circ g \big) \circ f \end{equation*}

    2. Identity map:

      \begin{equation*} \exists 1_X: X \to X : 1_A \circ f = f \circ 1_B \end{equation*}

Category of Sets

The category $\text{Set}(V)$ of $V \text{-sets}$ for any partially ordered set $V$, where

  • a $V \text{-set}$ is a function $A: X \to V$ from a set $X$ to $V$

  • a morphism $A \to B$ of $V \text{-sets}$ $A: X \to V$ and $B: Y \to V$ is a function

    \begin{equation*} f: X \to Y \quad \text{s.t.} \quad A(x) \le B \big( f(x) \big), \quad \forall x \in X \end{equation*}

Let $A = \left\{ \smiley \right\}$, i.e. $A$ be the singleton set, then, for any set $X$ there is an isomorphism of sets

\begin{equation*} X \cong \text{Hom}_{\text{Set}}(A, X) \end{equation*}

Just to make the point clear here, for the set $X$, $\text{Hom}_{\text{Set}}(A, X) = \{ f_x: \left\{ \smiley \right\} \to X \}$ where $f_x$ is defined by the mapping:

\begin{equation*} f_x(\smiley) = x \end{equation*}

Products

Let $X$ and $Y$ be sets.

The product of $X$ and $Y$, denoted $X \times Y$, is defined as the set of ordered pairs $(x, y)$ where $x \in X$ and $y \in Y$. That is,

\begin{equation*} X \times Y = \left\{ (x, y) \mid x \in X, y \in Y \right\} \end{equation*}

There are two natural projections $\pi_1: X \times Y \to X$ and $\pi_2: X \times Y \to Y$.

products.png

Let $X$ and $Y$ be sets.

For any set $A$ and functions $f: A \to X$ and $g: A \to Y$ there exist a unique function $A \to X \times Y$ such that the following diagram commutes:

universal-property-of-products.png

We might write the unique function as

\begin{equation*} f \times g: A \to X \times Y \end{equation*}

Suppose we are given $f,g$ as above. To provide a function $\ell: A \to X \times Y$ is equivalent of providing an element $\ell(a) \in X \times Y$ for each $a \in A$.

We need such a function $\ell$ for which

\begin{equation*} \pi_1 \circ \ell = f, \quad \pi_2 \circ \ell = g \end{equation*}

An element of $X \times Y$ is an ordered pair $(x,y)$, and so we can use

\begin{equation*} \ell(a) = (x, y) \iff x = \pi_1(x, y) = f(a) \text{ and } y = \pi_2(x, y) = g(a) \end{equation*}

Hence, it's necessary and sufficient to define

\begin{equation*} \big( f \times g \big)(a) = \big( f(a), g(a) \big), \quad \forall a \in A \end{equation*}

Coproducts

Let $X$ and $Y$ be sets.

The coproduct of $X$ and $Y$, denoted $X \sqcup Y$ is defined as the disjoint union of $X$ and $Y$, i.e. the set for which an element is either an element of $X$ or an element of $Y$.

If something is an element of both $X$ and $Y$ then we include both copies, and distinguish between them, in $X \sqcup Y$.

There are two natural inclusion functions

\begin{equation*} i_1: X \to X \sqcup Y \quad \text{and} \quad i_2: Y \to X \sqcup Y \end{equation*}

coproduct-inclusions.png

Finite limits in Set

Pullbacks

Suppose the given diagram of sets and functions below

pullback-of-sets.png

Its fiber product is the set

\begin{equation*} X \times_Z Y := \left\{ \big( x, w, y \big) \mid f(x) = w = g(y), \quad w \in Z \right\} \end{equation*}

There are obvious projections

\begin{equation*} \begin{split} \pi_1 : X \times_Z Y \to X \quad & \text{and} \quad \pi_2: X \times_Z Y \to Y \\ \pi_1(x, w, y) = x \quad & \quad \quad \quad \pi_2(x, w, y) = y \end{split} \end{equation*}

Note that if

\begin{equation*} W = X \times_Z Y \end{equation*}

then the diagram pullback-of-sets-2.png commutes.

Given the setup in the diagram above, we define the pullback of $X$ and $Y$ over $Z$ to be any set $W$ for which we have an isomorphism

\begin{equation*} W \overset{\cong}{\to} X \times_Z Y \end{equation*}

The corner symbol denotes that $W$ is the pullback.

Sometimes you'll see the fiber product $W = X \times_Z Y$ denoted $f \times_Z g$.

Suppose given the diagram of sets and functions as below.

universal-property-of-pullbacks-1.png

For any set $A$ and commutative solid arrow diagram as below (i.e. functions $f: A \to X$ and $g: A \to Y$ such that $t \circ f = u \circ g$),

universal-property-of-pullbacks-2.png

there exists a unique arrow $f \times_Z g: A \to X \times_Z Y$ making everything commmute,

\begin{equation*} f = \pi_1 \circ \big( f \times_Z g \big) \quad \text{and} \quad g = \pi_2 \circ \big( f \times_Z g \big) \end{equation*}

Category of Fuzzy Sets

The category of fuzzy subsets is denoted

\begin{equation*} \mathscr{F} = \text{Set}([0, 1]) \end{equation*}

The objects of $\mathscr{F}$ are all pairs $(X, A)$ where

  • $X$ is a set
  • $A: X \to [0, 1]$ is a function from $X$ to the unit interval

The maps of $\mathscr{F}$ are defined by

\begin{equation*} \text{Map}_{\mathscr{F}} \Big( (X, A), (Y, B) \Big) = \left\{ f \in \text{Map}_{\mathscr{S}}(X, Y): A(x) \le B f(x), \forall x \in X \right\} \end{equation*}

where $\mathscr{S}$ denotes the category of sets.

  • With composition simply being the composition of functions

Course

Notation

  • morphism is a structure-preserving map

Lecture 1

A category $\mathscr{C}$ consists of

  1. A collection $\mathrm{ob}(\mathscr{C})$ of objects $A, B, C, \dots$
  2. A collection $\mathrm{mor}(\mathscr{C})$ of morphisms $f, g, h, \dots$
  3. Two operations $\mathrm{dom}$ and $\mathrm{cod}$ from $\mathrm{mor}(\mathscr{C})$ to $\mathrm{ob}(\mathscr{C})$: we write $A \overset{f}{\longrightarrow} B$ for "$f \in \mathrm{mor}(\mathscr{C})$ and $\mathrm{dom}(f) = A$ and $\mathrm{cod}(f) = B$".
  4. An operation $A \mapsto 1_A$ from $\mathrm{ob}(\mathscr{C})$ to $\mathrm{mor}(\mathscr{C})$, s.t. $A \overset{1_A}{\longrightarrow} A$
  5. A partial binary operation $(f, g) \mapsto fg$ on $\mathrm{mor}(\mathscr{C})$, defined iff $\mathrm{dom}(f) = \mathrm{cod}(g)$, and satisfying $\mathrm{dom}(fg) = \mathrm{dom}(g)$, $\mathrm{cod}(fg) = \mathrm{cod}(f)$.

  6. Satisfying

    \begin{equation*} 1_B f = f = f 1_A, \quad \forall A \overset{f}{\longrightarrow} B \end{equation*}
  7. $f(gh) = (fg)h$ whenever it makes sense (i.e. domain- and co-domain-conditions in (3) are satisfied)
  1. We don't require $\mathrm{ob}(\mathscr{C})$ and $\mathrm{mor}(G)$ to be sets
    • If they are sets, we call $\mathrm{\mathscr{C}}$ small
  2. Could formualte the definition with "morphism" as the only primitive notion, identifying "objects" $\mor(\mathscr{C} )$ with identity morphisms.
    • However, in practice the objects are often logically prior to the morphisms

Examples

  1. The category $\mathrm{Set}$ has all sets as objects, and all functions between them as morphisms.
    • Formally, morphisms are pairs $(f, B)$ where $f$ is a set-theoretic function and $B = \cod( f, B)$
  2. Algebraic ones:
    • $\mathrm{Gr}$ is the category of groups and group homomorphisms
    • $\mathrm{Rng}$ is the category of rings and ring homomorphisms
    • $\mathrm{Mod}_{\mathbb{R}}$ is the category of R-modules and R-module homomorphisms, for a particular ring $R$
  3. Topological:
    • $\mathrm{Top}$ is the category of topological spaces with continuous maps as morphisms
    • $\mathrm{Mf}$ is the category of smooth manifolds and $C^{\infty}$ maps as morphisms
  4. The category $\mathrm{Htpy}$ has the same objects as $\mathrm{Top}$, but morphisms are homotopy classes of continuous maps.

    • More generally, given an equivalence relation $\sim$ on $\mor(\mathscr{C} )$ s.t.

      1. $f \sim g$ implies $\dom(f) = \dom(g)$ and $\cod(f) = \cod(g)$
      2. $f \sim g$ implies $fh \sim gh$ and $kf \sim kg$ whenever the composites are defined

      we have a new category $\mathscr{C} / \sim$ with the same objects as $\mathscr{C}$ but $\sim$ equivalence classes as morphisms

  5. The category of relations, $\mathrm{Rel}$, has the same objects as $\mathrm{Set}$, but morphisms $A \longrightarrow B$ are relations $R \subseteq A times B$ with composition of $A \overset{R}{\longrightarrow} B \overset{S}{\longrightarrow} C$ defined to be

    \begin{equation*} \left\{ (a, c) \mid \exists b \in B, (a, b) \in R \land (b, c) \in S \right\} \end{equation*}
    • The category $\mathrm{Part}$ also has sets as objects, but morphisms are partial functions, i.e. functions $A' \longrightarrow B$ for some $A' \subseteq A$
  6. For any category $\mathscr{C}$, the opposite category $\mathscr{C}^{\mathrm{op}}$ has the same objects and morphisms as $\mathscr{C}$, but the $\dom$ and $\cod$ are interchanged, and thus the order of composition has to be interchanged, i.e. $fg$ in $\mathscr{C}^{\mathrm{op}}$ is $gf$ in $\mathscr{C}$.
    • Hence we have the duality principle: if $P$ is a true statement about categories, then so is the statement I get by reversing all the arrows, denoted $P^*$.
  7. A category with a single object $*$ has $\dom(f) = \cod(f) = *$ for all morphisms $f$, and so composition is defined everywhere. Hence a samll category with one object may be "identified" with a monoid (i.e. a semigroup with 1)
    • In particular, a group is a small category with one object in which all morphisms are isomorphisms.
  8. A (Brandt) groupoid is a category in which all morphisms as isomorphisms.
    • E.g. for any category $\mathscr{C}$, $\mathrm{Core}(\mathscr{C})$ has the same objects as $\mathscr{C}$, but only the isomorphisms of $\mathscr{C}$ as morphisms
    • Also, for any topological space $X$, the fundamental groupoid $\pi(X)$ has points of $X$ as objects and morephisms $x \longrightarrow y$ are (homotopy classes of) paths $u: [0, 1] \to X$ with $u(0) = x$ and $u(1) = y$.