Return to Answer

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ will meet the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$.(*) So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

Zhen Lin asks in comments: How constructive is this? The counting of deflationary maps certainly requires LEM; but the correspondence between natural operations $P(-)^n \to P$ and deflationary maps on $P([n])$ turns out to be entirely constructive. The one non-constructive step in the argument above is (); constructively this point is a bit harder, so I’m leaving the classical version above and giving the constructive version here. In the unary case, we essentially need to show: for any natural $\tau : P(-) \to P(-)$, if $P_X(X)$ is inhabited, then $P_X(X) = X$. I’ll just show this case; the $n$-ary version needed at () is similar.

Classically, Martin argues this in the question: by naturality, $P_X(X)$ must be invariant under all permutations of $X$, and the only inhabited invariant subset is $X$ itself. Constructively, we can’t construct transpositions on an arbitrary set $X$ to make that second step — but by several appeals to naturality, we can reduce it back to the case of a discrete set, where we the classical argument does work:

• By naturality along $X \to 1$, $\tau_1(1) = 1$.
• By naturality along $Y \to 1$, $\tau_Y(Y)$ is inhabited for any inhabited $Y$.
• In particular, $\tau_2(2)$ is inhabited — and since 2 has decidable equality, the its only permutation-invariant inhabited subset is 2, so $\tau_2(2) = 2$.
• So for any coproduct of inhabited sets $Y+Z$, naturality along $Y+Z \to 1+1=2$ shows that $\tau_{Y+Z}(Y+Z)$ must meet both summands. In particular, $\tau_{Y+1}(Y+1)$ must include the adjoined point.
• Now going back to the original $X$, for any $x \in X$, naturality along $[1_X,x] : X+1 \to X$ shows that $x \in \tau_X(X)$; so $\tau_X(X) = X$ as desired.

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ will meet the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$  (*). So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

Zhen Lin asks in comments: How constructive is this? The counting of deflationary maps certainly requires LEM; but the correspondence between natural operations $P(-)^n \to P$ and deflationary maps on $P([n])$ turns out to be entirely constructive. The one non-constructive step in the argument above is (*); constructively this point is a bit harder, so I’m leaving the classical version above and giving the constructive version here. In the unary case, we essentially need to show: for any natural $\tau : P(-) \to P(-)$, if $P_X(X)$ is inhabited, then $P_X(X) = X$. I’ll just show this case; the $n$-ary version needed at (*) is similar.

Classically, Martin argues this in the question: by naturality, $P_X(X)$ must be invariant under all permutations of $X$, and the only inhabited invariant subset is $X$ itself. Constructively, we can’t construct transpositions on an arbitrary set $X$ to make that second step — but by several appeals to naturality, we can reduce it back to the case of a discrete set, where the classical argument does work:

• By naturality along $X \to 1$, $\tau_1(1) = 1$.
• By naturality along $Y \to 1$, $\tau_Y(Y)$ is inhabited for any inhabited $Y$.
• In particular, $\tau_2(2)$ is inhabited — and since $2$ has decidable equality, its only permutation-invariant inhabited subset is $2$, so $\tau_2(2) = 2$.
• So for any coproduct of inhabited sets $Y+Z$, naturality along $Y+Z \to 1+1=2$ shows that $\tau_{Y+Z}(Y+Z)$ must meet both summands. In particular, $\tau_{Y+1}(Y+1)$ must include the adjoined point.
• Now going back to the original $X$, for any $x \in X$, naturality along $[1_X,x] : X+1 \to X$ shows that $x \in \tau_X(X)$; so $\tau_X(X) = X$ as desired.

Here is a classification: Natural operations $\tau : P(-)^n \to P(-)$ correspond to maps $M : P([n]) \to P([n])$ that are deflationary, i.e. $M a \subseteq a$ for each $a$.

A deflationary map $M$ on $P([n])$ induces an operation $\varphi_M : P(X)^n \to P(X)$ by taking $\varphi_M(U_1,\ldots,U_n) = \bigcup_{i \in M(\{ j | U_j \neq \emptyset \})} U_i$. Conversely, a natural operation $\tau$ induces a map $D_\tau : P([n]) \to P([n])$ by sending $a \in P([n])$ to $\tau(a \cap \{1\}, a \cap \{2\}, \ldots)$. This is deflationary by naturality: for each $a \in P([n])$, the tuple $(a \cap \{1\},\ldots)$ is in the image of $P(a)^n \hookrightarrow P([n])^n$, and so its image under $\tau$ is in the image of $P(a) \hookrightarrow P([n])$.

Now certainly for any deflationary map $M$, $D_{\varphi_M} = M$ (by direct calculation). Conversely, for any natural operation $\tau : P(-)^n \to P(-)$, naturality implies that $\varphi_{D_\tau} = \tau$ as follows: Given $U_1,\ldots,U_n \subseteq X$, write $a = \{ i \in [n] \mid U_i \neq \emptyset \}$, and $\vec a = (a \cap \{1\}, \ldots, a \cap \{n\}) \in P([n])^n$. We need to show that $\tau(U_1,\ldots,U_n) = \bigcup_{i \in \tau(\vec a)} U_i$.

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ must have non-intersection with the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$. So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

This proves the claimed correspondence between natural $n$-ary operations and deflationary maps on $P([n])$. For counting, a little calculation shows that there are $2^{n2^{n-1}}$ such maps.

This correspondence also restricts to a monotone version: an operation will be monotone precisely when its corresponding deflationary map is.

Here is a classification: Natural operations $\tau : P(-)^n \to P(-)$ correspond to maps $M : P([n]) \to P([n])$ that are deflationary, i.e. $M a \subseteq a$ for each $a$.

A deflationary map $M$ on $P([n])$ induces an operation $\varphi_M : P(X)^n \to P(X)$ by taking $\varphi_M(U_1,\ldots,U_n) = \bigcup_{i \in M(\{ j | U_j\, \text{inhabited} \})} U_i$. Conversely, a natural operation $\tau$ induces a map $D_\tau : P([n]) \to P([n])$ by sending $a \in P([n])$ to $\tau(a \cap \{1\}, a \cap \{2\}, \ldots)$. This is deflationary by naturality: for each $a \in P([n])$, the tuple $(a \cap \{1\},\ldots)$ is in the image of $P(a)^n \hookrightarrow P([n])^n$, and so its image under $\tau$ is in the image of $P(a) \hookrightarrow P([n])$.

Now certainly for any deflationary map $M$, $D_{\varphi_M} = M$ (by direct calculation). Conversely, for any natural operation $\tau : P(-)^n \to P(-)$, naturality implies that $\varphi_{D_\tau} = \tau$ as follows: Given $U_1,\ldots,U_n \subseteq X$, write $a = \{ i \in [n] \mid U_i\, \text{inhabited} \}$, and $\vec a = (a \cap \{1\}, \ldots, a \cap \{n\}) \in P([n])^n$. We need to show that $\tau(U_1,\ldots,U_n) = \bigcup_{i \in \tau(\vec a)} U_i$.

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ will meet the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$.(*) So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

This proves the claimed correspondence between natural $n$-ary operations and deflationary maps on $P([n])$. For counting, a little calculation shows that there are $2^{n2^{n-1}}$ such maps.

This correspondence also restricts to a monotone version: an operation will be monotone precisely when its corresponding deflationary map is.

Zhen Lin asks in comments: How constructive is this? The counting of deflationary maps certainly requires LEM; but the correspondence between natural operations $P(-)^n \to P$ and deflationary maps on $P([n])$ turns out to be entirely constructive. The one non-constructive step in the argument above is (); constructively this point is a bit harder, so I’m leaving the classical version above and giving the constructive version here. In the unary case, we essentially need to show: for any natural $\tau : P(-) \to P(-)$, if $P_X(X)$ is inhabited, then $P_X(X) = X$. I’ll just show this case; the $n$-ary version needed at () is similar.

Classically, Martin argues this in the question: by naturality, $P_X(X)$ must be invariant under all permutations of $X$, and the only inhabited invariant subset is $X$ itself. Constructively, we can’t construct transpositions on an arbitrary set $X$ to make that second step — but by several appeals to naturality, we can reduce it back to the case of a discrete set, where we the classical argument does work:

• By naturality along $X \to 1$, $\tau_1(1) = 1$.
• By naturality along $Y \to 1$, $\tau_Y(Y)$ is inhabited for any inhabited $Y$.
• In particular, $\tau_2(2)$ is inhabited — and since 2 has decidable equality, the its only permutation-invariant inhabited subset is 2, so $\tau_2(2) = 2$.
• So for any coproduct of inhabited sets $Y+Z$, naturality along $Y+Z \to 1+1=2$ shows that $\tau_{Y+Z}(Y+Z)$ must meet both summands. In particular, $\tau_{Y+1}(Y+1)$ must include the adjoined point.
• Now going back to the original $X$, for any $x \in X$, naturality along $[1_X,x] : X+1 \to X$ shows that $x \in \tau_X(X)$; so $\tau_X(X) = X$ as desired.

Here is a classification: Natural operations $\tau : P(-)^n \to P(-)$ correspond to maps $M : P([n]) \to P([n])$ that are deflationary, i.e. $M a \subseteq a$ for each $a$.

A deflationary map $M$ on $P([n])$ induces an operation $\varphi_M : P(X)^n \to P(X)$ by taking $\varphi_M(U_1,\ldots,U_n) = \bigcup_{i \in M(\{ j | U_j \neq \emptyset \})} U_i$. Conversely, a natural operation $\tau$ induces a map $D_\tau : P([n]) \to P([n])$ by sending $a \in P([n])$ to $\tau(a \cap \{1\}, a \cap \{2\}, \ldots)$. This is deflationary by naturality: for each $a \in P([n])$, the tuple $(a \cap \{1\},\ldots)$ is in the image of $P(a)^n \hookrightarrow P([n])^n$, and so its image under $\tau$ is in the image of $P(a) \hookrightarrow P([n])$.

Now certainly for any deflationary map $M$, $D_{\varphi_M} = M$ (by direct calculation). Conversely, for any natural operation $\tau : P(-)^n \to P(-)$, naturality implies that $\varphi_{D_\tau} = \tau$ as follows: Given $U_1,\ldots,U_n \subseteq X$, write $a = \{ i \in [n] \mid U_i \neq \emptyset \}$, and $\vec a = (a \cap \{1\}, \ldots, a \cap \{n\}) \in P([n])^n$. We need to show that $\tau(U_1,\ldots,U_n) = \bigcup_{i \in \tau(\vec a)} U_i$.

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ must have non-intersection with the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$. So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

This proves the claimed correspondence between natural $n$-ary operations and deflationary maps on $P([n])$. For counting, a little calculation shows that there are $2^{n2^{n-1}}$ such maps.

This correspondence also restricts to a monotone version: an operation will be monotone precisely when its corresponding deflationary map is.

Here is a classification: Natural operations $\tau : P(-)^n \to P(-)$ correspond to maps $M : P([n]) \to P([n])$ that are deflationary, i.e. $M a \subseteq a$ for each $a$.

A deflationary map $M$ on $P([n])$ induces an operation $\varphi_M : P(X)^n \to P(X)$ by taking $\varphi_M(U_1,\ldots,U_n) = \bigcup_{i \in M(\{ j | U_j \neq \emptyset \})} U_i$. Conversely, a natural operation $\tau$ induces a map $D_\tau : P([n]) \to P([n])$ by sending $a \in P([n])$ to $\tau(a \cap \{1\}, a \cap \{2\}, \ldots)$. This is deflationary by naturality: for each $a \in P([n])$, the tuple $(a \cap \{1\},\ldots)$ is in the image of $P(a)^n \hookrightarrow P([n])^n$, and so its image under $\tau$ is in the image of $P(a) \hookrightarrow P([n])$.

Now certainly for any deflationary map $M$, $D_{\varphi_M} = M$ (by direct calculation). Conversely, for any natural operation $\tau : P(-)^n \to P(-)$, naturality implies that $\varphi_{D_\tau} = \tau$ as follows: Given $U_1,\ldots,U_n \subseteq X$, write $a = \{ i \in [n] \mid U_i \neq \emptyset \}$, and $\vec a = (a \cap \{1\}, \ldots, a \cap \{n\}) \in P([n])^n$. We need to show that $\tau(U_1,\ldots,U_n) = \bigcup_{i \in \tau(\vec a)} U_i$.

Take the disjoint sum $U = \coprod_i U_i = \{ (i,x) \mid i \in [n],\, x \in U_i\}$, with natural maps $U \to [n]$ and $U \to X$ given by first and second projections. Write $\vec U$ for $(\{1\} \times U_1,\ldots, \{n\} \times U_n) \in P(U)^n$. Now the image of $\vec U$ under first projection $P(U)^n \to P([n])^n$ is exactly the set $\vec a$ from above; so the image of $\tau(\vec U)$ under $P(U) \to P([n])$ must be exactly $\tau(\vec a)$. So $\tau(\vec U) \in P(U)$ must have non-intersection with the summand $\{i\} \times U_i$ precisely when $i \in \tau(\vec a)$. Moreover, in that case, it must contain the whole summand, by naturality under all permutations of $U_i$. So $\tau(\vec U)$ consists precisely of the union of all summands $\{i\} \times U_i$ for $i \in \tau(\vec a)$. So now by naturality under the map $U \to X$, we get that $\tau(U_1,\ldots,U_n)$ is the union of these $U_i$, as required.

This proves the claimed correspondence between natural $n$-ary operations and deflationary maps on $P([n])$. For counting, a little calculation shows that there are $2^{n2^{n-1}}$ such maps.

This correspondence also restricts to a monotone version: an operation will be monotone precisely when its corresponding deflationary map is.