category-theory-foundations

Category theory foundations including categories, functors, natural transformations, limits, and adjunctions

Category Theory Foundations

Scope: Categories, functors, natural transformations, limits/colimits, adjunctions, Yoneda lemma Lines: ~450 Last Updated: 2025-10-25

When to Use This Skill

Activate this skill when:

• Understanding abstract mathematical structures uniformly
• Working with functors between categories (homology, fundamental group)
• Designing composable abstractions in functional programming
• Studying universal properties (products, coproducts, limits)
• Understanding monads, functors, natural transformations in Haskell/Scala
• Formalizing mathematical concepts categorically

Core Concepts

Categories

Definition: A category C consists of:

• Objects: ob(C)
• Morphisms: For objects A, B, a set hom(A, B) of morphisms f: A → B
• Composition: For f: A → B and g: B → C, composition g ∘ f: A → C
• Identity: For each object A, identity morphism id_A: A → A

Axioms:

• Associativity: h ∘ (g ∘ f) = (h ∘ g) ∘ f
• Identity: f ∘ id_A = f = id_B ∘ f

from abc import ABC, abstractmethod
from typing import TypeVar, Generic, Callable

A = TypeVar('A')
B = TypeVar('B')
C = TypeVar('C')

class Category(ABC):
    """Abstract base for category"""

    @abstractmethod
    def objects(self):
        """Return collection of objects"""
        pass

    @abstractmethod
    def morphisms(self, source, target):
        """Return morphisms from source to target"""
        pass

    @abstractmethod
    def compose(self, f, g):
        """Compose g ∘ f"""
        pass

    @abstractmethod
    def identity(self, obj):
        """Return identity morphism for object"""
        pass

# Example: Category of Sets
class Set_Category(Category):
    """Category Set: objects are sets, morphisms are functions"""

    def objects(self):
        # Conceptual: all sets (can't enumerate)
        return "All sets"

    def morphisms(self, source, target):
        # All functions from source to target
        return f"Functions: {source} → {target}"

    def compose(self, f, g):
        """g ∘ f"""
        return lambda x: g(f(x))

    def identity(self, obj):
        """id(x) = x"""
        return lambda x: x

# Example usage
Set = Set_Category()
f = lambda x: x + 1  # ℕ → ℕ
g = lambda x: x * 2  # ℕ → ℕ
h = Set.compose(f, g)  # h(x) = g(f(x)) = 2(x+1)
print(h(3))  # 8

Common categories:

def category_examples():
    """Common mathematical categories"""
    return {
        'Set': 'Sets and functions',
        'Grp': 'Groups and group homomorphisms',
        'Ring': 'Rings and ring homomorphisms',
        'Vect_k': 'Vector spaces over field k, linear maps',
        'Top': 'Topological spaces and continuous maps',
        'Poset': 'Partially ordered sets, monotone functions',
        'Cat': 'Small categories and functors',
        'Hask': 'Haskell types and functions (idealized)'
    }

Functors

Definition: Functor F: C → D maps:

• Objects: F(A) ∈ ob(D) for A ∈ ob(C)
• Morphisms: F(f: A → B) = F(f): F(A) → F(B)

Axioms:

• F(id_A) = id_{F(A)}
• F(g ∘ f) = F(g) ∘ F(f)

class Functor(ABC):
    """Abstract functor between categories"""

    def __init__(self, source_category, target_category):
        self.source = source_category
        self.target = target_category

    @abstractmethod
    def map_object(self, obj):
        """F(A)"""
        pass

    @abstractmethod
    def map_morphism(self, f):
        """F(f: A → B): F(A) → F(B)"""
        pass

# Example: List functor in programming
class ListFunctor(Functor):
    """F(A) = List[A] in Hask"""

    def map_object(self, type_a):
        """F(A) = List[A]"""
        return f"List[{type_a}]"

    def map_morphism(self, f):
        """
        F(f: A → B) = map(f): List[A] → List[B]
        """
        return lambda xs: [f(x) for x in xs]

# Usage
list_functor = ListFunctor(None, None)
f = lambda x: x * 2  # Int → Int
F_f = list_functor.map_morphism(f)  # List[Int] → List[Int]
print(F_f([1, 2, 3]))  # [2, 4, 6]

Contravariant functors: Reverse arrow direction

class ContravariantFunctor(Functor):
    """F: C^op → D (reverses arrows)"""

    @abstractmethod
    def map_morphism(self, f):
        """F(f: A → B): F(B) → F(A) (reversed!)"""
        pass

# Example: Hom functor hom(-, B): C^op → Set
def hom_functor(B):
    """hom(-, B) sends A ↦ hom(A, B)"""
    return lambda A: f"Functions from {A} to {B}"

Natural Transformations

Definition: Natural transformation η: F ⇒ G between functors F, G: C → D

• Components: η_A: F(A) → G(A) for each object A
• Naturality: For f: A → B, the square commutes:

`` F(A) --η_A--> G(A) | | F(f) G(f) | | v v F(B) --η_B--> G(B) `` i.e., G(f) ∘ η_A = η_B ∘ F(f)

class NaturalTransformation:
    """Natural transformation η: F ⇒ G"""

    def __init__(self, source_functor, target_functor):
        self.F = source_functor
        self.G = target_functor
        self.components = {}

    def component(self, obj):
        """η_A: F(A) → G(A)"""
        return self.components.get(obj)

    def set_component(self, obj, morphism):
        """Define component at object"""
        self.components[obj] = morphism

    def verify_naturality(self, f, source_obj, target_obj):
        """Check: G(f) ∘ η_A = η_B ∘ F(f)"""
        η_A = self.component(source_obj)
        η_B = self.component(target_obj)
        Ff = self.F.map_morphism(f)
        Gf = self.G.map_morphism(f)

        # Would need to check equality of composed morphisms
        return "Naturality condition (conceptual check)"

# Example: List to Maybe natural transformation
# length: List[A] → Maybe[Int]
def list_to_maybe_length():
    """η: List ⇒ Maybe where η_A(xs) = Just(len(xs)) if xs non-empty"""
    def component(type_a):
        def eta(xs):
            if xs:
                return ('Just', len(xs))
            else:
                return ('Nothing', None)
        return eta
    return component

Universal Properties and Limits

Product: A × B with projections π₁: A × B → A, π₂: A × B → B Universal property: For any Z with f: Z → A, g: Z → B, ∃! h: Z → A × B such that π₁ ∘ h = f and π₂ ∘ h = g

class Product:
    """Categorical product A × B"""

    def __init__(self, A, B):
        self.A = A
        self.B = B
        self.product = (A, B)  # Conceptual tuple

    def projection1(self):
        """π₁: A × B → A"""
        return lambda pair: pair[0]

    def projection2(self):
        """π₂: A × B → B"""
        return lambda pair: pair[1]

    def universal_morphism(self, f, g):
        """
        Given f: Z → A, g: Z → B
        Return h: Z → A × B (unique)
        """
        return lambda z: (f(z), g(z))

# Example in Set
A, B = "A", "B"
prod = Product(A, B)

# Universal property: pairing
f = lambda z: f"f({z})"  # Z → A
g = lambda z: f"g({z})"  # Z → B
h = prod.universal_morphism(f, g)  # Z → A × B

z0 = "z0"
print(h(z0))  # ('f(z0)', 'g(z0)')
print(prod.projection1()(h(z0)))  # 'f(z0)' = f(z0) ✓

Coproduct (sum): A + B with injections ι₁: A → A + B, ι₂: B → A + B Universal property: Dual to product

class Coproduct:
    """Categorical coproduct A + B (disjoint union)"""

    def __init__(self, A, B):
        self.A = A
        self.B = B

    def injection1(self):
        """ι₁: A → A + B"""
        return lambda a: ('Left', a)

    def injection2(self):
        """ι₂: B → A + B"""
        return lambda b: ('Right', b)

    def universal_morphism(self, f, g):
        """
        Given f: A → Z, g: B → Z
        Return h: A + B → Z (unique)
        """
        def h(coproduct_elem):
            tag, value = coproduct_elem
            if tag == 'Left':
                return f(value)
            else:  # 'Right'
                return g(value)
        return h

# Example: Either a b in Haskell
# Either a b = Left a | Right b (coproduct)

Adjunctions

Definition: Functor F: C → D is left adjoint to G: D → C (F ⊣ G) if: hom_D(F(A), B) ≅ hom_C(A, G(B)) naturally in A and B

Unit and counit:

• Unit: η: 1_C ⇒ G ∘ F
• Counit: ε: F ∘ G ⇒ 1_D

class Adjunction:
    """F ⊣ G: Adjunction between functors"""

    def __init__(self, left_adjoint, right_adjoint):
        self.F = left_adjoint  # F: C → D
        self.G = right_adjoint  # G: D → C

    def unit(self):
        """η: Id ⇒ G ∘ F"""
        # For each A in C, η_A: A → G(F(A))
        pass

    def counit(self):
        """ε: F ∘ G ⇒ Id"""
        # For each B in D, ε_B: F(G(B)) → B
        pass

# Example: Free-Forgetful adjunction
# Free: Set → Grp (free group functor)
# Forgetful: Grp → Set (forget group structure)
# Free ⊣ Forgetful

Monads

Definition: Monad on category C is a triple (M, η, μ) where:

• M: C → C is endofunctor
• η: 1_C ⇒ M (unit)
• μ: M ∘ M ⇒ M (multiplication)

Axioms:

• μ ∘ M(μ) = μ ∘ μ(M) (associativity)
• μ ∘ η(M) = μ ∘ M(η) = id_M (unit laws)

class Monad:
    """Monad (M, η, μ)"""

    def __init__(self, functor_m):
        self.M = functor_m

    def unit(self, x):
        """η: a → M(a) (return/pure)"""
        raise NotImplementedError

    def join(self, mmx):
        """μ: M(M(a)) → M(a) (flatten)"""
        raise NotImplementedError

    def bind(self, mx, f):
        """
        (>>=): M(a) → (a → M(b)) → M(b)
        bind(mx, f) = μ(M(f)(mx))
        """
        # Apply f to get M(M(b)), then join
        mmx = self.M.map_morphism(f)(mx)
        return self.join(mmx)

# Example: List monad
class ListMonad(Monad):
    """List monad in Python"""

    def unit(self, x):
        """η(x) = [x]"""
        return [x]

    def join(self, lists):
        """μ([[x]]) = [x] (flatten)"""
        result = []
        for lst in lists:
            result.extend(lst)
        return result

    def bind(self, xs, f):
        """xs >>= f = concat(map(f, xs))"""
        return self.join([f(x) for x in xs])

# Usage
list_monad = ListMonad(None)
xs = [1, 2, 3]
f = lambda x: [x, -x]  # a → [a]
result = list_monad.bind(xs, f)  # [1, -1, 2, -2, 3, -3]
print(result)

---

Patterns

Pattern 1: Yoneda Lemma

Statement: Natural transformations η: hom(A, -) ⇒ F correspond bijectively to elements of F(A)

• Given η, get x ∈ F(A) by x = η_A(id_A)
• Given x ∈ F(A), define η_B(f: A → B) = F(f)(x)

def yoneda_embedding():
    """
    Yoneda: C → Set^(C^op)
    A ↦ hom(-, A)
    Fully faithful embedding
    """
    def embed(obj):
        # Returns functor hom(-, obj)
        return lambda x: f"hom({x}, {obj})"

    return embed

Pattern 2: Functoriality of Homology

Homology as functor: H_n: Top → Grp

• Sends spaces to abelian groups
• Sends continuous maps to group homomorphisms
• H_n(g ∘ f) = H_n(g) ∘ H_n(f)

# Conceptual: H_n functor
class HomologyFunctor(Functor):
    def __init__(self, n):
        self.degree = n

    def map_object(self, space):
        """H_n(X) = n-th homology group"""
        return f"H_{self.degree}({space})"

    def map_morphism(self, f):
        """f: X → Y induces f_*: H_n(X) → H_n(Y)"""
        return f"induced_homomorphism({f})"

Pattern 3: Curry-Howard-Lambek Correspondence

Correspondence:

• Logic ↔ Type Theory ↔ Category Theory
• Proposition ↔ Type ↔ Object
• Proof ↔ Program ↔ Morphism
• Implication (A → B) ↔ Function type ↔ Exponential B^A

def curry_howard_lambek():
    """Three-way correspondence"""
    return {
        'Conjunction (A ∧ B)': 'Product type (A, B) | A × B',
        'Disjunction (A ∨ B)': 'Sum type Either A B | A + B',
        'Implication (A → B)': 'Function type A → B | B^A',
        'True': 'Unit type () | Terminal object 1',
        'False': 'Empty type Void | Initial object 0',
    }

---

Quick Reference

Category Theory Hierarchy

Objects and Morphisms (Category)
    ↓
Functors (between categories)
    ↓
Natural Transformations (between functors)
    ↓
Modifications (between natural transformations)

Universal Constructions

| Construction | Universal Property | Example | |--------------|-------------------|---------| | Product | ∀ f, g ∃! h | Cartesian product | | Coproduct | ∀ f, g ∃! h | Disjoint union | | Equalizer | Limit | Kernel | | Coequalizer | Colimit | Cokernel | | Pullback | Limit | Fiber product | | Pushout | Colimit | Gluing |

Adjunctions in Programming

| Left Adjoint | Right Adjoint | Example | |--------------|---------------|---------| | Free | Forgetful | Free monoid ⊣ Underlying set | | Curry | Uncurry | (A → B → C) ≅ (A × B → C) | | Σ (Sum) | → (Function) | Dependent sum ⊣ Function |

---

Anti-Patterns

❌ Ignoring universal properties: Defining product as just a tuple ✅ Product defined by universal property (unique mediating morphism)

❌ Confusing objects and morphisms: Category theory is about morphisms ✅ "Objects are completely determined by morphisms to/from them"

❌ Forgetting naturality: Just defining components of transformation ✅ Natural transformation requires commuting squares for all morphisms

❌ Treating functors as just "type constructors": Missing preservation of structure ✅ Functor preserves composition: F(g ∘ f) = F(g) ∘ F(f)

---

Related Skills

• curry-howard.md - Propositions as types, category-theoretic view
• topology-algebraic.md - Functorial nature of π₁, H_*
• abstract-algebra.md - Categories of groups, rings, modules
• type-systems.md - Categories in programming languages
• formal/lean-mathlib4.md - Category theory in Lean

---

Last Updated: 2025-10-25 Format Version: 1.0 (Atomic)