3
$\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?

Improve this question
$\endgroup$
3
  • $\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
    Commented May 7, 2014 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
    Commented May 7, 2014 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
    Commented May 7, 2014 at 21:54

1 Answer 1

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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