Cartesian closed categories and the Lawvere fixed point theorem

September 28, 2013 by Qiaochu Yuan

Previously we saw that Cantor’s theorem, the halting problem, and Russell’s paradox all employ the same diagonalization argument, which takes the following form. Let $X$ be a set and let

$\displaystyle f : X \times X \to 2$

be a function. Then we can write down a function $g : X \to 2$ such that $g(x) \neq f(x, x)$ . If we curry $f$ to obtain a function

$\displaystyle \text{curry}(f) : X \to 2^X$

it now follows that there cannot exist $x \in X$ such that $\text{curry}(f)(x) = g$ , since $\text{curry}(f)(x)(x) = f(x, x) \neq g(x)$ .

Currying is a fundamental notion. In mathematics, it is constantly implicitly used to talk about function spaces. In computer science, it is how some programming languages like Haskell describe functions which take multiple arguments: such a function is modeled as taking one argument and returning a function which takes further arguments. In type theory, it reproduces function types. In logic, it reproduces material implication.

Today we will discuss the appropriate categorical setting for understanding currying, namely that of cartesian closed categories. As an application of the formalism, we will prove the Lawvere fixed point theorem, which generalizes the argument behind Cantor’s theorem to cartesian closed categories.

Some examples of mathematical currying

Example. A group action on a set is often described using a function $G \times X \to X$ . Currying gives a function $G \to (X \Rightarrow X)$ ; in other words, it associates to every element $g \in G$ a function $X \to X$ . It seems more natural to define a group action in this way, but what works in $\text{Set}$ may work less well in other categories; for example, when defining actions of Lie groups on manifolds, we talk about smooth functions $G \times M \to M$ because it is unclear in this setting in what sense the space of smooth functions $M \to M$ is a smooth manifold (hence in what sense we should be asking for smooth functions from $G$ into this space).

Example. A vector space $V$ is equipped with a dual pairing $V \times V^{\ast} \to k$ . Currying gives a function $V \to (V^{\ast} \Rightarrow k)$ , and the corresponding functions are in fact linear, so we can associate to every $v \in V$ an element of the double dual space $(V^{\ast})^{\ast}$ . In other words, currying gives us the double dual map $V \mapsto (V^{\ast})^{\ast}$ . There is a similar map in the setting of Pontrjagin duality.

Example. A topological space $X$ is equipped with an evaluation map $X \times C(X) \to \mathbb{C}$ , where $C(X)$ here denotes the space of continuous complex-valued functions $X \to \mathbb{C}$ . Currying gives a function $X \to (C(X) \Rightarrow \mathbb{C})$ which associates to every $x \in X$ an evaluation map $C(X) \to \mathbb{C}$ . When $X$ is compact Hausdorff, every homomorphism $C(X) \to \mathbb{C}$ of complex algebras has this form.

Cartesian closed categories

A cartesian closed category $C$ is a category with finite products in which the product functor $- \times Y$ has a right adjoint, the exponential $Y \Rightarrow (-)$ . In other words, there is a natural identification

$\text{curry} : \text{Hom}(X \times Y, Z) \cong \text{Hom}(X, Y \Rightarrow Z)$ .

The notation $Y \Rightarrow Z$ is nonstandard; a more conventional notation is $Z^Y$ , but the notation $Y \Rightarrow Z$ (which is sometimes used for the more general notion of internal hom) emphasizes the fact that a Cartesian closed category is in particular a closed monoidal category, and in particular is enriched over itself.

Letting $X = 1$ be the terminal object, we get that there is a natural identification

$\displaystyle \text{Hom}(Y, Z) \cong \text{Hom}(1, Y \Rightarrow Z)$ .

In other words, the global points (morphisms from $1$ , also just called points) of $Y \Rightarrow Z$ are naturally identified with the set of morphisms from $Y$ to $Z$ .

More generally, the $X$ -points of $Y \Rightarrow Z$ , which by definition are naturally identified with $\text{Hom}(X \times Y, Z)$ , should be thought of as “ $X$ -parameterized families of morphisms from $Y$ to $Z$ .”

Uncurrying the identity map $\text{id} : (X \Rightarrow Y) \to (X \Rightarrow Y)$ , we obtain the evaluation map

$\displaystyle \text{eval} : (X \Rightarrow Y) \times X \to Y$

describing, internally, how to evaluate functions on arguments. In computer science, this function is also called apply.

Example. $\text{Set}$ is cartesian closed, and is the basic example. Here the internal hom $Y \Rightarrow Z$ is the set of functions from $Y$ to $Z$ and the global points of a set are its set of points in the ordinary sense. The same applies to $\text{FinSet}$ .

Example. The category $\text{Cat}$ of (small) categories is cartesian closed. Here the product is the usual product of catgories and the internal hom $Y \Rightarrow Z$ is the category of functors from $Y$ to $Z$ , with morphisms given by natural transformations. The global points of a category are its objects.

Subexample. In $\text{Cat}$ , the subcategory $\text{Gpd}$ of groupoids is cartesian closed, since the product of groupoids and the functor category between two groupoids both remain groupoids. If $G, H$ are two groups regarded as one-object categories, the functor category $G \Rightarrow H$ is the groupoid whose objects are the morphisms $G \to H$ and whose morphisms are given by pointwise conjugation by elements of $H$ . Note that the category of groups is not cartesian closed.

Subexample. In $\text{Cat}$ , the subcategory $\text{Pos}$ of posets is cartesian closed, since the product of posets and the functor category between two posets both remain posets. If $P, Q$ are two posets, then $P \Rightarrow Q$ is the poset of order-preserving functions $P \to Q$ with $f \le g$ iff $f(p) \le g(p)$ for all $p \in P$ .

Example. Let $G$ be a group. The category $G\text{-Set}$ is cartesian closed; it has a product inherited from $\text{Set}$ , and exponential objects $Y \Rightarrow Z$ are given by the set of all functions from $Y$ to $Z$ together with the $G$ -action

$\displaystyle (Y \Rightarrow Z) \ni f(-) \mapsto g(f(g^{-1}(-))) \in (Y \Rightarrow Z)$ .

The global points of a $G$ -set are its fixed points, and in particular the global points of $Y \Rightarrow Z$ are the set of $G$ -morphisms $Y \to Z$ .

Example. Any Boolean algebra, regarded as a poset and then regarded as a category, is cartesian closed. The product $p \times q$ of two propositions $p, q$ is their logical “and” $p \wedge q$ , and the exponential object $p \Rightarrow q$ is the material implication $\neg p \vee q$ . The currying adjunction

$\displaystyle \text{Hom}(p \times q, r) \cong \text{Hom}(p, q \Rightarrow r)$

simply says that $p \wedge q$ implies $r$ if and only if $p$ implies $q \Rightarrow r$ . The terminal object $1$ is the proposition “true,” and a proposition has a global point if and only if it is a tautology. The evaluation map is an internal description of modus ponens.

Non-example. It is an unfortunate fact about point-set topology that $\text{Top}$ is not cartesian closed (see, for example, this math.SE question). When it exists, the exponential $Y \Rightarrow Z$ is often given the compact-open topology. This problem is fixed by working instead with a convenient category of topological spaces, such as the category of compactly generated spaces.

Non-example. Suppose a cartesian closed category $C$ has a zero object $0 \cong 1$ . Since there is a unique morphism from $0 \cong 1$ to any other object, it follows that every exponential $Y \Rightarrow Z$ has a unique global point, hence that there is a unique morphism $Y \to Z$ from any object to any other object (necessarily the zero morphism). Conversely, if $C$ has a zero object and a nonzero morphism, then $C$ cannot be cartesian closed.

Proposition: In a cartesian closed category, products $X \times Y$ distribute over colimits in both variables, and exponentials $Y \Rightarrow Z$ send colimits in $Y$ to limits and preserves limits in $Z$ .

Corollary: If $C$ is a cartesian closed category with finite coproducts (a bicartesian closed category), then letting $+$ denote the coproduct, we have the following natural identifications:

$X \times (Y + Z) \cong X \times Y + X \times Z$ (so $C$ is a distributive category),
$Z^{X+Y} \cong Z^X \times Z^Y$
$(XY)^Z \cong X^Z \times Y^Z$ .

Proof. These all follow from the natural identifications

$\text{Hom}(X \times Y, Z) \cong \text{Hom}(X, Y \Rightarrow Z) \cong \text{Hom}(Y, X \Rightarrow Z)$ .

In more detail, $- \times Y$ is a left adjoint and hence preserves arbitrary colimits, $Y \Rightarrow -$ is a right adjoint and hence preserves arbitrary limits, and $- \Rightarrow Z : \text{Set}^{op} \to \text{Set}$ is a (contravariant) right adjoint (to itself!) and hence, as a contravariant functor on $\text{Set}$ , sends colimits to limits. $\Box$

Specialized to the cartesian closed category of finite sets, the above result explains from a categorical point of view the algebraic axioms satisfied by addition, multiplication, and exponentiation of non-negative integers.

Corollary: Let $C$ be a category. Then the category $\widehat{C} = (C^{op} \Rightarrow \text{Set})$ of presheaves on $C$ is cartesian closed.

This greatly generalizes the example of $G\text{-Set}$ ; we get, for example, a version of the category of graphs and the category of simplicial sets as special cases.

Proof. Products are easy to construct, since limits are computed pointwise. To construct exponentials, suppose that $F, G : C^{op} \to \text{Set}$ are two presheaves whose exponential $F \Rightarrow G$ exists. The universal property and the Yoneda lemma together imply that

$\displaystyle (F \Rightarrow G)(c) \cong \text{Hom}_{\widehat{C}}(\text{Hom}(-, c), F \Rightarrow G) \cong \text{Hom}_{\widehat{C}}(\text{Hom}(-, c) \times F, G)$

which uniquely defines a presheaf. It remains to check that this presheaf really satisfies the universal property, but this follows from the fact that every presheaf is a colimit of representable presheaves and from the fact that products distribute over colimits, which is true because it is true pointwise; that is, in $\text{Set}$ . $\Box$

The terminal object in $\widehat{C}$ is the presheaf sending every object to $1 \in \text{Set}$ and sending every morphism to the unique morphism $1 \to 1$ . If $C$ itself has a terminal object $1$ , then it represents the terminal presheaf, hence a global point of a presheaf $F$ is just an element of $F(1)$ , so we can explicitly verify that $(F \Rightarrow G)(1) \cong \text{Hom}_{\widehat{C}}(F, G)$ . In general, a global point of a presheaf $F$ is a choice of element $x_c \in F(c)$ for each $c \in C$ which is compatible with every morphism in $C$ in the sense that if $f : c \to d$ is any morphism, then $F(f)(x_d) = x_c$ ; in other words, it is an element of the limit $\lim F$ .

In particular, if $C = O(X)$ is the category of open subsets of a topological space $X$ (so that a presheaf on $C$ is a presheaf on $X$ in the usual sense), then a global point of a presheaf $F$ is a global section. Note that this is equivalently an element of $F(X)$ (since $X$ is the terminal object) or a choice of element $x_U \in F(U)$ for each open $U$ which is compatible with inclusions in the sense that if $U \subseteq V$ then $x_V$ restricts to $x_U$ .

The category $\text{Sh}(X)$ of sheaves on a topological space is also a cartesian closed category, and moreover is a topos.

Presheaves on a monoid

We showed earlier that $G\text{-Set}$ is cartesian closed for $G$ a group, but the explicit description we gave of the exponential requires talking about inverses in $G$ . On the other hand, the above theorem implies in particular that $M\text{-Set}$ is cartesian closed for $M$ a monoid which is not necessarily a group. What does the exponential look like in this case?

Let $C = BM$ be a category with one object with endomorphism monoid $M$ . Then $\widehat{C}$ is the category of right $M$ -sets, and the unique representable presheaf is $M$ as a right $M$ -module over itself. If $S, T$ are two $M$ -sets, then the above description of the exponential gives

$\displaystyle (S \Rightarrow T) \cong \text{Hom}_{\widehat{C}}(M \times S, T)$

with right $M$ -action induced from the left $M$ -action of $M$ on itself. If $M$ is a group, this is naturally isomorphic to $\text{Hom}_{\text{Set}}(S, T)$ , since a morphism $M \times S \to T$ of right $M$ -sets is freely and uniquely determined by what it does to $1 \times S$ (where $1 \in M$ is the identity). This can fail if $M$ is not a group, since the value of such a morphism on $(m, s) \in M \times S$ may not be determined by the value on an element of the form $(1, s')$ if $s$ is not of the form $s' m$ for any $m \in M$ , and also since the value of a morphism on $(m, s)$ may be constrained by the value on two elements of the form $(1, s'), (1, s'')$ if there exists an $m \in M$ such that $s = s' m = s'' m$ .

Example. Let $M = \{ 1, e \}$ be the free monoid on an idempotent, so that $e^2 = e$ . This is the smallest monoid which is not a group. The category of right $M$ -sets is the category of sets equipped with idempotent endomorphisms. The subcategory of such sets $(S, e)$ such that $e$ is constant (equivalently, such that $e$ has a unique fixed point) is equivalent to the category of pointed sets: a morphism between such $M$ -sets is precisely a map of sets which preserves the unique fixed point. Thus if $S, T$ are such $M$ -sets of cardinalities $s, t$ respectively, then $M \times S$ is again such a set of cardinality $2s$ , and so there are $t^{2s-1}$ morphisms $M \times S \to T$ . On the other hand, there are $t^s$ maps $S \to T$ of sets.

The Lawvere fixed point theorem

To motivate the Lawvere fixed point theorem, let’s write the diagonalization argument above in somewhat greater generality. If $f : X \times X \to Y$ is any function, then we can find a function $g : X \to Y$ such that $g(x) \neq f(x, x)$ iff $|Y| \ge 2$ . Now we curry $f$ to obtain a function $\text{curry}(f) : X \to Y^X$ . If there exists $x \in X$ such that $\text{curry}(f)(x) = g$ , then as before $\text{curry}(f)(x)(x) = f(x, x) \neq g(x)$ and $g$ cannot be in the image of $\text{curry}(f)$ , hence $\text{curry}(f)$ is not surjective.

The crucial step is the step where we write down the function $g$ such that $g(x) \neq f(x, x)$ . A systematic way to do this is to compose $f(x, x)$ with a function $Y \to Y$ with no fixed points. Lawvere realized that, by taking contrapositives, this means the basic argument behind Cantor’s theorem can be recast as the following fixed point theorem.

Theorem (Lawvere): Let $X, Y$ be objects in a category with finite products such that the exponential $Y^X$ exists (in particular, this is true for any pair of objects in a cartesian closed category). Let $f : X \times X \to Y$ and suppose that $\text{curry}(f) : X \to Y^X$ is surjective on points in the sense that the induced map $\text{Hom}(1, X) \to \text{Hom}(1, Y^X)$ is surjective. Then every morphism $h : Y \to Y$ has a fixed point in the sense that the induced map $\text{Hom}(1, Y) \to \text{Hom}(1, Y)$ has a fixed point; that is, $Y$ has the fixed point property.

Proof. Let $h : Y \to Y$ be any morphism and let

$\displaystyle g = h \circ f \circ \Delta_X : X \to Y$

where $\Delta_X : X \to X \times X$ is the diagonal map; see, for example, this blog post. ( $g$ specializes to the paradoxical subset constructed in the usual proof of Cantor’s theorem.) By hypothesis, there exists a point $x : 1 \to X$ such that $f \circ (x \times \text{id}_X) = g$ (where, if $p : A \to B, q : C \to D$ are two morphisms in a category with finite products, $p \times q$ denotes the product morphism $A \times C \to B \times D$ .) But then

$\displaystyle g \circ x = f \circ (x \times x) = f \circ \Delta_X \circ x$

whereas by definition $g \circ x = h \circ f \circ \Delta_X \circ x$ , from which it follows that $f \circ \Delta_X \circ x$ is a fixed point of $h$ . $\Box$

Taking the contrapositive

Taking the contrapositive, we conclude that if $Y$ is an object in a cartesian closed category such that there exists a function $h : Y \to Y$ with no fixed points, then no morphism $X \to Y^X$ can be surjective on points. When $Y = 2$ in $\text{Set}$ we immediately reproduce Cantor’s theorem, and morally we reproduce Russell’s paradox as well. The proof of the Lawvere fixed point theorem actually provides a particular morphism $Y \to X$ not in the image of any morphism $X \to Y^X$ ; this particular morphism generalizes CantorBot and also gives us the unsolvability of the halting problem.

One Response

on December 10, 2013 at 8:55 pm | Reply How to invent intuitionistic logic | Annoying Precision

[…] Propositional logic should have an “internal” notion of implication. In other words, should not only just be true or false but should itself be a proposition. This would allow us to state inference rules like modus ponens (). The corresponding universal property is that if and only if . This is precisely the universal property of exponential objects, which we encountered when talking about the Lawvere fixed point theorem. […]

Comments RSS

	CG on GILA V: The Polya enumeration…
	rajeshd007 on Gradient descent
	Robert on Gradient descent
	Qiaochu Yuan on Gradient descent
	Kram Einsnulldreizwe… on Gradient descent

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos