Skip to main content
MathOverflow

Return to Answer

added 776 characters in body
Source Link
Will Sawin
Will Sawin
  • 148.6k
  • 9
  • 324
  • 563

EDIT: This doesn't deal properly with the empty set, I will hopefully fix later.

Given a functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and a subset $E$ of $F(0)$, we can construct a natural functor from $(\operatorname{Finite Sets}, \operatorname{Injections})$ to $\operatorname{FinSet}$. The construction sends a functor $F$ to the functor $F'$ given by

unless $S$ is empty, in which case it is $F(0) \setminus E$.

To see the map is injective, suppose that $x \in G(S)$ lies in the image of $y \in F(A) \subseteq G(A) $ and $z \in F(B)\subseteq G(B)$ for two subsets $A, B$ of $S$. 

If $A=B$ then we can apply a left inverse of the inclusion $A \to S$ to see that $y=z$ in $G(A)$ and so $(A,y)= (B,z)$ in $F'(S)$. 

If $A\neq B$, assume wlog$B$ contains a nonempty proper subset which contains $B \not\subset A$$A \cap B$, and let $m$ be a left inverse of the inclusion $B \to S$ which sends $A \setminus B$ into $A \cap B$this proper subset. Let $i_A$ and $i_B$ be the inclusions of $A $ and $B$ into $S$. Then by functoriality $$ G_{i_A} (y) = x = G_{i_b}(z)$$ and so $$z = G_m ( G_{i_b}(z)) = G_m( G_{i_A}(x)) = G_{m \circ i_A} (x) $$

  but $m \circ i_A$ factors through the inclusion of $A \cap B$ into $B$, so $z$ lies in the image of $G(A \cap B)$ which contradicts the assumption that $z \in F(B)$. QED

This second case only fails if $B \subseteq A$ or $B$ has one element. By symmetry, we are also good unless $A \subseteq B$ or $A$ has one element. Because we also handled the cases $A = B$, the remaining cases are when $B$ and $A$ both have one element and are equal. In this case we have an isomorphism between $A$ and $B$ and left inverses show that this isomorphism sends $y$ to $z$, but injectivity can fail. To fix injectivitiy, we move these elements from $F(1)$ into $F(0)$ and place them in $E$ (the set of evil elements).

 

(or $|F(0)|-|E|$ if $n=0$) so if a sequence $a_n$ arises from any functor from finite sets to finite sets (and not just a monad) we must have

for some sequence of natural numbers $b_k$, with $a_0=b_0-e$. This gives the inequalities described by Valery Isaev.

Conversely, for any functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and evil subset $E$, if $F(0)\neq 0$$F(0)\setminus E \neq 0$ and $F(1)\neq 0$ we can extend $F'$ to a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and in fact to a monad.

To do this, fix $c \in F(0)$$c \in F(0)\setminus E$ and thus in $F'(S)$ for all $s$, and fix $i \in F(1)$ and thus an injective natural transformation $i: S \to F'(S)$ for all $S$.

Also Valery showed that if $b_1$ is zero, we must have $b_0=0$ or $1$ and all higher $b_i=0$. So the main case of interest is when $b_0=0$ and $b_1$ is not zero. In this case there may be more restrictions on the $b_i$s.

EDIT: This doesn't deal properly with the empty set, I will hopefully fix later.

Given a functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$, we can construct a natural functor from $(\operatorname{Finite Sets}, \operatorname{Injections})$ to $\operatorname{FinSet}$. The construction sends a functor $F$ to the functor $F'$ given by

To see the map is injective, suppose that $x \in G(S)$ lies in the image of $y \in F(A) \subseteq G(A) $ and $z \in F(B)\subseteq G(B)$ for two subsets $A, B$ of $S$. If $A=B$ then we can apply a left inverse of the inclusion $A \to S$ to see that $y=z$ in $G(A)$ and so $(A,y)= (B,z)$ in $F'(S)$. If $A\neq B$, assume wlog $B \not\subset A$, and let $m$ be a left inverse of the inclusion $B \to S$ which sends $A \setminus B$ into $A \cap B$. Let $i_A$ and $i_B$ be the inclusions of $A $ and $B$ into $S$. Then by functoriality $$ G_{i_A} (y) = x = G_{i_b}(z)$$ and so $$z = G_m ( G_{i_b}(z)) = G_m( G_{i_A}(x)) = G_{m \circ i_A} (x) $$

  but $m \circ i_A$ factors through the inclusion of $A \cap B$ into $B$, so $z$ lies in the image of $G(A \cap B)$ which contradicts the assumption that $z \in F(B)$. QED

so if a sequence $a_n$ arises from any functor from finite sets to finite sets (and not just a monad) we must have

for some sequence of natural numbers $b_k$.

Conversely, for any functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$, if $F(0)\neq 0$ and $F(1)\neq 0$ we can extend $F'$ to a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and in fact to a monad.

To do this, fix $c \in F(0)$ and thus in $F'(S)$ for all $s$, and fix $i \in F(1)$ and thus an injective natural transformation $i: S \to F'(S)$ for all $S$.

Also Valery showed that if $b_1$ is zero, we must have $b_0=0$ or $1$ and all higher $b_i=0$. So the main case of interest is when $b_0=0$ and $b_1$ is not zero.

Given a functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and a subset $E$ of $F(0)$, we can construct a natural functor from $(\operatorname{Finite Sets}, \operatorname{Injections})$ to $\operatorname{FinSet}$. The construction sends a functor $F$ to the functor $F'$ given by

unless $S$ is empty, in which case it is $F(0) \setminus E$.

To see the map is injective, suppose that $x \in G(S)$ lies in the image of $y \in F(A) \subseteq G(A) $ and $z \in F(B)\subseteq G(B)$ for two subsets $A, B$ of $S$. 

If $A=B$ then we can apply a left inverse of the inclusion $A \to S$ to see that $y=z$ in $G(A)$ and so $(A,y)= (B,z)$ in $F'(S)$. 

If $B$ contains a nonempty proper subset which contains $A \cap B$, let $m$ be a left inverse of the inclusion $B \to S$ which sends $A \setminus B$ into this proper subset. Let $i_A$ and $i_B$ be the inclusions of $A $ and $B$ into $S$. Then by functoriality $$ G_{i_A} (y) = x = G_{i_b}(z)$$ and so $$z = G_m ( G_{i_b}(z)) = G_m( G_{i_A}(x)) = G_{m \circ i_A} (x) $$ but $m \circ i_A$ factors through the inclusion of $A \cap B$ into $B$, so $z$ lies in the image of $G(A \cap B)$ which contradicts the assumption that $z \in F(B)$.

This second case only fails if $B \subseteq A$ or $B$ has one element. By symmetry, we are also good unless $A \subseteq B$ or $A$ has one element. Because we also handled the cases $A = B$, the remaining cases are when $B$ and $A$ both have one element and are equal. In this case we have an isomorphism between $A$ and $B$ and left inverses show that this isomorphism sends $y$ to $z$, but injectivity can fail. To fix injectivitiy, we move these elements from $F(1)$ into $F(0)$ and place them in $E$ (the set of evil elements).

 

(or $|F(0)|-|E|$ if $n=0$) so if a sequence $a_n$ arises from any functor from finite sets to finite sets (and not just a monad) we must have

for some sequence of natural numbers $b_k$, with $a_0=b_0-e$. This gives the inequalities described by Valery Isaev.

Conversely, for any functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and evil subset $E$, if $F(0)\setminus E \neq 0$ and $F(1)\neq 0$ we can extend $F'$ to a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and in fact to a monad.

To do this, fix $c \in F(0)\setminus E$ and thus in $F'(S)$ for all $s$, and fix $i \in F(1)$ and thus an injective natural transformation $i: S \to F'(S)$ for all $S$.

Also Valery showed that if $b_1$ is zero, we must have $b_0=0$ or $1$ and all higher $b_i=0$. So the main case of interest is when $b_0=0$ and $b_1$ is not zero. In this case there may be more restrictions on the $b_i$s.

Source Link
Will Sawin
Will Sawin
  • 148.6k
  • 9
  • 324
  • 563

I can give a more categorical description of the construction in Valery Isaev's answer.

EDIT: This doesn't deal properly with the empty set, I will hopefully fix later.

Given a functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$, we can construct a natural functor from $(\operatorname{Finite Sets}, \operatorname{Injections})$ to $\operatorname{FinSet}$. The construction sends a functor $F$ to the functor $F'$ given by

$$F'(S) = \bigcup_{A \subseteq S} F(A)$$

I claim every functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, when restricted to isomorphisms, arises this way.

To prove this let $G$ be a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and define $F(S)$ to be the subset of $G(S)$ consisting of elements that do not lie in the image of $G(A)$ for any proper subset $A$ of $S$. Then there is a natural map from $F'(S)$ to $G(S)$ where we send, for each subset $A$ in $S$, $F(A) \subseteq G(A)$ to $G(S)$ under the functoriality map $G(A) \to G(S)$

This map is surjective because each element either lies in the image of some proper subset or doesn't, and we can induct in the first case.

To see the map is injective, suppose that $x \in G(S)$ lies in the image of $y \in F(A) \subseteq G(A) $ and $z \in F(B)\subseteq G(B)$ for two subsets $A, B$ of $S$. If $A=B$ then we can apply a left inverse of the inclusion $A \to S$ to see that $y=z$ in $G(A)$ and so $(A,y)= (B,z)$ in $F'(S)$. If $A\neq B$, assume wlog $B \not\subset A$, and let $m$ be a left inverse of the inclusion $B \to S$ which sends $A \setminus B$ into $A \cap B$. Let $i_A$ and $i_B$ be the inclusions of $A $ and $B$ into $S$. Then by functoriality $$ G_{i_A} (y) = x = G_{i_b}(z)$$ and so $$z = G_m ( G_{i_b}(z)) = G_m( G_{i_A}(x)) = G_{m \circ i_A} (x) $$

but $m \circ i_A$ factors through the inclusion of $A \cap B$ into $B$, so $z$ lies in the image of $G(A \cap B)$ which contradicts the assumption that $z \in F(B)$. QED

This gives the formula

$$| G(n)| = \sum_{k=0}^n { n \choose k} |F(k) | $$

so if a sequence $a_n$ arises from any functor from finite sets to finite sets (and not just a monad) we must have

$$ a_n = \sum_{k=0}^n { n \choose k} b_k $$

for some sequence of natural numbers $b_k$.

Conversely, for any functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$, if $F(0)\neq 0$ and $F(1)\neq 0$ we can extend $F'$ to a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and in fact to a monad.

To do this, fix $c \in F(0)$ and thus in $F'(S)$ for all $s$, and fix $i \in F(1)$ and thus an injective natural transformation $i: S \to F'(S)$ for all $S$.

To extend $F'$ to a functor, given a map $f: S_1 \to S_2$, a subset $A\subseteq S_1$, and an element $x \in F(A)$, send $(A,x)$ to $(f(A), f(x))$ if $f$ is injective on restriction to $A$ and to $(\emptyset, c)$ otherwise. Functoriality of this is easily checked.

To extend $F'$ to a monad, our unit will be the map $i$ and our multiplication will send an element in $F'(F'(S))$ associated to a subset $A$ of $F'(S)$ and an element $x$ in $F(A)$ to, if $A$ is contained in the image of $i$, the element $(i^{-1}(A), i^{-1}(x)) \in F'(S)$, if $A$ has one element $y$ and $x=i$, the element $y \in F'(S)$, and $c$ in every other case.

The compatibility with the left and right unit come from the first two cases. The associativity is not too hard to check.

This shows a stronger functorial version of the claim that for any sequence $b_k$, as long as $b_0$ and $b_1$ are nonzero, we can find a monad with sequence $a_n$.

Also Valery showed that if $b_1$ is zero, we must have $b_0=0$ or $1$ and all higher $b_i=0$. So the main case of interest is when $b_0=0$ and $b_1$ is not zero.