Module 2: Categories: The Language of Structure
This module introduces the core objects of category theory: categories, objects, and morphisms. The goal is fluency before formality. You will discover that structures you already work with daily — directed graphs, relational databases, partial orders, typed programming languages — are categories in disguise. By the end of this module you will be comfortable with the basic vocabulary and able to recognize categorical structure throughout computer science.
Learning Objectives
- Define a category precisely via objects, morphisms, composition, and identity axioms.
- Verify the associativity and identity laws for a given candidate category.
- Identify Set, Graph, Poset, and Vect as concrete categories with explicit morphisms.
- Model a relational database schema as a category and a database instance as a functor into Set.
- Distinguish between small categories, large categories, and the category Cat.
- Explain why structures familiar from CS — graphs, type systems, databases — are categories.
Materials
Key Concepts
- Category: A collection of objects and morphisms satisfying two laws — composition (morphisms chain associatively) and identity (every object has a do-nothing morphism).
- Object: A node in a category; analogous to a type, a table, or a set depending on context.
- Morphism: An arrow from one object to another satisfying the category laws; analogous to a function, a relation, or a foreign key.
- Composition: Given f: A → B and g: B → C, their composite g ∘ f: A → C exists and is unique; composition is associative.
- Identity Morphism: For every object A, a morphism id_A: A → A such that f ∘ id_A = f and id_B ∘ f = f for all f: A → B.
- Schema: A relational database schema interpreted as a category whose objects are tables and whose morphisms are foreign key relationships.
- Instance: A functor from a schema category into Set; assigns an actual set of rows to each table and a function to each foreign key.
Central Concepts from Prerequisites
- Discrete mathematics: directed graphs, paths, adjacency
- Databases: tables, primary keys, foreign keys, referential integrity
- Abstract algebra: monoids (a category with one object)
- Functional programming: types as objects, functions as morphisms (helpful)