1
$\begingroup$

In Andreas Blass's famous paper `Seven Trees in One', the existence of a natural bijection between binary trees and 7-tuples of binary trees is related to the equation $T^7 = T$ being satisfied by a complex number which satisfies the equation $T = 1 + T^2$ (the categorification of which is satisfied by the set of binary trees).

In a similar vein, Leinster states that there are (for a non-standard definition of cardinality) $e$ finite sets up to isomorphism. Specifically, for each finite cardinality $k$, there is one way to specify a list of $k$ distinct elements, but this counts each set $k!$ times (one for each permutation), so there are $\dfrac{1}{k!}$ sets of size $k$ and $\dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + \cdots = e$ finite sets.

http://quomodocumque.wordpress.com/2008/11/26/tom-leinster-on-entropy-diversity-and-cardinality/

Now, this result can be generalised. Consider a set of $k$ elements, each of which is coloured with one of $m$ non-equivalent colours. Up to isomorphism, there are now $\dfrac{m^k}{k!}$ $m$-coloured sets of size $k$, so $e^m$ finite $m$-coloured sets up to isomorphism.

Let $S_m$ be the collection of finite sets (for concreteness, subsets of $\mathbb{N}$) whose elements are $m$-coloured. Note that $e^m e^n \equiv e^{m+n}$, which suggests the following categorification:

"There exists a natural bijection between $S_m \times S_n$ and $S_{m+n}$."

Are there any prior results in this area? In particular, is there a natural bijection? (Such a bijection should generalise to when $\mathbb{N}$ is replaced by any infinite set, and should be constructive.)

$\endgroup$
1
  • 1
    $\begingroup$ The statement that the cardinality of the category of finite sets is $e$ isn't due to me. I learned it from a paper of John Baez and James Dolan, "From finite sets to Feynman diagrams" (arxiv.org/abs/math/0004133). Joyal may have realized it too, when he was setting up the theory of species: see James's answer. $\endgroup$ Jan 20, 2014 at 16:23

1 Answer 1

6
$\begingroup$

If I take an $m$-coloured set and an $n$-coloured set, their disjoint union (using disjoint sets of colours) is an $(m+n)$-coloured set. Conversely, if I have an $(m+n)$-coloured set, it has a subset which uses the first $m$ colours, and another subset which uses the other $n$...

While this answer is (perhaps unexpectedly) short, it is worth mentioning that there is a fairly good theory of phenomena like this: Joyal's theory of "combinatorial species". There's a survey article online nowadays.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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