Timeline for How many natural operations on subsets are there?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27 at 16:12 | answer | added | Martin Brandenburg | timeline score: 9 | |
| Sep 27 at 14:51 | vote | accept | Martin Brandenburg | ||
| Sep 27 at 11:40 | answer | added | Peter LeFanu Lumsdaine | timeline score: 32 | |
| Sep 27 at 11:32 | history | became hot network question | |||
| Sep 27 at 11:31 | answer | added | Martin Brandenburg | timeline score: 11 | |
| Sep 27 at 10:51 | comment | added | Peter LeFanu Lumsdaine | In particular, for $n=2$, this tells us that there are at least 16 operations (exactly 16 if the conjecture is correct), including non-monotonic ones such as: $\mu(U,V)$ is $V$ if $U = \emptyset$, and $\emptyset$ otherwise. | |
| Sep 27 at 10:40 | comment | added | Peter LeFanu Lumsdaine | Here is a conjectural classification: Operations $\tau : P(X)^n \to P(X)$ correspond to maps $M : P([n]) \to P([n])$ that are deflationary, i.e. $Ma \subseteq a$. A deflationary map $M$ induces an operation $\varphi_M$ by taking $\phi_M(X_1,\ldots,X_n) = \bigcup_{i \in M(\{ j \mid X_j \neq \emptyset\})} X_i$. Conversely, an operation $\tau$ induces a map $D_\tau $ by sending $a \in P([n])$ to $\tau(a \cap \{1\}, a \cap \{2\}, \ldots)$, deflationary by naturality. Certainly $D_(\phi_M) = D$; I hope naturality should imply $\phi_(D_\tau) = \tau$, but I don’t have time to finish the job now… | |
| Sep 27 at 10:25 | comment | added | Zhen Lin | Ah, I see where Tobias Fritz's decomposition comes from too: because of the natural augmentation $P (X) \to P (1)$, we can think of everything happening not in $\textbf{Set}$ but rather $\textbf{Set}_{/ P(1)}$. The fibre over $\bot$ is, of course, the constant $\{ \emptyset \}$ functor and the fibre over $\top$ is the inhabited subset functor. But there are fewer natural transformations $P^n \Rightarrow P$ if we require compatibility with the augmentation. | |
| Sep 27 at 10:06 | comment | added | Zhen Lin | It occurs to me that having $P (1)$ around means there are at least $P (1)^{P (1)^n}$ distinct $(n + 1)$-ary operations: for the first $n$ variables, map each one down to $P (1)$, apply an arbitrary $n$-ary operation on them, then combine it with the last variable by "scalar multiplication". This means it grows at least as fast as $2^{2^{n-1}}$...! | |
| Sep 27 at 9:59 | comment | added | Ivan Di Liberti | I think there may be some chance to establish a connection between natural transformation between $P^n \Rightarrow P$ and natural transformation between $n \times (-)$ and $(-)$. That's because in some informal (!) sense $P$ is representable. | |
| Sep 27 at 9:58 | comment | added | Martin Brandenburg | @GabrielC.Drummond-Cole Oh there are (at least) seven binary subset operations then! Good catch. Still wondering how to prove that these are all. | |
| Sep 27 at 9:48 | comment | added | Zhen Lin | It might be helpful to think of the linear/additive analogue of this: we are dealing with not merely a module but one with equipped with a homomorphism to the base ring. This extra gadget enriches the available natural operations. | |
| Sep 27 at 9:45 | comment | added | Zhen Lin | I think the "stubborn" operations can be understood constructively in terms of the natural map $P (X) \to P (1)$ and mixed operations $P (X)^n \times P (1)^m \to P (X)$. For example, there is a natural mixed operation $P (X) \times P (1) \to P (X)$ sending $(U, \phi)$ to $\{ x \in X : x \in U \text{ and } \phi \}$, where we conflate subsets of $1$ with constant truth values. This accounts for both the natural unary operations you have already found, since the elements of $P (1)$ can be considered constants, as well as the "stubborn" union and "stubborn" projections already mentioned. | |
| Sep 27 at 6:54 | comment | added | Andrej Bauer | Can we use some parametricity magic from functional programming to answer the question? | |
| Sep 27 at 6:12 | comment | added | Tobias Fritz | I think it should help to write $P$ as the coproduct of the terminal functor and the nonempty power set functor $P'$ defined by $P'(X) = P(X) \setminus \{\emptyset\}$. The stubborn operations seem to be induced by this decomposition. Have you thought about using this yet? It seems plausible that the natural operations on $P'$ are only the unions, but I'm not sure how to go about a proof. | |
| Sep 27 at 4:08 | comment | added | Gabriel C. Drummond-Cole | $\alpha$ determines and is determined by determined by $\alpha(U,\emptyset)$ and $\alpha(\emptyset,V)$, and $\alpha(U, V)$ where $U$ and $V$ range over nonempty subsets of $X$. Are there any naturality constraints connecting these three systems? To me it looks like any independent combination of choices for these three yields a subset operation. E.g. the "stubborn projection" $\alpha(U,V) = U$ unless $V=\emptyset$ in which case it is $\emptyset$. Do I misunderstand? | |
| Sep 27 at 2:38 | history | edited | Martin Brandenburg | CC BY-SA 4.0 |
added 6 characters in body
|
| Sep 27 at 2:26 | history | edited | Martin Brandenburg | CC BY-SA 4.0 |
added 243 characters in body
|
| Sep 27 at 2:19 | history | edited | Martin Brandenburg | CC BY-SA 4.0 |
added 243 characters in body
|
| Sep 27 at 0:09 | comment | added | Martin Brandenburg | Because the maps are not necessarily injective. | |
| Sep 27 at 0:08 | comment | added | Sam Hopkins | Probably stupid question: why doesn't intersection work? | |
| Sep 27 at 0:00 | history | asked | Martin Brandenburg | CC BY-SA 4.0 |