Cartesian closed category

In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming. For generalizations of this notion, see monoidal category.

Contents

1 Definition 2 Discussion 3 Examples 4 Applications 5 Equational theory

Definition

The category C is called cartesian closed iff it satisfies the following three properties:

• it has a terminal object
• any two objects X and Y of C have a product X×Y in C
• for every object Y in C, the functor −×Y from C to C has a right adjoint

The right adjoint of −×Y, applied to the object Z, is written as HOM(Y,Z), Y=>Z or Z^Y; we will use the exponential notation in the sequel. The adjointness condition means that the set of morphisms in C from X×Y to Z is naturally identified with the set of morphisms from X to Z^Y, for any three objects X, Y and Z in C.

Discussion

For people who don't have a feel for how adjoints work, another way of formulating the third condition is that for any two objects Y and Z of C, there is an exponent object Z^Y and arrow eval:Z^Y×Y→Z with the following property: for every object X of C and arrow f:X×Y→Z, there's a unique arrow λf:X→Z^Y such that f=eval o λf×Id_Y.

For what this means if the category is Set (where the arrows are functions), see Applications below.

Examples

Examples of cartesian closed categories include:

• The category Set of all sets, with functions as morphisms, is cartesian closed. The product X×Y is the cartesian product of X and Y, and Z^Y is the set of all functions from Y to Z. The adjointness is expressed by the following fact: the function f : X×Y → Z is naturally identified with the function g : X → Z^Y defined by g(x)(y) = f(x,y) for all x in X and y in Y.
• The category of finite sets, with functions as morphisms, is cartesian closed for the same reason.
• If G is a group, then the category of all G-sets is cartesian closed. If Y and Z are two G-sets, then Z^Y is again the set of all functions from Y to Z, with the following G action: (g.f)(y) = g.(f(g^-1y)) for every g in G, f in Z^Y and y in Y.
• The category of finite G-sets is also cartesian closed.
• If C is a small category, then the functor category Set^C consisting of all covariant functors from C into the category of sets, with natural transformations as morphisms, is cartesian closed. If F and G are two functors from C to Set, then the exponential F^G is the functor whose value on the object X of C is given by the set of all natural transformations from (X,−) × G to F.
  • The earlier example of G-sets can be seen as a special case of functor categories: every group can be considered as a one-object category, and G-sets are nothing but functors from this category to Set
  • The category of all directed graphs is cartesian closed; this is a functor category as explained under functor category.
• In algebraic topology, cartesian closed categories are particularly easy to work with, and it is regrettable that neither the category of topological spaces with continuous maps nor the category of smooth manifolds with smooth maps is cartesian closed. Substitute categories have therefore been considered: the category of compactly generated Hausdorff spaces is cartesian closed, as is the category of Frölicher spaces.
• The category Cat of all small categories (with functors as morphisms) is cartesian closed; the exponential C^D is given by the functor category consisting of all functors from D to C, with natural transformations as morphisms.
• If X is a topological space, then the open sets in X form the objects of a category O(X); there's a unique morphism from U to V if and only if U is a subset of V. This category is cartesian closed; the "product" of U and V is the intersection of U and V and the exponential U^V is the interior of U∪(X\V).

The following categories are not cartesian closed:

• The category of all vector spaces over some fixed field is not cartesian closed, neither is the category of all finite-dimensional vector spaces. While they have products (called direct sums), the product functors don't have right adjoints.
• The category of abelian groups is not cartesian closed, for the same reason.

Applications

In cartesian closed categories, a "function of two variables" (a morphism f:X×Y → Z) can always be represented as a "function of one variable" (the morphism λf:X → Z^Y). In computer science applications, this is known as currying; it has led to the realization that simply-typed lambda calculus can be interpreted in any cartesian closed category.

Certain cartesian closed categories, the topoi, have been proposed as a general setting for mathematics, instead of traditional set theory.

The renowned computer scientist John Backus has advocated a variable-free notation, or Function-level programming, which in retrospect bears some similarity to the internal language of cartesian closed categories. CAML is more consciously modelled on cartesian closed categories.

Equational theory

In every cartesian closed category (using exponential notation), (X^Y)^Z and (X^Z)^Y are isomorphic for all objects X, Y and Z. We write this as the "equation"

(x^y)^z = (x^z)^y

What other such equations are valid in all cartesian closed categories? It turns out that all of them follow logically from the following axioms:

• x×(y×z) = (x×y)×z
• x×y = y×x
• x×1 = x (here 1 denotes the terminal object of C)
• 1^x = 1
• x¹ = x
• (x×y)^z = x^z×y^z
• (x^y)^z = x^(y×z)

See also: Cartesian closed category, Abelian group, Adjoint functor, Algebraic topology, CAML, Category theory, Compactly generated space, Computer science, Continuous, Currying