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 
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 
What about additive inverses? Note first that the 
…yeah, me neither. This seems deeply strange. If someone says, “I either have an 
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 
So given such a 
That is, a 
We can easily check that this indeed defines a multiplicative inverse for
![\displaystyle \begin{array}{rcl}G G^{-1} &=& (1 + G_+) (1 - G_+ + G_+^2 - G_+^3 + \dots) \\[0.5em] &=& (1 - G_+ + G_+^2 - G_+^3 + \dots) + (G_+ - G_+^2 + G_+^3 - G_+^4 + \dots) \\[0.5em] &=& 1 \end{array}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cbegin%7Barray%7D%7Brcl%7DG+G%5E%7B-1%7D+%26%3D%26+%281+%2B+G_%2B%29+%281+-+G_%2B+%2B+G_%2B%5E2+-+G_%2B%5E3+%2B+%5Cdots%29+%5C%5C%5B0.5em%5D+%26%3D%26+%281+-+G_%2B+%2B+G_%2B%5E2+-+G_%2B%5E3+%2B+%5Cdots%29+%2B+%28G_%2B+-+G_%2B%5E2+%2B+G_%2B%5E3+-+G_%2B%5E4+%2B+%5Cdots%29+%5C%5C%5B0.5em%5D+%26%3D%26+1+%5Cend%7Barray%7D&bg=ffffff&fg=333333&s=0&c=20201002)
The infinite sums telescope down to leave only
As an example, consider 
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.
-
Note that species sum is cancellative—that is, if
then
—so this is a coherent definition. This cancellative property is probably worth another post of its own since the reason for it is not entirely trivial.↩
blog :: Brent -> [String] 
This 404’s, do have an updated link? https://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf
Yes, you can now find it here: http://ozark.hendrix.edu/~yorgey/pub/species-pearl.pdf
Okay, I am sure you have thought of this, but cardinality and un-normalized discreet probability are pretty dang closely related. Which ishould in turn closely related to general probability, and quantum logic* is often considered to be the generalization of probability. So maybe, maybe..embedding virtual species in a complex space makes sense?
So maybe equivalence classes of (P, N) * e ^ipiR? Not sure if R is just a real and e^ipi_ is basicly just formal, or if e^ipiR is some sort of function space?
Now this line of inqirery might be pointless, because quantum amplitudes don’t have a intuitive semantics, so all that work might just give us another formal model with no intuition.
On another topic, I to don’t really understand the semantics of additive cup and cap in The Two Dualities of Computation: Negative and Fractional Types.
Linear types also have a “negative” of sorts, with a pretty straitfroward interpretation as moving the type from environment to production.
(Parts of which are even preserved in non linear types. For example the isomorphism between (a+b)->c and (a->c,b->c) )
But I little idea what “linear” species would be. As you now have two additions and two multiplications, and each only distributes over the one they are not dual with. Maybe by using “classical” liner types you can use the demorgan rules to normalize things?
Sorry for the long rambling comment.
Thanks for the comment! I’m really not sure about any of this, though.
Neither am I!
Perhaps considering species valued in (monoidal) categories with a magnitude as surveyed in Leinster’s “The magnitude of a metric space: from category theory to geometric measure theory” https://arxiv.org/abs/1606.00095 would produce something interesting in that vein.
Thanks for the link, I’ll have to give that a read.
Awesome! Applying the Grothendieck group construction to the algebra of graphs has been on my todo list for quite some time, but I had no idea one may also be able to get multiplicative inverses for free. In my case, the cancellation law does not hold, so there will be some complications though. And then there is this weird fact that 0=1, so let’s see what happens :-)
Sounds like fun! My understanding is that if cancellation does not hold then you want to define (a,b) = (c,d) iff there is some x such that a+d+x = b+c+x.
The problem with the standard \exists x. p1+n2+x = p2+n1+x definition is that if x is a complete graph of the whole universe, then a + x = x, and everything collapses into the same equivalence class. In other words, existence of an absorbing element seems to lead to a trivial group in Grothendiek construction. Sets are quite similar to graphs in this sense; perhaps, I should start by looking for ways to turn a set into a non-trivial group, although I now doubt if it’s possible at all.
Aha, I see, that is a problem indeed.
Well if you have a weighting on edges that is a group then you don’t really need the grothendieck construction, and can still get some nice ideas of negation.
For example:
Using F T under xor gets you sum where a graph is its own inverse. Weighting by Z gives you Multigraphs that can have negative number of edges. Wightin by R+ (and using multiplication) you get something really weird.
But I think your addition is closer to an meet/union then a disjoint union so maybe look at lattices? Or at the min,+ rig?
You have probably considered all this.
Thanks Chris!
I do have a few examples where nodes and edges have labels that form a semiring, and so far these semirings were idempotent, to match the a + a = a law in the algebra (a natural definition for labelled graph overlay is [x]a + [y]a = [x y]a).
Your suggestion to consider labels forming a group is interesting. Indeed, this will give negation, even though we’ll then lose the idempotence of graph overlay. I’ll look into it!
That should have been [x]a + [y]a = [x ++ y]a, where ++ is the addition from the semiring.
What does it mean that 0 = 1 in the algebra of graphs? Any semiring satisfying 0 = 1 is trivial, are graphs a different algebraic structure?
Indeed, it’s not quite a semiring: https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/
If you don’t want to read the whole blog post that Brent linked to, here is a simple fact: if you add axiom xyz = xy + xz + yz to a semiring-without-annihilation-axiom (*), you force 0 = 1. The elements of the resulting structure correspond to graphs.
(*) Semirings are often (but not always!) defined with the annihilation axiom: 0x = x0 = 0. If you have this axiom, then everything indeed collapses when 0=1.
Regarding difference of species, I would recommend thinking of them in term of difference of multisets (think of what the Grothendieck construction does to multiset).
Examples where a difference of two species is a species but not one with a (recursive) polynomial definition can be nice. I think this works: Lists – Bags ≃ Non-increasing lists.
(Disclaimer: my knowledge of species is very limited)
I think I see what you mean about multisets — it does make for nice intuition to explain why there exist “purely virtual” species which are neither positive nor negative (in the same way that a “purely virtual multiset” might contain a positive number of one element and a negative number of another). Though I don’t really see how it helps come up with an intuitive idea of how to constructively interpret virtual species.
I like your example of Lists – Bags. But I am not exactly sure what you mean by “non-increasing”. Do you mean lists where the labels are not sorted in increasing order (i.e. identifying a bag of size n with a canonically sorted list of size n)? That does make for a nice example, although to be pedantic we can really only interpret Lists – Bags as non-sorted lists in the context of L-species (where the labels are equipped with a linear order).
Sorry: I’m a high-latency person.
The intuition I have, with multisets, is fibres of species are like multisets. Ostensibly they’re sets, but since the sum is tagged, they are more like multisets: L+L has two of each lists at each size. And sum is fibre-wise. It’s kind of where sum and product differ: products modify what « shapes » are available at each fibre, for sums, the « shape » of object is opaque, so we might as well take blurry glasses and see them as atoms. So, from this point of view, sums are pretty much just fibre-wise multiset sums (and subtraction, fibre-wise « virtual » multiset subtraction).
Regarding List-Bags: that’s indeed what I meant. And I realise that I was abusing the notation a bit (we could say that it’s all the lists except one per size, then every choice of the one missing list yields a syntactically different, but equivalent, species, but that’s rather boring…).
Hey, man do you mind if I register your rss feed on gwene. I would love to be able to read your blog
with gnus.
Sure, be my guest.
Pingback: Signed sets and ballots, part 1 | blog :: Brent -> [String]