Category Theory

category-theory.md

Category Theory

Sets and classes

A class in set theory, is a collection of sets that can be unambiguously defined by a property that all of its members share. By this definition, every set is a class, and classes that are also sets are called small classes. Classes that are not sets are called proper classes.

Two example of proper classes are any collection of vector spaces, such as the collection all the sets obtained from the cartesian product of $\mathbb{R}$ with itself ($\mathbb{R}$, $\mathbb{R^2}$, $\mathbb{R^3}$, $\mathbb{R^4}$ and so on), and ordinal numbers, a generalization of natural numbers.

Categories

A Category $C$ consists of these three entities:

• A class of objects $ob(C)$.
• A class of morphisms $hom(C)$. Each $f \in hom(C)$ is a relation $f : X \rightarrow Y$, where $X, Y \in obj(C)$.
• A composition function $\circ$ between morphisms, so that if $f : X \rightarrow Y$ and $g : Y \rightarrow Z$, the composition $g \circ f$ is a morphism $g \circ f : X \rightarrow Z$.

The composition function needs to satisfy these two properties:

• Associativity: for $f : W \rightarrow X$, $g : X \rightarrow Y$, $h : Y \rightarrow Z$, we have that $h \circ (g \circ f) \equiv (h \circ g) \circ f$.
• Identity: $\forall , K \in ob(C)$, $\exists ; 1_k \in hom(C)$ so that $f \circ 1_k \equiv f$ for each $f : K \rightarrow X$ and $1_k \circ g \equiv g$ for each $g : Y \rightarrow K$ where $X, Y \in ob(C)$.

A simple example of category is the following:

• $ob(C) \equiv \mathbb{Z}$.
• Each $f \in hom(C)$, $f : z_1 \rightarrow z_2$ corresponds to the $z_1 \leq z_2$ relation $\forall , z_1, z_2 \in \mathbb{Z}$.
• The composition function $\circ$ can be intuitively constructed given $hom(C)$: if we have two $f : z_1 \rightarrow z_2$ and $g : z_2 \rightarrow z_3$, we have that $g \circ f : z_1 \rightarrow z_3$ corresponds to the relation $z_1 \leq z_2 \leq z_3 \Rightarrow z_1 \leq z_3$.

It's easy to verify that both associativity and identity are satisfied, given how we construct the composition of $\leq$ operators.

In terms of C# code, we may define the previous category as follows:

using System.Collections.Generic;
using System.Linq.Expressions;
using static System.Linq.Expressions.Expression;

public interface ICategory<TObject, TMorphism>
{
    IEnumerable<TObject> Objects { get; }
    TMorphism Morphism(TObject obj1, TObject obj2);
    TMorphism Compose(TMorphism m1, TMorphism m2);
}

public class IntCategory : ICategory<int, BinaryExpression>
{
    public IEnumerable<int> Objects
    {
        get
        {
            for (int i = int.MinValue; i < int.MaxValue; i++)
            {
                yield return i;
            }
            
            // avoids overflows
            yield return int.MaxValue;
        }
    }
    
    public BinaryExpression Morphism(int x, int y)
        => LessThanOrEqual(Constant(x), Constant(y));

    public BinaryExpression Compose(BinaryExpression be1, BinaryExpression be2) 
        => LessThanOrEqual(be1.Left, be2.Right);
}

Another example of category can be derived from the types in a statically typed programming language like C#:

• $ob(C) \equiv $ ${ T , | , T \text{ is a type in C#}}$.
• Each $f \in hom(C)$ is a morphism $f : T_1 \rightarrow T_2$ is a pure function that converts a value of type $T_1$ into type $T_2$, like Object.ToString() or DateTime.Parse(). $hom(C)$ includes the identity function, which corresponds to the lambda expression x => x for every type.
• The composition function $\circ$ is the regular composition between functions.