The algebra of species: primitives

[This is the fifth in a series of posts about combinatorial species. Previous posts: And now, back to your regularly scheduled combinatorial species; Decomposing data structures; Combinatorial species definition, Species definition clarification and exercises.]

Recall that a species is a functor from $\mathbb{B}$ , the category of finite sets and bijections, to $\mathbb{E}$ ,¹ the category of finite sets and total functions. (Equivalently, species are endofunctors on $\mathbb{B}$ , but in this post I’m going to want to think about them as the former.) That is, a species $F$ is a mapping sending every set of labels $U$ to a set of structures $F[U]$ , which also lifts relabelings $\sigma : U \leftrightarrow V$ to functions $F[\sigma] : U \to V$ in a way that respects the compositional structure of bijections.

However, as I hinted in a previous post, it’s inconvenient to work directly with this definition in practice. Instead, we use an algebraic theory that lets us compositionally build up certain species from a collection of primitive species and species operations. (It’s important to note that it does not allow us to build all species, but it does allow us to build many of the ones we care about.)

In this post we’ll begin by examining a few natural species to take as primitive.

The zero or empty species, denoted $\mathbf{0}$ , is the unique species with no structures whatsoever; that is,

$\mathbf{0}[U] = \emptyset$

and

$\mathbf{0}[\sigma : U \leftrightarrow V] = id_{\emptyset} : \mathbf{0}[U] \to \mathbf{0}[V]$ .

Of course, $\mathbf{0}$ will turn out to be the identity element for species sum (which I’ll define in my next post, though it’s not hard to figure out what it should mean).
The unit species, denoted $\mathbf{1}$ , is defined by

$\begin{array}{lcl}\mathbf{1}[\emptyset] &=& \{\star\} \\ \mathbf{1}[U] &=& \emptyset \qquad (U \neq \emptyset)\end{array}$

That is, there is a unique $\mathbf{1}$ -structure indexed by the empty set of labels, and no $\mathbf{1}$ -structures with any positive number of labels. $\mathbf{1}$ lifts bijections in the obvious way, sending every bijection to the appropriate identity function.

Some people initially find this definition surprising, expecting something like $\mathbf{1}[U] = \{ \star \}$ for all $U$ instead. That is indeed a valid species, and we will meet it below; but as I hope you will come to see, it doesn’t deserve the name $\mathbf{1}$ .

Of course we should also verify that this definition satisfies the requisite functoriality properties, which is not difficult.

More abstractly, for those who know some category theory, it’s worth mentioning that $\mathbf{1}$ can be defined as $\mathbb{B}(\emptyset, -) : \mathbb{B} \to \mathbb{E}$ , that is, the covariant hom-functor sending each finite set $U \in \mathbb{B}$ to the (finite) set of bijections $\emptyset \leftrightarrow U$ . (This is why I wanted to think of species as functors $\mathbb{B} \to \mathbb{E}$ . I learned this fact from Yeh (1986).) There is, of course, a unique bijection $\emptyset \leftrightarrow \emptyset$ and no bijections $\emptyset \leftrightarrow U$ for nonempty $U$ , thus giving rise to the definition above.

As you might expect, $\mathbf{1}$ will be the identity element for species product. Like $\mathbf{1}$ itself, species product isn’t defined quite as most people would initially guess. If you haven’t seen it before, you might like to try working out how product can be defined in order to make $\mathbf{1}$ an identity element.
The singleton species, denoted $\mathbf{X}$ , is defined by

$\mathbf{X}[U] = \begin{cases} U & |U| = 1 \\ \emptyset & \text{otherwise} \end{cases}$

with lifting of bijections defined in the evident manner. That is, there is a single $\mathbf{X}$ -structure on a label set of size $1$ (which we identify with the label itself, though we could have also defined $\mathbf{X}[U] = \{\star\}$ when $|U| = 1$ ), and no $\mathbf{X}$ -structures indexed by any other number of labels.

As with $\mathbf{1}$ , we may equivalently define $\mathbf{X}$ as a hom-functor, namely $\mathbf{X} = \mathbb{B}(\{\star\}, -)$ .

It’s worth noting again that although $\mathbf{1}$ and $\mathbf{X}$ do “case analysis” on the label set $U$ , they actually only depend on the size of $U$ ; indeed, as we noted previously, by functoriality this is all they can do.
The species of bags², denoted $\mathbf{E}$ , is defined by

$\mathbf{E}[U] = \{U\}$ ,

that is, there is a single $\mathbf{E}$ -structure on any set of labels $U$ , which we usually identify with the set of labels itself (although we could equivalently define $\mathbf{E}[U] = \{\star\}$ ). The idea is that an $\mathbf{E}$ -structure consists solely of a collection of labels, with no imposed ordering whatsoever.

If you want to abuse types slightly, one can define $\mathbf{E}$ as a hom-functor too, namely $\mathbb{E}(-,\{\star\})$ . (Yeh (1986) actually has $\mathbb{B}(-, \{\star\})$ , but that’s wrong.)

As a summary, here’s a graphic showing $\mathbf{0}$ -, $\mathbf{1}$ -, $\mathbf{X}$ -, and $\mathbf{E}$ -structures arranged by size (i.e., the size of the underlying set of labels $U$ ): a dot indicates a single structure, and the size of the label set increases as you move to the right.

Just as a teaser, it turns out that $\mathbf{X}$ and $\mathbf{E}$ are identity elements for certain binary operations on species as well, though you’ll have to wait to find out which ones!

Next up, addition!

References

Yeh, Yeong-Nan. 1986. “The calculus of virtual species and K-species.” In Combinatoire énumérative, ed. Gilbert Labelle and Pierre Leroux, 1234:351–369. Springer Berlin Heidelberg. http://dx.doi.org/10.1007/BFb0072525.

Last time I called this category $\mathbf{FinSet}$ , but $\mathbb{E}$ is more concise and matches the species literarure.↩
The species literature calls this the species of sets, but that’s misleading to computer scientists, who expect the word “set” to imply that elements cannot be repeated.↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

7 Responses to The algebra of species: primitives

Omar says:

January 9, 2013 at 6:29 am

Can you explain what you mean in footnote [2]? I don’t see bags anywhere: there is a unique E-structure on a SET of labels U which can be identified with the SET U itself.

[I would expect something called the species of bags to have bags as structures, not sets. Say, generalizing species to allow infinitely many structures on a single set of labels, i.e. generalizing to functors B->Sets, I’d expect the species of bags to be Sets(.,N) where N is the natural numbers (a bag on U can be regarded as a function U->N giving the multiplicities of each element).]

- Brent says:
  
  January 9, 2013 at 1:38 pm
  
  Great question! I probably should have done a better job explaining that footnote. Remember that we are talking about labeled shapes, not data structures. An E-structure is just the shape of a bag. To make an actual bag data structure we would pair an E-structure (i.e. a set of labels $U$ ) with any total function of type $U \to A$ . The fact that the function need not be injective reflects the fact that values of type $A$ can show up multiple times. (If you wanted set data structures instead, you could restrict the function to be injective.) Labels, on the other hand, should be unique, so the fact that an E-structure is a set just reflects the lack of ordering.
  
  - Omar says:
    
    January 10, 2013 at 3:16 am
    
    Oh, I see. Combinatorialists study E-structures, they don’t use them as containers for data, so it makes sense that they call this particular E the species of sets.
    
    Do you do this renaming consistently? For example, do you call the species of graphs “the species of graphs with possibly repeated vertices” or something like that?
    
    - Brent says:
      
      January 11, 2013 at 6:38 pm
      
      No, because the term “graph” does not have a connotation of “the data stored at vertices is unique”, so there is no opportunity for confusion.
      
Andrew Gainer-Dewar says:

January 24, 2013 at 12:45 am

I’ve been interested in the connections between species theory and data types for a while now. (I’m an enumerative combinatorialist by trade, but I have some amateur interest in the formal side of theoretical CS.) I’ll definitely be following this series with keen interest!

Pingback: Avoiding the axiom of choice, part I | blog :: Brent -> [String]
Pingback: Signed sets and ballots, part 1 | blog :: Brent -> [String]