Combinatorial Species - Class of All Species

Class of All Species

There are many ways of thinking about the class of all combinatorial species. Since a species is a functor, it makes sense to say that the category of species is a functor category whose objects are species and whose arrows are natural transformations. This idea can be extended to a bicategory of certain categories, functors, and natural transformations, to be able to include species over categories other than . The unary and binary operations defined above can be specified in categorical terms as universal constructions, much like the corresponding operations for other algebraic systems.

Though the categorical approach brings powerful proof techniques, its level of abstraction means that concrete combinatorial results can be difficult to produce. Instead, the class of species can be described as a semiring — an algebraic object with two monoidal operations — in order to focus on combinatorial constructions. The two monoids are addition and multiplication of species. It is easy to show that these are associative, yielding a double semigroup structure; and then the identities are the species 0 and 1 respectively. Here, 0 is the empty species, taking every set to the empty set (so that no structures can be built on any set), and 1 is the empty set species, which is equal to 0 except that it takes to (it constructs the empty set whenever possible). The two monoids interact in the way required of a semiring: addition is commutative, multiplication distributes over addition, and 0 multiplied by anything yields 0.

The natural numbers can be seen as a subsemiring of the semiring of species, if we identify the natural number n with the n-fold sum 1 + ... + 1 = n 1. This embedding of natural number arithmetic into species theory suggests that other kinds of arithmetic, logic, and computation might also be present. There is also a clear connection between the category-theoretic formulation of species as a functor category, and results relating certain such categories to topoi and Cartesian closed categories — connecting species theory with the lambda calculus and related systems.

Given that natural number species can be added, we immediately have a limited form of subtraction: just as the natural number system admits subtraction for certain pairs of numbers, subtraction can be defined for the corresponding species. If n and m are natural numbers with n larger than m, we can say that n 1 − m 1 is the species (n − m) 1. (If the two numbers are the same, the result is 0 — the identity for addition.) In the world of species, this makes sense because m 1 is a subspecies of n 1; likewise, knowing that E = 1 + E+, we could say that E+ = E − 1.

Going further, subtraction can be defined for all species so that the correct algebraic laws apply. Virtual species are an extension to the species concept that allow inverses to exist for addition, as well as having many other useful properties. If S is the semiring of species, then the ring V of virtual species is (S × S) / ~, where "~" is the equivalence relation

(F, G) ~ (H, K) if and only if F + K is isomorphic to G + H.

The equivalence class of (F, G) is written "F − G". A species F of S appears as F − 0 in V, and its additive inverse is 0 − F.

Addition of virtual species is by component:

(F − G) + (H − K) = (F + H) − (G + K).

In particular, the sum of F − 0 and 0 − F is the virtual species F − F, which is the same as 0 − 0: this is the zero of V. Multiplication is defined as

(F − G)·(H − K) = (F·H + G·K) − (F·K + G·H)

and its unit is 1 − 0. Together, these make V into a commutative ring, which as an algebraic structure is much easier to deal with than a semiring. Other operations carry over from species to virtual species in a very natural way, as do the associated power series. "Completing" the class of species like this also means that certain differential equations insoluble over S do have solutions in V.