Module 2 Discussion Topics

Strong answers will include an explicit description of objects, morphisms, and verification (or failure) of the category axioms.

Discussion 1: Finding Categories in CS

Below are five CS structures. For each one, determine whether it forms a category. If yes, explicitly state the objects, the morphisms, and verify associativity and identity. If no, identify which axiom fails and construct a specific counterexample.

1. Types and functions in a statically-typed programming language (e.g., Haskell or Java)
2. Programs and reductions: objects are programs, morphisms are reduction steps in a term rewriting system
3. Files and hard links in a Unix filesystem: objects are files, morphisms are hard links pointing from one file to another
4. Git commits and merges: objects are commit hashes, morphisms are merge operations
5. Propositions and proofs: objects are logical propositions, morphisms are proofs that one proposition implies another (Curry-Howard correspondence)

Discussion 2: The Database Interpretation

Consider a simple three-table relational database: Employee(id, name, department_id), Department(id, name, location_id), Location(id, city).

• Draw the schema category: objects are tables, morphisms are foreign keys. What are the morphisms? Are there composite morphisms?
• An instance of this schema is a functor into Set. What does the functor assign to each object? What does it assign to each morphism?
• A natural transformation between two instances corresponds to what database operation? (Hint: think about what changes between two versions of the same schema.)
• If the foreign key constraint department_id → Department.id is violated (a dangling reference), which category axiom is violated by the corresponding functor?

Discussion 3: What Is a Morphism in ML?

We often think of machine learning models as functions from inputs to outputs. In a categorical setting, functions are morphisms. But the appropriate choice of category for an ML system is not obvious.

• Suppose the objects are "model states" (parameter vectors) and the morphisms are "gradient steps." Does this form a category? What are the identity morphisms? Is composition well-defined?
• Suppose instead the objects are "probability distributions" and the morphisms are "stochastic kernels" (conditional distributions p(y|x)). Does this form a category? (This is the Kleisli category of the probability monad.)
• Which of these two categories is more useful for encoding the structural constraints of the problem domain? Why?
• Propose a category for a specific ML problem you know well. What would the objects be? What would the morphisms be? What structural property does your choice encode?

Discussion 4: Equality vs. Isomorphism

In programming, we often ask "are these two objects equal?" In category theory, the correct question is "are these two objects isomorphic?" The distinction matters.

• In Python, a == b tests value equality and a is b tests identity (same object in memory). Which corresponds to isomorphism in Set?
• Two database tables with the same schema but different orderings of rows — are they equal or isomorphic? What is the isomorphism?
• The Yoneda Lemma (Module 4) implies that two objects are isomorphic if and only if their hom-sets are naturally isomorphic. What does this mean for a database schema: if two tables have the same set of foreign keys going into and out of them, are they the same table?
• In machine learning, two models with different weight values but the same input-output function — are they equal or isomorphic? What is the categorical statement of this?