2
$\begingroup$

The definition of a (combinatorial) species $F$ emphasizes that any bijection $\phi\, :\, A \to B$ between support sets $A$ and $B$ must induce a bijection between $F[A]$ and $F[B]$ (the $F$-structures on $A$ and $B$ respectively), referred to as "transport of $F$-structures along $\phi$" in the standard textbooks by Bergeron, Labelle, and Leroux. For all the usual examples of species, the induced bijection between $F[A]$ and $F[B]$ is the "obvious" one. I trace this to the fact that for all these species, every structure on a support set $A$ is (or can be viewed as) a set in which each element is either (1) an element of $A$ or (2) a set in which each element is either (1) an element of $A$ or (2) a set in which each element is either ... (continued to a finite level of recursion).

If the notion of a species was restricted to structures formed in this way, the emphasis on induced bijections would be unnecessary---an induced bijection could always be found by letting $\phi$ "pass thru" the enclosing braces of all the sets.

The question is: would there be any significant loss of generality (as opposed to a loss of conceptual simplicity) in doing so?

More specifically, is there an example of a species whose structures cannot be expressed as sets of the above type?

$\endgroup$
  • $\begingroup$ I don't understand the claim that it's not necessary to think about the induced bijection in cases where it's in some sense easy to define. $\endgroup$ – Qiaochu Yuan May 7 '14 at 2:03
  • $\begingroup$ Is your proposed restriction supposed to include examples like Qiaochu's $[n]^k$ or ${[n] \choose k}$, which don't really have elements that can be identified with elements of $[n]$ at all? $\endgroup$ – Tim Campion May 7 '14 at 15:24
  • $\begingroup$ Not sure I follow. I understand $[n]^{k}$ to be the k-fold product of the species of singletons. In this species, a structure on $A=[n]$ is a length-$k$ list of not-necessarily-distinct elements of $[n]$ (or, to be precise, a list of singletons). Certainly, a list can be represented as a set of sets, and so this species falls in the restricted class I propose. $\endgroup$ – David Callan May 7 '14 at 21:54
3
$\begingroup$

The category of combinatorial species is equivalent to the category of sequences $F_n$ of $S_n$-sets, where $S_n$ is the symmetric group on $n$ letters. Of course $[n] = \{ 1, 2, 3, ... n \}$ is itself such an $S_n$-set, as are various sets one can build from $[n]$ such as $[n]^k$ or ${[n] \choose k}$ (the set of $k$-element subsets). But in general one can just build $S_n$-sets by picking subgroups $H_{n,i}$ and considering $\bigsqcup_i S_n/H_{n,i}$ (and of course every $S_n$-set arises in this way). As $n$ varies these subgroups $H_{n,i}$ need not have anything to do with each other.

In particular, constructions like $[n] \mapsto [n]^k$ and ${[n] \choose k}$ are functorial with respect to arbitrary maps, not just bijections, but we don't need to restrict ourselves to such things.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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