Purely combinatorial proof that$ (e^x)' = e^x$

At the beginning of Week 300 of John Baez's blog, Baez gives a proof that the "number" of finite sets (more specifically, the cardinality of the groupoid of all finite sets, where an object in the groupoid counts as $1/n!$ if it has $n!$ symmetries) equals $e$.

He then says that this leads to a purely combinatorial proof that $e^x$ is its own derivative.

Can anyone explain the purely combinatorial proof?

Solution 1:

I am not quite sure how to translate this into groupoid cardinality language, but here is the standard proof. Suppose $A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}$ is an exponential generating function. Then we should interpret $a_n$ as being the number of ways to put a certain structure on a set of size $n$. For example, when $a_n = 1$ this is the structure of "being a set." When $a_n = n!$ this is the structure of "being a totally ordered set." And so forth. We will call this an $A$-structure.

Then $A'(x) = \sum_{n \ge 0} a_{n+1} \frac{x^n}{n!}$ can be interpreted as having coefficients $b_n = a_{n+1}$ which count the number of ways to add an element to a set of size $n$, then put an $A$-structure on the resulting set of size $n+1$. This is a purely combinatorial definition of differentiation.

With this definition, the proof is quite obvious: there is exactly one way for a set to be a set, and there is also exactly one way to add an element to a set and then make the result a set. So $\frac{d}{dx} e^x = e^x$.

This proof might seem contentless. Try to see how it generalizes to show that $\frac{d}{dx} e^{ax} = ae^{ax}$ for any positive integer $a$, and if you're up for a challenge see if you can generalize it all the way to this identity.

Vaguely the proof in groupoid cardinality language goes like this. For a finite set $X$ the groupoid of finite sets equipped with a function to $X$ has cardinality $e^{|X|}$. (The morphisms between two objects $A \to X, B \to X$ in this category are isomorphisms $A \simeq B$ such that the obvious triangle commutes.) One way to think about this groupoid is as the groupoid of "colored" sets, where $X$ is the set of colors and an isomorphism must respect color. Then it is easy to see that an isomorphism class of colored sets where there are $|X|$ colors is the same thing as a disjoint union of isomorphism classes of $|X|$ sets, one for each color. One gets a direct interpretation of the terms in the expansion $\left( \sum_{n \ge 0}^{\infty} \frac{1}{n!} \right)^{|X|}$ this way.

Differentiation replaces $|X|^n$ with $n|X|^{n-1}$, which means that we replace functions from an $n$-element set $S$ to $X$ with functions from $S - \{ s \}$ to $X$ where $s$ ranges over all elements of $S$. The resulting groupoid is still the groupoid of finite sets equipped with a function to $X$; in particular, it has the same cardinality. (Note that $X$ does not really have to be a finite set of a particular size for this argument to work; it can be a "formal" set in the same way that $x$ is a formal variable and the resulting groupoid cardinality is a generating function instead of a number. I think this is what the formal theory of "stuff types" is for, but I am not familiar with it.)