Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A species $F$ is defined as an endofunctor of the category of finite sets. What if our combinatorial structure is not defined for sets of arbitrary size. More precisely, can we define a species from a subcategory of finite sets? For example, the species of Sudoko puzzles.

share|improve this question
    
Maybe I am comfused about the defenition of an endofunctor. Is it F:G-->G necessarily defined for all of the objects in G? –  user34942 Jul 18 '12 at 13:48

1 Answer 1

A combinatorial species is designed to capture an infinite family of combinatorial structures, which will always just be sets enriched with additional structure built out of them in some way. It is a way for category theory to externalize the "building process" (transfer outside objects to the viewpoint of morphisms). A species is in fact an endofunctor on $\cal B$ (finite sets with bijections) and therefore must be defined for all finite sets. This lack of restrictions on the sets allows basic operations on species to make sense (and everybody loves generating functions!), essentially allowing a notion of "closure" under intuitive structure-combining operations analogous to arithmetic / algebraic operations.

It should be possible however to imagine a functor $\cal C\to B$ with $\cal C$ a possibly finite subcategory of $\cal C$; such functors no longer carry forward the far-reaching purpose of combinatorial species. I am not aware if these have a name, so in practice you could probably just name them something yourself.

Note thought it is possible to conceptualize sudokus as being built from sets of arbitrary size; for the case of $n=3$ we have the usual sudoku given as a $3\times 3$ array of $3\times 3$ blocks partially filled in with elements from $1,2,\cdots 9$ (which we identify with $[3]^2=\{1,2,3\}\times\{1,2,3\}$ for functorial purposes), in a way that it is possible to fill in the empty spaces so that each row, column, and block contains every element of $[3]^2$. The set of all such sudokus is the image of $[3]$ under the "sudoku species."

Exercise: How to phrase this appropriately in an elementary-set-theoretic way that doesn't rely on "columns" and "rows"? Hint: Recall how direct products may be defined via choice functions. The effect of the functor on bijections is essentially "relabelling the entries."

Further note: more generally we can also define sudokus as bifunctors $F:\cal B\times B\to B$, by forming an array of blocks of products, i.e. $F(A,B)$ is the set of functions $(A\times B)^2\to(A\times B)\cup\{\square\}$ that result from altering some of the outputs of some function $(A\times B)^2\to(A\times B)$ to a blank square (again, satisfying the appropriate "row, column, block" conditions). I don't know of a name for the bifunctors like this, but they are very much in the spirit of combinatorial species. Maybe one can even combine this bifunctor idea with the partition species to create jigsaw sudokus?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.