# Induced bijections of combinatorial species

I'm doing this exercise:

Prove that $\mathcal{S}[\beta]$ is a bijection.

Here, $\beta:M\rightarrow N$ is a bijection of finite sets, $\mathcal{S}$ is a species, and $\mathcal{S}[\beta]:\mathcal{S}[M]\rightarrow\mathcal{S}[N]$ is "the induced map" by $\mathcal{S}$.

My problem is that I am having trouble writing what a general $\sigma\in\mathcal{S}[M]$ looks like. I understand how I would prove what is to be shown when $\mathcal{S}$ is the species of finite graphs, the power set, the permutations, or any of the other specific cases of species that I've seen. I understand completely how these work. However, these species all have their particular notation where I can go in and apply $\beta$ to elements of $M$ to show how $\beta$ acts on $\sigma\in\mathcal{S}[M]$, and thus describe the induced map $\mathcal{S}[\beta]$. But how do I do this when $\mathcal{S}$ is kept general? How would I notate $\mathcal{S}[\beta]$ well enough to prove it's bijective?

• Should it be $\mathcal{S}[\beta]: \mathcal{S}[M] \to \mathcal{S}[N]$ is the "induced map" which we are trying to prove is a bijection? – John Machacek Jun 15 '14 at 20:58
• Use the definition. Functors take isomorphisms to isomorphisms. – Qiaochu Yuan Jun 15 '14 at 21:49
• The definition given in my book is "A species is defined to be a mapping $\mathcal{S}$ that associates to each finite set $M$ a finite set $\mathcal{S}$ consisting of elements $\sigma\in\mathcal{S}[M]$ that can be expressed in terms of the labels $m$ of the elements of $M$ only." I don't know what to do with this definition, @QiaochuYuan, which is why I'm asking the question. – user157261 Jun 15 '14 at 22:49
• That seems ambiguous. The correct definition is that a species is a functor from the category of finite sets and bijections to, say, the category of sets. – Qiaochu Yuan Jun 15 '14 at 23:05
• @Qiaochu I feel like I should prove that that's true before I can use it. (which I'd like to.) But in doing so I think I have the same problem as mentioned in my post - I don't know how to describe an element in the general case. I mean, I could do it given a specific functor / species, like for graphs, but if I'm not given one what can I do? – user157261 Jun 16 '14 at 1:15

Your book certainly requires that $\mathcal{S}$ carries composite functions to composites, in the sense that if $M,M',M''$ are finite sets and $M\xrightarrow{f}M'\xrightarrow{g}M''$ are maps between them, then $$\mathcal{S}[g\circ f]=\mathcal{S}[g]\circ\mathcal{S}[f]$$ and furthermore it should carry identity maps to identity maps, in the sense that for any finite set $M$ $$\mathcal{S}[\mathrm{id}_M]=\mathrm{id}_{\mathcal{S}[M]}$$

Now suppose $\beta:M\to N$ is a bijection of finite sets. Apply the two points above to $\beta$ and its inverse map $\alpha$.