Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathbf{Set}$ be the category of finite sets and functions between them, and let $\mathbf{Vect}$ be the category of finite-dimensional complex vector spaces and linear transformations between them. There is a free functor $G \colon \mathbf{Set} \to \mathbf{Vect}$, left adjoint to the forgetful functor, given by $G(X) = \mathbb{C}^X$ and $G(f)(\phi)(y) = \sum_{f(x)=y} \phi(x)$.

Is any functor $\mathbf{Set} \to \mathbf{Vect}$ of the form $H \circ G \circ F$ for $F \colon \mathbf{Set} \to \mathbf{Set}$ and $H \colon \mathbf{Vect} \to \mathbf{Vect}$?

A priori one might expect lots more functors, but I'm having a hard time coming up with any. On the other hand, functoriality seems to keep $G$ from "creating chaos" to "mess up freeness" (sorry that I can't explicate this feeling better). To keep it simple, let's keep things finite(-dimensional), and not consider anything about other base fields, or monoidal structure.

share|improve this question
    
If it helps, we may restrict to skeletons of $\mathbf{Set}$ and $\mathbf{Vect}$, i.e. to sets $\{1,\ldots,n\}$, and vector spaces $\mathbb{C}^n$ and matrices between them. –  Chris Heunen Jul 14 at 10:58
2  
Does the thing have to do much with complex numbers? As was noticed, Vect is equivalent to the category of finite sets and complex matrices. But even if you replace this by the category of finite sets and matrices with values in {0, 1}, i.e. the category Rel, will there be a counterexample? What would be the Rel analogue of the counterexample in the answer below? –  Dimitri Chikhladze Jul 14 at 20:36

3 Answers 3

up vote 13 down vote accepted

This is probably an absurdly over-complicated answer, but ...

Let $$J(X)=\left\{\sum_{x\in X}a_xx\in GX: \sum_{x\in X}a_x=0\right\}.$$

I claim that $J$ is not of the form $H\circ G\circ F$.

Suppose it were.

Let $n=\{0,\dots,n-1\}$.

The functors $F,G,H$ induce group homomorphisms $$S(n)\to S(F(n))\to \operatorname{GL}(GF(n))\to\operatorname{GL}(HGF(n))$$ (where $S(n)$ is the symmetric group) and $J(n)$ is a representation (of dimension $n-1$) of all of these groups. It's irreducible as an $S(n)$-module, and so must be irreducible for all the other groups. (Actually, I'm really only going to need the case $n=3$.)

Since, for $0<n<m$, $n$ is a retract of $m$, and $J(n)\not\cong J(m)$, it follows that $F(n)\not\cong F(m)$ and $|F(1)|<|F(2)|<\dots$. So $\dim GF(n)\geq n-1 (=\dim HGF(n))$. But all homomorphisms $\operatorname{GL}(k,\mathbb{C})\to\operatorname{GL}(l,\mathbb{C})$ have abelian image for $k>l$ and so $\dim GF(n)=|F(n)|=n-1$ for $n>2$, or else $J(n)$ would be a direct sum of one-dimensional representations.

But $S(n-1)$ doesn't usually have any $(n-1)$-dimensional irreducible representations.

share|improve this answer
    
Very nice, thanks! Would imposing any linear relation on $G$ do the trick? –  Chris Heunen Jul 14 at 20:05
3  
@ChrisHeunen The linear relation would have to be essentially the one in the answer, in order for $J$ to be a functor. You need $J(f)$ to make sense, in particular for $f$ a permutation. –  Andreas Blass Jul 14 at 20:26

The easiest example is the functor that sends the empty set to a 1-dimensional vector space, and all other finite sets to zero. (Any H that sends some vector space to 0 must send 0 to 0 as well).

The second-easiest example is the one given by Jeremy Rickard.

If you're interested in functors from the category of finite sets to finite dimensional vector spaces, you might take a look at my paper http://arxiv.org/abs/1406.0786 The main result is a structure theorem about (finitely-generated) functors in this category.

share|improve this answer

There are some functors obtained by the "doubly contravariant trick" --- composites of the form $\mathbf{Set}\to\mathbf{Set}^{\mathrm{op}}\to\mathbf{Vect}$ or $\mathbf{Set}\to\mathbf{Vect}^{\mathrm{op}}\to\mathbf{Vect}$. I doubt all these can be represented as $H\circ G\circ F$...

share|improve this answer
    
$\mathbf{Vect}$ is equivalent to $\mathbf{Vect}^\mathrm{op}$, so that shouldn't matter. What is the functor $\mathbf{Set} \to \mathbf{Set}^\mathrm{op}$ you're using? –  Chris Heunen Jul 14 at 15:16
    
@ChrisHeunen just to clarify -- the equivalence of Vect with its opposite category is something special to the finite-dimensional case, right? –  Yemon Choi Jul 14 at 15:33
    
@YemonChoi: that's correct. In arbitrary dimension there is also a "free" functor $G \colon \mathbf{Set}^\mathrm{op} \to \mathbf{Vect}$, and we could ask the same question based on $G$ for contravariant functors, I suppose. Are the two questions related? –  Chris Heunen Jul 14 at 15:46
    
@ChrisHeunen You are probably right about the equivalence... for $\mathbf{Set}\to\mathbf{Set}^{\mathrm{op}}$ - well any contravariant hom would do, that is, $\hom(\_,S)$ for any finite set $S$... –  მამუკა ჯიბლაძე Jul 14 at 15:48

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.