Module 2 Glossary: Categories: The Language of Structure
Formal definitions for all terms introduced in Module 2. These definitions are used without modification throughout the rest of the course.
- Category
- A category C consists of: (1) a collection of objects ob(C); (2) for each pair of objects A, B, a set hom(A, B) of morphisms from A to B; (3) for each triple A, B, C, a composition function ∘: hom(B,C) × hom(A,B) → hom(A,C); and (4) for each object A, an identity morphism id_A ∈ hom(A,A). These must satisfy associativity: h ∘ (g ∘ f) = (h ∘ g) ∘ f, and identity: f ∘ id_A = f and id_B ∘ f = f for all f: A → B.
- Object
- A node in a category. Objects have no internal structure visible to the category — they are completely characterized by the morphisms into and out of them (Yoneda Lemma, Module 4). In Set, objects are sets. In Graph, objects are graphs. In a database schema category, objects are tables.
- Morphism
- An arrow f: A → B in a category from source object A to target object B. Morphisms encode structure-preserving relationships. They must be composable (g ∘ f when the target of f equals the source of g) and every object must have an identity morphism. In Set, morphisms are functions. In Graph, morphisms are graph homomorphisms. In a poset, morphisms are inequalities a ≤ b.
- Composition
- The operation that combines two morphisms f: A → B and g: B → C into a single morphism g ∘ f: A → C. Composition must be associative: h ∘ (g ∘ f) = (h ∘ g) ∘ f. This models sequential application: first f, then g. In Set, composition is function composition. In a database, composition of foreign keys gives a derived relationship.
- Identity Morphism
- For every object A, a morphism id_A: A → A satisfying f ∘ id_A = f and id_B ∘ f = f for all f: A → B. The identity is the "do nothing" morphism. In Set, id_A is the identity function on the set A. The identity axiom ensures that doing nothing before or after any operation has no effect.
- Isomorphism
- A morphism f: A → B for which there exists an inverse morphism g: B → A satisfying g ∘ f = id_A and f ∘ g = id_B. If an isomorphism exists between A and B, they are said to be isomorphic: A ≅ B. In category theory, isomorphic objects are indistinguishable — they satisfy all the same universal properties. In Set, isomorphisms are bijections. The Yoneda Lemma implies that objects are determined up to isomorphism by their hom-sets.
- Small Category
- A category in which ob(C) and all hom-sets are actual sets (as opposed to proper classes). Free categories generated from graphs, finite posets, and database schemas are all small. The category Set is large (its objects form a proper class). For most practical purposes in this course, the categories we construct are small.
- Discrete Category
- A category in which the only morphisms are identity morphisms. A discrete category on a set S has the elements of S as objects and only id_s for each s ∈ S as morphisms. Discrete categories appear in the construction of limits and colimits (Modules 5–6): a diagram over a discrete index category is simply a collection of objects with no arrows between them.
- Thin Category (Poset)
- A category in which there is at most one morphism between any two objects. A thin category corresponds precisely to a preorder: the objects are elements, and there is a morphism a → b if and only if a ≤ b. The category axioms then reduce to reflexivity (identity) and transitivity (composition). Posets as categories are the entry point for understanding that all of order theory is a special case of category theory.
- Monoid as a Category
- A monoid (M, ·, e) can be viewed as a category with a single object ★, where the morphisms are the elements of M, composition is the monoid operation ·, and the identity morphism is the monoid identity e. This shows that monoids, groups, and rings are all special cases of categories. String concatenation, integer addition, and matrix multiplication are all morphisms in their respective one-object categories.
- Schema (as a Category)
- A relational database schema interpreted as a category: tables are objects, foreign key relationships are morphisms. A schema morphism (functor between schema categories) maps tables to tables and foreign keys to foreign keys. This interpretation is the foundation of the AlgebraicJulia / Catlab.jl approach to database programming and is the basis for the data migration functors of Module 7.
- Instance (as a Functor)
- A database instance assigns actual data to each table in a schema. Categorically, an instance is a functor I: Schema → Set that maps each table-object to the set of its rows, and each foreign-key morphism to the function that maps each row to its referenced row. Two instances on the same schema are natural transformations between their corresponding functors.
- Free Category
- The free category on a directed graph G has the vertices of G as objects and the finite directed paths in G (including paths of length zero, the identity morphisms) as morphisms, with composition given by path concatenation. Every category is a quotient of a free category — the category axioms impose the only constraints (associativity and identity). Free categories are important because they show that categories are "just graphs with composition."