Questions: Cartesian Closed Categories

Question 1

The adjunction Hom(A × B, C) ≅ Hom(A, C^B) in a cartesian closed category captures which familiar programming concept?

• A. Pattern matching — decomposing a product type into its components
• B. Currying — converting a function of two arguments into a function that takes one argument and returns a function
• C. Polymorphism — a single function operating on multiple types
• D. Memoization — caching function results to avoid recomputation

Answer: (B)

The adjunction says: a morphism from A × B to C (a function taking a pair as input) corresponds naturally and bijectively to a morphism from A to C^B (a function that takes one argument and returns a function from B to C). This is exactly currying. In Haskell, curry :: ((a,b) -> c) -> a -> b -> c; uncurry :: (a -> b -> c) -> (a,b) -> c. The CCC adjunction is the categorical version: the isomorphism is natural (respects composition), invertible (uncurrying exists), and universal (works for all A, B, C). The evaluation morphism ev: C^B × B → C is the categorical analog of function application.

Question 2

The category Grp of groups and group homomorphisms is not cartesian closed. What is the core reason?

• A. Groups do not have a terminal object, which is required for cartesian closure
• B. The binary product of two groups does not exist in Grp
• C. The set of group homomorphisms from A to B cannot be given a natural group structure, so no exponential object exists
• D. Grp is a closed category but not a cartesian one because the tensor product is not the categorical product

Answer: (C)

Grp does have a terminal object (the trivial group) and binary products (direct products A × B). What it lacks is exponential objects. The exponential B^A should represent 'the object of all morphisms from A to B' — in Set this is the function set with composition. In Grp, the set of group homomorphisms Hom(A, B) does not carry a natural group structure: the pointwise product of two homomorphisms (f·g)(x) = f(x)·g(x) is only a homomorphism when B is abelian. For non-abelian B, Hom(A, B) cannot be made into a group naturally, so the exponential fails to exist. This shows that cartesian closure is a strong condition that fails even in well-behaved algebraic categories.

Question 3

Every cartesian closed category must have all finite products, including a terminal object.

• T. True
• F. False

Answer: True

By definition, a CCC requires: (1) a terminal object 1 (the empty product), (2) all binary products A × B (and hence all finite products by iteration), and (3) exponential objects B^A for every pair A, B satisfying the adjunction Hom(C × A, B) ≅ Hom(C, B^A). The terminal object and binary products give the 'cartesian' part; the exponentials give the 'closed' part. The terminal object plays the role of the unit for the monoidal structure, and the product is the tensor. You cannot have cartesian closed structure without the cartesian structure (products) as its foundation.

Question 4

A category that has most finite products automatically also has most exponential objects, making it cartesian closed.

• T. True
• F. False

Answer: False

Having finite products is necessary but not sufficient for cartesian closure. The exponential B^A must exist as a specific object satisfying the adjunction Hom(C × A, B) ≅ Hom(C, B^A) naturally in all three variables. Many categories have products but fail to be cartesian closed because the required exponential objects do not exist. Examples: Grp has products but no exponentials (for non-abelian groups). Top (all topological spaces) has products but is not cartesian closed with the pointwise topology on function spaces — you need to restrict to compactly generated spaces. Checking cartesian closure requires explicitly verifying the representability of Hom(− × A, B) as a functor.

Question 5

What is the Curry-Howard-Lambek correspondence, and what three structures does it connect?

Model answer: The Curry-Howard-Lambek correspondence is a three-way equivalence between: (1) types and terms of simply-typed lambda calculus, (2) propositions and proofs in intuitionistic propositional logic, and (3) objects and morphisms in cartesian closed categories. Under this correspondence, function types (A → B) correspond to exponential objects (B^A) and to logical implication (A ⊃ B); lambda abstraction corresponds to currying (the CCC adjunction); function application corresponds to the evaluation morphism; and products correspond to logical conjunction and the type-theoretic product.

The significance is that three apparently different disciplines — programming language theory, proof theory, and abstract algebra — are secretly the same subject, expressed in different notation. A program that type-checks is simultaneously a valid proof and a well-defined morphism in a CCC. This means insights transfer freely: type-theoretic constructions like dependent types correspond to more expressive categories (locally cartesian closed categories, toposes), and categorical constructions suggest new programming language features. The correspondence is the foundation of proof assistants like Coq and Agda, where writing a program and proving a theorem are literally the same activity.