New here? Read Start Here first. This is the map of content for this vault, built from An Invitation to Applied Category Theory (7 Sketches in Compositionality), Category Theory for Scientists (CTfS), The Dao of Functional Programming (DaoFP) and the Kittenlab.jl lectures, plus research papers on category theory for machine learning (see Papers). Every concept has its own note tagged with #definition, #theorem, #proof, #example, #exercise, #solution, #program or #annotation, a > Sources: line pointing into the books, and code tabs for Julia (Catlab v0.16), Lean 4 (Mathlib) and Haskell. Exercise statements live in Exercises/ and their solutions in Solutions/, one note per chapter with a heading per exercise; each exercise and solution are cross-linked.
Sets, relations and functions (CTfS Ch. 2)
Set, Finite Set, Subset, Power Set, Relation, Partition, Equivalence Relation, Partitions Correspond to Equivalence Relations, Quotient Set, Function, Injection, Surjection, Bijection, Cardinality, Pigeonhole Principle, Identity Function, Function Composition, Global Element, Fiber, Natural Numbers, Real Numbers, Booleans, Graph, Path in a Graph, Arithmetic of Sets, Multiset, Indexed Set, Olog, Simplicial Complex
Preorders and Galois connections (7S Ch. 1)
Preorder, Discrete Preorder, Codiscrete Preorder, Partial Order, Total Order, Dagger Preorder, Divisibility Order, Equivalent Elements of a Preorder, Hasse Diagram, Preorder of Partitions, Upper Set, Upper Sets Classified by Maps to Bool, Product Preorder, Opposite Preorder, Tree of Life, Monotone Map, Category of Preorders, Isomorphism of Preorders, Meet, Join, Preservation of Meets and Joins, Generative Effect, Galois Connection, Right Adjoints Preserve Meets, Adjoint Functor Theorem for Preorders, Pushforward and Pullback of Partitions, Direct Image, Preimage, and Dual Image, Closure Operator, Interior Operator, Reflexive Transitive Closure, Yoneda Lemma for Preorders
Monoidal preorders and enrichment (7S Ch. 2)
Symmetric Monoidal Preorder, Monoid, Bool (Monoidal Preorder), Cost, Opposite Monoidal Preorder, Wiring Diagram, Wiring Diagrams for Monoidal Preorders, Resource Theory, Discard and Copy Axioms, Monoidal Monotone Map, Enriched Category, Preorders are Bool-Categories, Metric Space, Lawvere Metric Space, Hausdorff Distance, Weighted Graph, Change of Base, Enriched Functor, Enriched Natural Transformation, Product of Enriched Categories, Opposite Enriched Category, Monoidal Closed Preorder, Quantale, Matrix Multiplication in a Quantale
Categories and functors (7S Ch. 3, CTfS Ch. 3–4, DaoFP Ch. 1–3, 8–9, Kittenlab)
Category, Free Category, Presentation of a Category, Preorder Reflection, Category of Sets, Category of Finite Sets, Opposite Category, Isomorphism, Section and Retraction, Monomorphism, Epimorphism, Epi-Mono Factorization, Group, Groupoid, Skeleton, Discrete Category, Codiscrete Category, Walking Arrow, Terminal Category, Subcategory, Product Category, Slice Category, Comma Category, Category of Elements, Functor, Category of Categories, Constant Functor, Diagonal Functor, Endofunctor, Bifunctor, Contravariant Functor, Hom Functor, Natural Transformation, Natural Isomorphism, Diagram, Functor Category, Equivalence of Categories, 2-Category, Universal Property, Representable Functor, Yoneda Lemma, Yoneda Embedding, Presheaf, Monoid Action, Group Action, Endomorphism Monoid, Presentation of a Monoid, Finite State Machine, Full and Faithful Functor, Simplex Category, Symmetric Graph
Databases and data migration (7S Ch. 3, CTfS §3.5, 4.4, 5.1, Kittenlab)
C-Set, Database Schema, Category of Graphs, Graph Homomorphism, Discrete Dynamical System, Data Migration Functor, Catlab, Categories and Schemas are Equivalent, Kleisli Instance
Adjunctions, limits and colimits (7S Ch. 3 & 6, CTfS §4.5, 5.1, DaoFP Ch. 9–10)
Adjunction, Unit and Counit of an Adjunction, Universal Arrow, Right Adjoints Preserve Limits, Adjoint Functor Theorem, Defunctionalization, Free-Forgetful Adjunction, Free Monoid, Terminal Object, Initial Object, Product, Coproduct, Cone, Cocone, Limit, Colimit, Finite Limits in Set, Finite Colimits in Set, Colimits and Connection, Pullback, Pasting Lemma for Pullbacks, Equalizer, Coequalizer, Pushout, Span, Cospan, Exponential Object, Currying, Cartesian Closed Category, Bicartesian Closed Category, Cone Category
Types and recursion (DaoFP Ch. 4–7, 11–13)
Sum Type, Cartesian Category, Symmetric Monoidal Category, Natural Numbers Object, List, Dependent Type, Base Change Functor, Dependent Sum, Dependent Product, Locally Cartesian Closed Category, Equality Type, Algebra of an Endofunctor, Initial Algebra, Coalgebra of an Endofunctor, Terminal Coalgebra
Monads and comonads (DaoFP Ch. 14–16, CTfS §5.3)
Monad, Kleisli Category, Side Effects as Functors, Maybe Monad, Writer Monad, Reader Monad, State Monad, List Monad, Continuation Monad, IO Monad, Do Notation, Continuation, Continuation Passing Style, Free Monad, Functorial Strength, Applicative Functor, String Diagram, Monads from Adjunctions, Monad Transformer, Eilenberg-Moore Category, Comonad, Store Comonad, Lens, Power Set Monad, Distribution Monad, Markov Chain
Profunctors, ends and optics (7S Ch. 4, DaoFP Ch. 17–18)
Co-design, Feasibility Relation, Profunctor, Category of Profunctors, Companion and Conjoint, Collage, Categorification, Coend, End, Ninja Yoneda Lemma, Day Convolution, Bicategory of Profunctors, Prearrow, Existential Lens, Tannakian Reconstruction, Tambara Module, Profunctor Optics
Monoidal categories, props and string diagrams (7S Ch. 4–6)
Monoidal Category, Monoid Object, Monoidal Functor, Monoidal Natural Transformation, Monoidal Closed Category, Compact Closed Category, Traced Monoidal Category, Corelation, Prop, Category of Relations, Dagger Category, Port Graph, Free Prop, Presentation of a Prop, Rig, Signal Flow Graph, Prop of Matrices, Functorial Semantics, Graphical Linear Algebra, Behavior of a Signal Flow Graph, Category of Finite Sets as a Prop, Frobenius Monoid, Hopf Algebra, Hypergraph Category, Decorated Cospan, Structured Cospan, Operad, Operad Algebra, Undirected Wiring Diagram, Open Graph, Petri Net
Kan extensions and enrichment (DaoFP Ch. 19–20)
Kan Extension, Codensity Monad, Weighted Limit
Toposes, sheaves and logic (7S Ch. 7, CTfS §5.2)
Topos, Subobject, Subobject Classifier, Predicate, Internal Logic of a Topos, Heyting Algebra, Topos of Graphs, Topological Space, Sierpinski Space, Sheaf, Sheaf of Sections, Quantification, Modality, Internal Language of a Topos, Interval Domain, Topos of Behavior Types, Temporal Logic
Category theory for machine learning (arXiv papers)
Bicategory, Lax Functor, Grothendieck Construction, Actegory, Double Category, Graded Monad, Para Construction, Optic, Parametric Lens, Cartesian Differential Category, Reverse Derivative Category, Gradient-Based Learning with Parametric Lenses, Backprop as Functor, Open Game, Copy-Discard Category, Markov Category, Giry Monad, Almost-Sure Equality, Conditionals and Disintegration, Bayesian Inversion, Conditional Independence, Partial Markov Category, Gaussian Relations, Open Model, Bayesian Lens, Variational Free Energy, Statistical Game
Category theory for compilers and databases (arXiv papers)
Syntax and identity: Polynomial Functor, Abstract Syntax with Binding, Bisimulation, Congruence · Semantics: Curry-Howard-Lambek Correspondence, Lawvere Theory, Category with Families, Algebraic Effects and Handlers, Freyd Category, Call-by-Push-Value, Linear-Non-Linear Adjunction · Equivalence and translation: Contextual Equivalence, Logical Relations, Institution, Compiler Correctness · Rewriting: E-Graph, Double-Pushout Rewriting · Databases and queries: Attributed C-Set, Algebraic Database, Conjunctive Query, Cartesian Bicategory, Least Fixed Point, Provenance Semiring, Change Action, Relational Lens, Monad Comprehension
Papers: Papers — one note per arXiv paper, grouped by topic.
Exercises from 7 Sketches
Chapter 1 (exercises, solutions): 1.1 (sol), 1.4 (sol), 1.6 (sol), 1.7 (sol), 1.10 (sol), 1.11 (sol), 1.16 (sol), 1.17 (sol), 1.20 (sol), 1.24 (sol), 1.25 (sol), 1.27 (sol), 1.38 (sol), 1.40 (sol), 1.41 (sol), 1.42 (sol), 1.44 (sol), 1.46 (sol), 1.48 (sol), 1.51 (sol), 1.53 (sol), 1.55 (sol), 1.57 (sol), 1.63 (sol), 1.65 (sol), 1.66 (sol), 1.67 (sol), 1.69 (sol), 1.71 (sol), 1.73 (sol), 1.77 (sol), 1.79 (sol), 1.80 (sol), 1.85 (sol), 1.90 (sol), 1.94 (sol), 1.98 (sol), 1.99 (sol), 1.101 (sol), 1.103 (sol), 1.105 (sol), 1.106 (sol), 1.109 (sol), 1.110 (sol), 1.112 (sol), 1.114 (sol), 1.118 (sol), 1.119 (sol), 1.124 (sol), 1.125 (sol)
Chapter 2 (exercises, solutions): 2.5 (sol), 2.8 (sol), 2.20 (sol), 2.21 (sol), 2.29 (sol), 2.31 (sol), 2.33 (sol), 2.34 (sol), 2.35 (sol), 2.36 (sol), 2.39 (sol), 2.40 (sol), 2.43 (sol), 2.44 (sol), 2.45 (sol), 2.50 (sol), 2.52 (sol), 2.55 (sol), 2.58 (sol), 2.60 (sol), 2.61 (sol), 2.62 (sol), 2.63 (sol), 2.67 (sol), 2.68 (sol), 2.73 (sol), 2.75 (sol), 2.78 (sol), 2.82 (sol), 2.84 (sol), 2.92 (sol), 2.93 (sol), 2.94 (sol), 2.103 (sol), 2.104 (sol), 2.105 (sol)
Chapter 3 (exercises, solutions): 3.3 (sol), 3.9 (sol), 3.10 (sol), 3.12 (sol), 3.15 (sol), 3.16 (sol), 3.17 (sol), 3.19 (sol), 3.21 (sol), 3.22 (sol), 3.25 (sol), 3.30 (sol), 3.31 (sol), 3.32 (sol), 3.33 (sol), 3.37 (sol), 3.39 (sol), 3.40 (sol), 3.43 (sol), 3.45 (sol), 3.48 (sol), 3.55 (sol), 3.58 (sol), 3.62 (sol), 3.64 (sol), 3.67 (sol), 3.73 (sol), 3.76 (sol), 3.78 (sol), 3.81 (sol), 3.82 (sol), 3.83 (sol), 3.88 (sol), 3.90 (sol), 3.91 (sol), 3.97 (sol), 3.98 (sol), 3.101 (sol)
Chapter 4 (exercises, solutions): 4.4 (sol), 4.7 (sol), 4.9 (sol), 4.10 (sol), 4.12 (sol), 4.15 (sol), 4.17 (sol), 4.18 (sol), 4.22 (sol), 4.26 (sol), 4.30 (sol), 4.32 (sol), 4.36 (sol), 4.38 (sol), 4.41 (sol), 4.44 (sol), 4.48 (sol), 4.50 (sol), 4.52 (sol), 4.54 (sol), 4.62 (sol), 4.64 (sol), 4.65 (sol), 4.66 (sol)
Chapter 5 (exercises, solutions): 5.5 (sol), 5.9 (sol), 5.10 (sol), 5.16 (sol), 5.18 (sol), 5.20 (sol), 5.21 (sol), 5.23 (sol), 5.24 (sol), 5.28 (sol), 5.32 (sol), 5.35 (sol), 5.41 (sol), 5.43 (sol), 5.51 (sol), 5.55 (sol), 5.58 (sol), 5.59 (sol), 5.62 (sol), 5.63 (sol), 5.67 (sol), 5.69 (sol), 5.77 (sol), 5.80 (sol), 5.82 (sol), 5.83 (sol), 5.84 (sol), 5.85 (sol)
Chapter 6 (exercises, solutions): 6.3 (sol), 6.6 (sol), 6.7 (sol), 6.8 (sol), 6.10 (sol), 6.13 (sol), 6.16 (sol), 6.17 (sol), 6.18 (sol), 6.24 (sol), 6.26 (sol), 6.28 (sol), 6.35 (sol), 6.41 (sol), 6.48 (sol), 6.49 (sol), 6.57 (sol), 6.59 (sol), 6.62 (sol), 6.63 (sol), 6.67 (sol), 6.70 (sol), 6.78 (sol), 6.79 (sol), 6.80 (sol), 6.82 (sol), 6.84 (sol), 6.86 (sol), 6.88 (sol), 6.96 (sol)
Chapter 7 (exercises, solutions): 7.4 (sol), 7.6 (sol), 7.7 (sol), 7.8 (sol), 7.9 (sol), 7.11 (sol), 7.16 (sol), 7.17 (sol), 7.19 (sol), 7.20 (sol), 7.21 (sol), 7.27 (sol), 7.29 (sol), 7.31 (sol), 7.32 (sol), 7.34 (sol), 7.38 (sol), 7.40 (sol), 7.42 (sol), 7.44 (sol), 7.47 (sol), 7.49 (sol), 7.52 (sol), 7.53 (sol), 7.55 (sol), 7.59 (sol), 7.60 (sol), 7.62 (sol), 7.64 (sol), 7.66 (sol), 7.67 (sol), 7.68 (sol), 7.70 (sol), 7.72 (sol), 7.76 (sol), 7.77 (sol), 7.80 (sol)
Exercises from Category Theory for Scientists
CTfS prints no solutions; the solutions below are written for this wiki. Only the exercises referenced from concept notes are included.
Chapter 2 (exercises, solutions): 2.1.2.2 (sol), 2.1.2.5 (sol), 2.1.2.10 (sol), 2.1.2.13 (sol), 2.4.1.15 (sol), 2.4.2.13 (sol), 2.5.1.3 (sol), 2.5.1.5 (sol), 2.5.1.6 (sol), 2.5.1.10 (sol), 2.5.3.3 (sol), 2.6.1.3 (sol), 2.6.1.5 (sol), 2.6.1.10 (sol), 2.6.2.6 (sol), 2.6.2.7 (sol), 2.6.3.2 (sol), 2.7.1.2 (sol), 2.7.2.2 (sol), 2.7.2.5 (sol), 2.7.2.6 (sol), 2.7.3.2 (sol), 2.7.3.3 (sol), 2.7.4.7 (sol), 2.7.4.12 (sol), 2.7.5.6 (sol), 2.7.6.4 (sol), 2.7.6.5 (sol), 2.7.6.8 (sol), 2.7.6.9 (sol), 2.7.6.14 (sol)
Chapter 3 (exercises, solutions): 3.1.1.7 (sol), 3.1.1.13 (sol), 3.1.1.18 (sol), 3.1.1.23 (sol), 3.1.2.4 (sol), 3.1.2.13 (sol), 3.1.4.7 (sol), 3.1.4.15 (sol), 3.2.1.8 (sol), 3.2.1.14 (sol), 3.2.1.15 (sol), 3.3.2.4 (sol), 3.3.3.5 (sol), 3.3.3.6 (sol), 3.3.3.9 (sol), 3.4.1.8 (sol), 3.4.1.12 (sol), 3.4.1.14 (sol), 3.4.4.3 (sol), 3.4.4.7 (sol), 3.4.4.11 (sol), 3.5.2.12 (sol), 3.5.2.13 (sol), 3.5.2.18 (sol), 3.5.3.2 (sol), 3.5.3.5 (sol)
Chapter 4 (exercises, solutions): 4.1.1.8 (sol), 4.1.2.29 (sol), 4.2.1.10 (sol), 4.2.1.11 (sol), 4.2.1.13 (sol), 4.2.1.22 (sol), 4.2.1.23 (sol), 4.2.2.3 (sol), 4.2.3.12 (sol), 4.2.4.4 (sol), 4.3.1.10 (sol), 4.3.1.11 (sol), 4.3.2.13 (sol), 4.3.3.3 (sol), 4.3.3.6 (sol), 4.3.4.5 (sol), 4.3.4.13 (sol), 4.3.4.14 (sol), 4.3.4.16 (sol), 4.4.1.5 (sol), 4.4.1.6 (sol), 4.4.1.7 (sol), 4.5.1.4 (sol), 4.5.1.15 (sol), 4.5.2.5 (sol), 4.5.2.9 (sol), 4.5.2.10 (sol), 4.5.3.12 (sol), 4.5.3.13 (sol), 4.5.3.19 (sol), 4.6.2.5 (sol), 4.6.4.3 (sol)
Chapter 5 (exercises, solutions): 5.1.1.3 (sol), 5.1.1.6 (sol), 5.1.1.9 (sol), 5.1.4.5 (sol), 5.1.4.8 (sol), 5.1.4.11 (sol), 5.2.3.3 (sol), 5.3.2.5 (sol), 5.3.3.5 (sol), 5.3.3.6 (sol), 5.3.3.7 (sol), 5.4.1.4 (sol)
Exercises from the Dao of Functional Programming
Chapter 2 (exercises, solutions): 2.1.1 (sol), 2.1.2 (sol), 2.1.3 (sol), 2.3.1 (sol), 2.4.1 (sol), 2.5.1 (sol)
Chapter 3 (exercises, solutions): 3.1.1 (sol), 3.1.2 (sol), 3.1.3 (sol), 3.1.4 (sol), 3.2.1 (sol), 3.3.1 (sol), 3.3.2 (sol)
Chapter 4 (exercises, solutions): 4.1.1 (sol), 4.4.1 (sol), 4.4.2 (sol), 4.4.3 (sol), 4.4.4 (sol), 4.4.5 (sol)
Chapter 5 (exercises, solutions): 5.1.1 (sol), 5.1.2 (sol), 5.1.3 (sol), 5.1.4 (sol)
Chapter 6 (exercises, solutions): 6.3.1 (sol)
Chapter 7 (exercises, solutions): 7.1.1 (sol), 7.1.2 (sol), 7.2.1 (sol), 7.2.2 (sol), 7.2.3 (sol)
Chapter 8 (exercises, solutions): 8.2.1 (sol), 8.2.2 (sol), 8.3.1 (sol), 8.3.2 (sol), 8.3.3 (sol), 8.3.4 (sol), 8.5.1 (sol)
Chapter 9 (exercises, solutions): 9.3.1 (sol), 9.3.2 (sol), 9.3.3 (sol), 9.5.1 (sol), 9.5.2 (sol), 9.6.1 (sol), 9.6.2 (sol), 9.6.3 (sol), 9.8.1 (sol), 9.8.2 (sol), 9.8.3 (sol), 9.8.4 (sol), 9.8.5 (sol)
Chapter 10 (exercises, solutions): 10.3.1 (sol), 10.3.2 (sol), 10.3.3 (sol), 10.5.1 (sol), 10.5.2 (sol), 10.5.3 (sol), 10.5.4 (sol), 10.9.1 (sol), 10.9.2 (sol)
Chapter 11 (exercises, solutions): 11.1.1 (sol), 11.2.1 (sol), 11.2.2 (sol), 11.2.3 (sol), 11.2.4 (sol), 11.4.1 (sol), 11.4.2 (sol)
Chapter 12 (exercises, solutions): 12.2.1 (sol), 12.2.2 (sol), 12.5.1 (sol)
Chapter 13 (exercises, solutions): 13.2.1 (sol), 13.2.2 (sol), 13.2.3 (sol)
Chapter 14 (exercises, solutions): 14.4.1 (sol), 14.5.1 (sol), 14.5.2 (sol), 14.8.1 (sol), 14.8.2 (sol), 14.8.3 (sol), 14.9.1 (sol), 14.9.2 (sol), 14.9.3 (sol)
Chapter 15 (exercises, solutions): 15.1.1 (sol), 15.2.1 (sol), 15.3.1 (sol)
Chapter 16 (exercises, solutions): 16.0.1 (sol), 16.1.1 (sol), 16.1.2 (sol), 16.1.3 (sol), 16.3.1 (sol)
Chapter 17 (exercises, solutions): 17.1.1 (sol), 17.1.2 (sol), 17.2.1 (sol), 17.2.2 (sol), 17.2.3 (sol), 17.3.1 (sol), 17.6.1 (sol), 17.7.1 (sol), 17.7.2 (sol), 17.7.3 (sol), 17.9.1 (sol)
Chapter 18 (exercises, solutions): 18.1.1 (sol), 18.2.1 (sol), 18.4.1 (sol)
Chapter 19 (exercises, solutions): 19.1.1 (sol), 19.1.2 (sol), 19.3.1 (sol), 19.3.2 (sol), 19.3.3 (sol), 19.3.4 (sol), 19.4.1 (sol), 19.4.2 (sol)
Chapter 20 (exercises, solutions): 20.1.1 (sol), 20.1.2 (sol), 20.2.1 (sol), 20.2.2 (sol), 20.6.1 (sol), 20.6.2 (sol), 20.7.1 (sol)