Over six years ago, I wrote a post explaining how virtual species are defined. Ever since then (time flies!) I’ve been meaning to write a follow-up post explaining a bit more about virtual species and how they actually suffice to give us not just additive inverses, but also (somewhat surprisingly) multiplicative inverses.

Recall that the intuitive idea of a combinatorial species is a family of labelled structures which are invariant under relabelling. If you’ve never seen the formal definition before, don’t worry: just think “data structures” or “algebraic data types” for now.

The basic idea of virtual species is to work with pairs of species \((P,N)\) where \(P\) is considered “positive” and \(N\) “negative”. Formally, we consider equivalence classes of such pairs under the equivalence relation defined by \((P_1, N_1) \cong (P_2, N_2)\) iff \(P_1 + N_2 = P_2 + N_1\).¹ This parallels the way one typically gives a formal definition of the integers starting from the natural numbers (the “Grothendieck construction”); see my previous post for more details.

Intuition

How can we build intuition for virtual species, and for additive inverses of species in particular? To be honest I have been struggling with this question for many years.

Multiplicative inverses are much simpler to think about: they are like matter and antimatter. Having both an \(F\)-structure and an \(F^{-1}\) structure is the same as having nothing; they annihilate each other. By “having nothing” we mean “having no information”, that is, having a unit value: \(F F^{-1} = 1\).

What about additive inverses? Note first that the \(0\) species does not correspond to having nothing; the word “nothing” corresponds to the \(1\) (i.e. unit) species. Instead the \(0\) (i.e. uninhabited) species corresponds to (logical) impossibility. So to interpret \(-F\) we have to imagine something where having either \(F\) or \(-F\) is impossible.

…yeah, me neither. This seems deeply strange. If someone says, “I either have an \(F\) or a \(-F\)”, you can confidently call them a liar, because it is impossible to have either an \(F\) or a \(-F\); that is, \(F - F = 0\). But surely if you actually have an \(F\)-structure, it should also be true to say “I have either an \(F\) or a \(G\)”? Well, that works for normal, positive species—in which case we can define a canonical injection \(F \to F + G\). But once we introduce negative species this completely breaks down. As another example, if someone truthfully says, “I have either a tree or a negative non-empty tree”, you should be able to say, “Aha! I know what you have—it must be an empty tree.” In general, it’s strange that expressing a disjunction can cause some possibilities to be ruled out. Normally, we are used to disjunctions only increasing the number of possibilities.

Inspired by James and Sabry’s really cool paper The Two Dualities of Computation: Negative and Fractional Types, I have thought a bit about whether there is some plausible interpretation involving travelling backwards in time, but I haven’t been able to come up with one. I can’t quite seem to make the formalism of the paper match up with my intuition about species (though this may just be a failure of my imagination or intuition).

Multiplicative Inverses

In any case, let’s see why the ring of virtual species actually has multiplicative inverses—at least, all the ones we could possibly hope for. This is somewhat surprising, since when we build integers from natural numbers by considering equivalence classes of pairs, we certainly don’t get any multiplicative inverses, only additive ones. To get multiplicative inverses we have to do the same process a second time, building the rational numbers as equivalence classes of pairs of integers. But species already have enough extra structure that throwing in additive inverses is all it takes.

First, a caveat: we don’t get multiplicative inverses for all species, but only those species \(G\) such that \(G(0) = 1\): that is, species \(G\) with only a single structure of size zero, which are of the form \(G = 1 + X(\dots)\). With any constant term other than \(1\), we clearly have no hope of finding another species \(H\) such that \(GH = 1\), since the constant term of \(GH\) will be a multiple of \(G\)’s constant term.

So given such a \(G\), write \(G = 1 + G_+\), where \(G_+\) denotes “non-empty \(G\)-structures”. Then we can define the multiplicative inverse of \(G\) as follows:

That is, a \(G^{-1}\)-structure consists of a list of nonempty \(G\)-structures, except that even-length lists are considered “positive” and odd-length lists considered “negative”.

We can easily check that this indeed defines a multiplicative inverse for \(G\):

The infinite sums telescope down to leave only \(1\). Notice this really isn’t about species in particular, but really about infinite power series (of which species are the categorification): any infinite power series with integer coefficients and a constant term of \(1\) has a multiplicative inverse which is also such a power series.

As an example, consider \(1/(1-X) = (1-X)^{-1}\). We know this is “supposed” to be the species of lists (since it results from solving \(L = 1 + XL\) for \(L\)), but let’s see what happens. In this case \(G = 1-X\) and \(G_+ = -X\). So the inverse ought to be

And hey, look at that! Lists!

A field of species?

So what would we need to get a true field, i.e. a multiplicative inverse for every nonzero species? Well, for that we would need to throw in rational coefficients. I forget exactly where I read this—some paper by Baez and Dolan, most likely—but I believe the proper way to interpret this would be as groupoid-valued species, since there is a sense in which the “cardinality” of groupoids can be interpreted as rational numbers. But to be honest I have no idea where this leads.