What is an exponential object?

One interpretation for a power of natural numbers, such as 10^6, is that it is counting a certain collection of functions: in this case, the number of functions from a six-element set to a ten-element set. (One way to think about it is that 10^6 is the number of six-digit combinations from 000000 to 999999, and each combination corresponds to a function from \{1,\ldots,6\} to \{0,\dots,9\}: the first digit is the image of 1, the second digit is the image of 2, etc.)

In general, the number m^n is the number of functions from an n-element set to a m-element set. This is somewhat analogous to standard interpretations of other arithmetical operations:

  • m\times n is the number of elements in the Cartesian product of an m-element set and an n-element set.
  • m + n is the number of elements in the disjoint union of an m-element set and an n-element set.

So \times and + are arithmetical shadows of the categorical operations “Cartesian product” and “disjoint union” on sets. Is exponentiation the shadow of a categorical operation sending a pair of sets S and T to the set of functions from S to T? The answer is yes: this set of functions is an example of an exponential object in the category of sets, and is written T^S. This is one way of interpreting similarly notated sets like \mathbb{R}^3: as the set of functions from a 3-element set (such as \{1,2,3\}) to \mathbb{R}. We could instead let S be any set, and consider \mathbb{R}^S as the set of functions S\to \mathbb{R}, i.e. the set of S-indexed families of elements of \mathbb{R}.

So what are the categorical properties of this exponential object? Well, \mathbb{R}^3 comes with three maps \mathbb{R}^3\to \mathbb{R}: projection onto each coordinate. In other words, there’s a map

\{1,2,3\}\times \mathbb{R}^3 \to \mathbb{R}

that takes a number i and a point p\in \mathbb{R}^3 and sends it to the ith coordinate of p. More generally, there’s a canonical evaluation map

\text{eval}: S\times T^S \to T

that sends an element s\in S and a function f:S\to T to the element f(s)\in T. In fact, T^S is universal among sets A equipped with a function S\times A\to T: given such a function, each element a\in A gives us a function S\to T obtained from S\times A\to T by holding the second input constant at a, so we get a function A\to T^S.

This universal property is the categorical definition of an exponential object: if \mathcal{C} is any category with finite products (“\times“), then for any two objects S,T in \mathcal{C}, their exponential object T^S is an object with the property that morphisms A\to T^S are in natural one-to-one correspondence with morphisms S\times A\to T.

Here are some examples of exponential objects:

  1. The ordered set \{0,1\}, regarded as a category with the \leq relation as its morphisms, is a very simple category with nonetheless interesting exponential objects.

    The product operation in this category, as in any total order, is the “min” operation denoted \wedge, so that 0\wedge 0 = 0, 0\wedge 1 = 0, and 1\wedge 1 = 1. (If we interpret 0 and 1 as the truth values False and True, then this categorical product is the “and” operation. “Max” is the categorical coproduct, denoted by \vee.)

    Then given two truth values a and b, the exponential b^a is the largest element such that a\wedge b^a \leq b. You can check that this works out to: b^a = 0 if a=1 and b=0, and b^a = 1 otherwise. In other words, the exponential object b^a is the implication a\Rightarrow b!

  2. More generally, if \mathcal{B} is any Boolean algebra, regarded as a category via its poset structure, the exponential object b^a for two elements a,b\in B is the implication \neg a \vee b.
  3. If G is a group, the category of G-sets has exponential objects: if X and Y are two G-sets, then the exponential object Y^X is the set of all functions X\to Y (whether or not they respect the G-action!) and the G-action on Y^X is given by conjugation: the action of g\in G on f:X\to Y is the function X\to Y: x\to g\cdot f(g^{-1}\cdot x).
  4. If \mathcal{C} and \mathcal{D} are categories, i.e. objects in the category of categories, then the exponential object \mathcal{D}^\mathcal{C} is the category whose objects are functors \mathcal{C}\to \mathcal{D} and whose morphisms are natural transformations between them.

Do exponential objects always exist?

No: in fact, it’s rather common for exponential objects not to exist. If a category has an exponential object T^S for every pair of objects S and T, then one way of interpreting the correspondence

“morphisms S\times A\to T correspond to morphisms A\to T^S

is as an adjunction between the functors S\times (-) and (-)^S; as such, the functor S\times (-) automatically must preserve all colimits. In the category of sets, this is just a souped-up version of the statement that cartesian products distribute over disjoint unions:

S\times(A\coprod B) \cong (S\times A) \coprod (S\times B),

In other categories, however, this can fail. For example, in the category of abelian groups, the categorical product and coproduct are both direct sums, and we definitely don’t have a general isomorphism

S\oplus (A\oplus B) \cong (S\oplus A) \oplus (S\oplus B).

But in some ways this is the only problem: often if a category has enough colimits and a functor (such as S\times (-)) preserves them, that functor automatically has a right adjoint (which we could call (-)^S). Such a category would not only have binary products \times and a terminal object 1, it would also have binary coproducts + and an initial object 0, and if S\times (-) preserves colimits we must have

S\times (A+B) = (S\times A) + (S\times B)
and S\times 0 = 0.

In such a category, it’s possible to prove (with the Yoneda lemma, for example) that for all objects A, B, and C:

  1. A^B\times A^C \cong A^{B+C} and A^0 \cong 1.
  2. (A^B)^C \cong A^{B\times C} and A^1 \cong A.
  3. A^C\times B^C \cong (A\times B)^C and 1^C \cong 1.

These are exactly the laws of exponentiation for natural numbers, promoted to categorical isomorphisms, which we deduced in the first place from the interpretation of m^n as the number of functions from an n-element set to an m-element set. But now we know they hold in a general category with finite products, finite coproducts, and exponential objects—for example, if P, Q, and R are abstract propositions in the Boolean algebra of propositional logic, where product is “and”, coproduct is “or”, and exponentiation is “implies”, they read:

  1. P implies R and Q implies R if and only if (P or Q) implies R. Also, a false statement implies anything.
  2. P implies (Q implies R) if and only if (P and Q) implies R. Also, a proposition holds if and only if it is implied by a true statement.
  3. (P implies Q) and (P implies R) if and only if P implies (Q and R). Also, everything implies a true statement.

Amazing, huh?

Advertisements

Has this post helped you, or left you with further questions? Let me know with a comment!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s