Primitive species and species operations, part II

In my previous post, I began describing the primitive species and species operations supported by my combinatorial species library; we looked at the ring structure on species, that is, the primitive species \(0\) and \(1\), and the operations of species sum and product. Today we’ll continue by looking at a few more primitive species: singletons, sets, and cycles.

[By the way, all the diagrams for this post and the previous one were generated programmatically using my diagrams library. I’ll probably put the code up as an example on the diagrams website sometime in the near future.]

X

The species \(X\), also known as the species of singletons, is picky in a way similar to the species \(1\). Whereas \(1\) only puts a structure on the empty set of labels, X only puts a (single) structure on singleton label sets. If you give it more than one label, or none, it turns up its nose and refuses to do anything.

[caption id=“attachment_227” align=“aligncenter” width=“400” caption=“The species X of singletons”][/caption]

> take 10 $ labelled singleton [0,1,0,0,0,0,0,0,0,0] > generate singleton ([‘a’] :: [Char]) [‘a’] > generate singleton (“abc” :: [Char]) []

1. Describe the species \(X + X\). Show that it is isomorphic to the species \(2 * X\).
2. Describe the species \(X * X\).

E

The species \(E\) of sets, on the other hand, isn’t picky at all: it will happily put a singleton structure on any label set. Usually we identify this structure with the label set itself; that is, the only \(E\)-structure on a label set \(U\) is \(U\) itself.

[caption id=“attachment_258” align=“aligncenter” width=“400” caption=“The species E of sets”][/caption]

> take 10 $ labelled sets [1,1,1,1,1,1,1,1,1,1] > take 10 $ unlabelled sets [1,1,1,1,1,1,1,1,1,1] > generate set ([1..3] :: [Int]) [{1,2,3}] > generate set ([] :: [Int]) [{}]

We can now also describe the derived species \(X * E\) of elements, also known as the species of pointed sets. The only way to get any \(X * E\) structures is by partitioning the label set \(U\) into a singleton and all the rest, in which case we get exactly one structure; so there is one \(X * E\) structure for each element of \(U\).

> take 10 $ labelled (x * set) [0,1,2,3,4,5,6,7,8,9] > take 10 $ unlabelled (x * set) [0,1,1,1,1,1,1,1,1,1] > generate (x * set) ([1..3] :: [Int]) [(1,{2,3}),(2,{1,3}),(3,{1,2})]

(x is just a synonym for singleton.) Noteworthy is the fact that this is the first species we’ve looked at which has different numbers of labelled and unlabelled structures! This makes sense: there are \(n\) labelled \((X * E)\)-structures on a size \(n\) set; but if we can’t tell the difference between the labels, any one of them is just as good as any other, so we only get one unlabelled structure (unless the label set is empty, when we don’t get any structures: the \(X\) still requires us to have at least one element!). Note also that element is a special synonym for x * set with a special semantics under generate: if we really want to pick elements of the label set, then we probably don’t want to actually see each element paired with a set of the leftover elements, we just want to see the element itself:

> generate elements ([1..3]::[Int]) [1,2,3]

C

The final primitive species—and the only one so far that doesn’t feel quite so utterly trivial—is the species \(C\) of cycles. \(C\) puts no structures on an empty label set, but given any non-empty label set, \(C\) generates the set of all cyclical orderings of the labels.

[caption id=“attachment_259” align=“aligncenter” width=“400” caption=“The species C of cycles”][/caption]

Of course, the above diagram only shows six of the cycle structures on five labels; the ellipsis is meant to suggest the others not shown. So… how many labelled cycle structures are there on five labels, or generally on \(n\) labels? (Of course there is only one unlabelled \(n\)-cycle.) I’ll leave it as a (hopefully easy) exercise; and of course you know how to check your answer!

> generate cycles ([1..4] :: [Int]) [<1,2,3,4>,<1,2,4,3>,<1,3,2,4>,<1,3,4,2>,<1,4,2,3>,<1,4,3,2>]

As you can see, cycles are indicated with angle brackets; it is understood that <1,2,3,4>, <2,3,4,1>, <3,4,1,2>, and <4,1,2,3> are all equivalent.

At this point, you’re probably thinking about a certain species and wondering why I haven’t mentioned it yet—it seems pretty fundamental and primitive. Are you thinking of… the species of lists? It turns out that we don’t have to take lists as primitive—we can define the species of lists as the derivative of the species of cycles! The derivative of a regular type is its type of one-hole… but I’m getting ahead of myself. We’ll look at species differentiation (along with several other operations on species) in the next post!