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

Improve this question
$\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$
    – Tom Leinster
    Commented Jan 20, 2014 at 16:23

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .