How many natural operations on subsets are there?

Question

How many operations are there on subsets of a set that are compatible with images of maps? Of course, we can take unions, but are these all? Spoiler: No.

To formalize this, let $P : \mathbf{Set} \to \mathbf{Set}$ be the covariant power set functor. Let $n \in \mathbb{N}$. How many natural transformations $$P^n \to P$$ are there? Such a transformation $\alpha$ consists of an $n$-ary operation on the subsets of any set $X$, $$\alpha_X : P(X)^n \to P(X),$$ such that for all maps $f : X \to Y$ we have $$f(\alpha_X(U_1,\dotsc,U_n)) = \alpha_Y(f(U_1),\dotsc,f(U_n))$$ as subsets of $Y$. Let us call $\alpha$ just a subset operation.

For example, for every subset $T \subseteq \{1,\dotsc,n\}$ we have the $n$-ary subset operation $$(U_1,\dotsc,U_n) \mapsto \bigcup_{i \in T} U_i,$$ and one might think first that these are all.

The case $n = 0$ is easy, we have a natural subset $U_X \subseteq X$ for every set $X$ such that $f(U_X) = U_Y$ for all $f : X \to Y$. Taking $X = \emptyset$, we must have $U_X = \emptyset$, and then $U_Y = \emptyset$, for all $Y$. So this is the only solution.

The case $n = 1$ is also a good exercise. Let $\alpha : P \to P$ be a unary subset operation. Applying naturality to $i : U \hookrightarrow X$ shows $\alpha_X(U) = \alpha_U(U)$, in particular $\alpha_X(U) \subseteq U$. In particular, $\alpha_X(\emptyset) = \emptyset$. Let $\star$ be the singleton set. Then $\alpha_\star(\star)$ is either $\emptyset$ or $\star$. If it is $\emptyset$, then $\alpha_X(U) = \emptyset$ for all $U \subseteq X$: If $U = \emptyset$, this is already known. If $U \neq \emptyset$, then for the unique map $f : X \to \star$ we have $f(\alpha_X(U)) = \alpha_\star(f(U)) = \alpha_\star(\star) = \emptyset$ and hence $\alpha_X(U) = \emptyset$. Now assume $\alpha_\star(\star) = \star$. Then for $X \neq \emptyset$ we have $\alpha_X(X) \neq \emptyset$, since the unique map $f : X \to \star$ maps this to $\alpha_\star(\star) \neq \emptyset$. For all bijective maps $f : X \to X$ we have $f(\alpha_X(X)) = \alpha_X(f(X)) = \alpha_X(X)$. The only non-empty subset of $X$ that is invariant under all permutations is $X$ itself. Hence, $\alpha_X(X) = X$, and then $\alpha_X(U) = \alpha_U(U) = U$.

So there are only the two obvious unary subset operations, $\alpha(U) = \emptyset$ and $\alpha(U) = U$.

For $n = 2$ we have at least the following four subset operations: a pair of subsets $(U,V)$ is mapped to one of these: $$\emptyset, ~ U, ~ V, ~ U \cup V$$ However, there is a fifth subset operation! It is defined by $$U \cup_s V := \begin{cases} U \cup V & U \neq \emptyset \text{ and } V \neq \emptyset \\ \emptyset & U = \emptyset \text{ or } V = \emptyset \end{cases}$$ An elementary calculation shows that, indeed, $$f(U \cup_s V) = f(U) \cup_s f(V).$$ The crucial property of the image is here that $f(U) = \emptyset \iff U = \emptyset$. Notice that $\cup_s$ is associative, commutative, but it lacks a neutral element. I call $\cup_s$ the "stubborn union". It refuses to take the union when one of the sets is empty. Let me know if this already has a name.

I did not expect any other subset operation apart from the unions! But that's life, I guess (it would be better with pointed sets). Of course, you can combine this idea with the unions to generate many more subset operations for $n > 2$. For example, $(U,V,W) \mapsto U \cup ( V \cup_s W)$ is a subset operation for $n = 3$.

The exact number seems to be connected with partitions and be something like $$\sum_{k \leq n} \binom{n}{k} B_k = B_{n+1},$$ where $B_n$ is the Bell number, but I am not sure. Apparently for the the counting we also need to understand the compatibility conditions between $\cup_s$ and $\cup$ (if there are any), that is, the operad structure on $\hom(P^\bullet,P)$.

For this question, let me only focus on $n = 2$ though.

Question. Are the five operations described above the only binary subset operations?

Here is what I have tried. Let $\alpha : P^2 \to P$ be a binary subset operation. We have $\alpha(U,V) \subseteq U \cup V$. We can define three unary subset operations from it, by mapping $U$ either to $\alpha(U,\emptyset)$, $\alpha(\emptyset,U)$, or $\alpha(U,U)$. Now use the already known classification of unary subset operations. Let's look for example at the case that $\alpha(U,\emptyset) = \emptyset$ and $\alpha(\emptyset,U) = U$ hold, for all $U \subseteq X$. Now the case $\alpha(U,U) = \emptyset$ is easy to deal with, you can quite easily deduce $\alpha(U,V) = \emptyset$ by using the unique map $X \to \star$. The harder case is $\alpha(U,U) = U$ for all $U$. How can I then verify that $\alpha(U,V) = U \cup_s V$? Or is there even another operation that I missed? It suffices to consider subsets of $\{0,1\}$ (apply naturality to maps $X \to \{0,1\}$). So we only need to calculate $\alpha(\{0\},\{0,1\}$) and $\alpha(\{0\},\{1\})$, but how is that possible?

And this is only one of the cases! I also don't know how to proceed with the case $\alpha(U,\emptyset) = U$, $\alpha(\emptyset,U)=U$. Of course we would be done if $\alpha$ was monotonic in both of its arguments, but there is no a priori reason for this!

It is worthwile mentioning that the contravariant version is much easier to handle, since the contravariant power set functor is a representable functor, so that Yoneda kicks in. Our functor $P$ however is very far from being representable. This makes the question so interesting.

Answer 1

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 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.

Answer 2

In a comment Peter LeFanu Lumsdaine has conjectured a classification, which shows that there are $16$ (!) binary subset operations. They can be combined from $1 \cdot 2 \cdot 2 \cdot 4$ independent cases. For reference, let me write them down:

• $\alpha(\emptyset,\emptyset)$ must be $\emptyset$

• For non-empty sets $U$, $\alpha(U,\emptyset)$ can be one of $\emptyset$, $U$

• For non-empty sets $V$, $\alpha(\emptyset,V)$ can be one of $\emptyset$, $V$

• For non-empty sets $U,V$, $\alpha(U,V)$ can be one of $\emptyset, U, V, U \cup V$.

Update. According to the now proven classification in terms of deflationary maps, let me also mention the corresponding $16$ deflationary maps $M : P([2]) \to P([2])$:

• $M(\emptyset)$ must be $\emptyset$
• $M(\{1\})$ can be one of $\emptyset, \{1\}$
• $M(\{2\})$ can be one of $\emptyset, \{2\}$
• $M(\{1,2\})$ can be one of $\emptyset, \{1\}, \{2\}, \{1,2\}$

Answer 3

In the comments, Tobias Fritz suggested to look at the subfunctor $P' \subseteq P$ of non-empty subsets. Here the classification is much easier: Every operation $(P')^n \to P'$ is of the form $(U_1,\dotsc,U_n) \to \bigcup_{i \in T} U_i$ for a non-empty subset $T \subseteq [n]$. Hence their amount is $2^{n} - 1$.

Proof. Let $\alpha : (P')^n \to P'$ be an operation. Let $T := \alpha_{[n]}(\{1\},\dotsc,\{n\})$, this is a non-empty subset of $[n]$. Let $X$ be a set with subsets $U_1,\dotsc,U_n \subseteq X$. If $\pi : U_1 + \cdots + U_n \to X$ is the projection from the disjoint union, then $\alpha_X(U_1,\dotsc,U_n) = \alpha_{U_1 + \cdots + U_n}(U_1,\dotsc,U_n)$, and therefore we may as well assume $X = U_1 + \cdots + U_n$. The subset $A := \alpha_X(U_1,\dotsc,U_n)$ is invariant under the action of $S_{U_1} \times \cdots \times S_{U_n}$ on $U_1 + \cdots + U_n$. Hence, it has the form $\bigcup_{i \in J} U_i$ for some set $J \subseteq [n]$. If $f : X \to [n]$ is the "index projection", we have on the one hand $f(A) = J$, on the other hand $f(A) = \alpha_{[n]}(f(U_1),\dotsc,f(U_n)) = \alpha_{[n]}(\{1\},\dotsc,\{n\}) = T$, and we are done. $\checkmark$

PS: One can also show in a similar fashion (but with more effort, and extra care when $K = \mathbb{F}_2$) that for the (covariant) functor $\mathrm{Sub} : \mathbf{Vect}_K \to \mathbf{Set}$ of subspaces there $2^n$ operations $\mathrm{Sub}^n \to \mathrm{Sub}$.