Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 23 down vote accepted

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.