Category Theory
Adjoint Functors: The Universal Principle of Mathematics
Linux file system descriptors are objects in a category. fork() is a left adjoint to wait(). Currying in JavaScript - f(a, b) vs f(a)(b) - is a Hom-set isomorphism. Adjunctions are everywhere in OS design, type theory, and logic. Saunders Mac Lane: adjoint functors arise everywhere.
- Currying in JS/TS/Haskell: isomorphism (A×B→C) ≅ (A→B→C)
- Type inference in ML languages uses properties of adjoint functors
- SQL: GROUP BY + aggregate - adjunction with the diagonal functor
- Logic: quantifiers ∃ and ∀ - adjoint to variable substitution
Adjunction: the Hom-Set Isomorphism
Linux file system: descriptors are objects, syscalls are morphisms - a category. fork() is a left adjoint to wait() in the category of processes. Currying - writing f(a)(b) instead of f(a, b) - is a Hom-set isomorphism. A functor F: C → D is **left adjoint** to G: D → C (written F ⊣ G) if for all objects A ∈ C and B ∈ D there is a natural isomorphism: Hom_D(F(A), B) ≅ Hom_C(A, G(B)). Arrows from F(A) to B correspond bijectively to arrows from A to G(B).
**Mnemonic:** "F ⊣ G - an arrow out of an F-image = an arrow into a G-preimage". If F builds a free structure (free group, free module), then G forgets structure (forgetful functor). This is the most important example of an adjunction in algebra.
What does the isomorphism Hom_D(F(A), B) ≅ Hom_C(A, G(B)) mean in the adjunction F ⊣ G?
Unit and Counit of an Adjunction
An adjunction F ⊣ G is equivalent to a pair of natural transformations: the **unit** η: Id_C ⇒ G∘F and the **counit** ε: F∘G ⇒ Id_D, satisfying the triangular identities. These two transformations "close the loop" in both directions.
**Unit = "embedding", counit = "projection":** This intuition works for most adjunctions. For the free group: unit = embedding of the set into the generated group; counit = homomorphism from the free group into the group. The triangular identities say: "embed then immediately project" = identity.
What is the counit ε of the (product ⊣ exponential) adjunction?
Examples of Adjunctions: Free ⊣ Forgetful, Curry-Howard
Adjunctions permeate mathematics. **Free ⊣ Forgetful**: free group, free module, free algebra. **Product ⊣ Exponential**: currying in lambda calculus. **Limit ⊣ Diagonal**: universal constructions. Almost every important mathematical fact is often a consequence of an adjunction.
**Theorem:** Every monad arises from an adjunction (two canonical ways: via the Kleisli category or via the Eilenberg - Moore category). Adjunctions are more fundamental than monads: monads are the "shadow" of an adjunction in the original category.
Why is the free group F(S) on a set S the left adjoint to the forgetful functor G?
Key Ideas
- F ⊣ G: isomorphism Hom_D(FA,B) ≅ Hom_C(A,GB), natural in A and B
- Equivalent to: pair η: Id⇒GF and ε: FG⇒Id with triangular identities
- Every adjunction gives rise to a monad G∘F
- Free ⊣ Forgetful - the canonical example: a homomorphism = specifying generator images
- Curry-Howard: currying = adjunction = logical exportation
Related Topics
Adjunctions connect functors, limits, monads, and logic.
- Monads — Every adjunction F⊣G gives rise to a monad G∘F
- Limits and Colimits — lim is right, colim is left adjoint to Δ
- Topos Theory — A topos is defined via adjunctions (cartesian closed category)
Вопросы для размышления
- What adjunction underlies the logical negation operator (¬)? Hint: consider (¬) as a functor on the Boolean algebra.
- Show that the discrete topology and indiscrete topology are left and right adjoints to the forgetful functor Top→Set.
- Why is it said that "the right adjoint preserves limits"? Prove it for a concrete example.