4
$\begingroup$

Let $\mathbf{Set}$ be a category of set, and $\mathcal{P}:\mathbf{Set} \to \mathbf{Set}$ be a power set functor defined as $$ \mathcal{P}(X) = 2^{X} = \{U\subseteq X\} $$ and for any function $f:X\to Y$, $$ \mathcal{P}(f): \mathcal{P}(X) \to \mathcal{P}(Y), \quad \mathcal{P}(f)(U) = f(U). $$ It is not hard to show that this really defines a functor. My question is:

Let $\mathcal{F}:\mathbf{Set}\to \mathbf{Set}$ be a functor that satisfies $\mathcal{F}(X) = \mathcal{P}(X)$ for all set $X$. Does this imply that $\mathcal{F} = \mathcal{P}$? i.e. $\mathcal{F}(f) =\mathcal{P}(f)$ for all morphisms (functions) $f$?

I believe that this is true, but I have no idea about proof. This question is motivated from the functional programming, especially about list functor (in Haskell). This is the question that I posted on Haskell reddit. My strategy is that, if one can show that the above statement is true, then we can modify the proof to give an answer to the original question about list functor. Maybe one can try to show for the category of finite sets or countable sets.

$\endgroup$
5
  • 1
    $\begingroup$ @QiaochuYuan Isn't it fail to satisfy $\mathcal{F}(\mathrm{id}_{X}) = \mathrm{id}_{\mathcal{F}(X)}$? $\endgroup$
    – Seewoo Lee
    Sep 28, 2019 at 7:17
  • $\begingroup$ Oh, yes, you’re right. $\endgroup$ Sep 28, 2019 at 7:18
  • $\begingroup$ For finite sets there is a counterexample not yet mentioned: let $f:X\rightarrow Y$ be a function; define $Ff:P(X) \rightarrow P(Y)$ by $Ff(U) = \{y\in Y : |f^{-1}(y)| \text{ is odd}\}$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however. $\endgroup$ Sep 28, 2019 at 22:34
  • $\begingroup$ I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341. $\endgroup$
    – ComFreek
    Sep 29, 2019 at 8:10
  • $\begingroup$ @MiloBrandt Does your functor fulfill $Fid_X = id_{FX}$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$). $\endgroup$
    – ComFreek
    Sep 29, 2019 at 8:32

2 Answers 2

10
$\begingroup$

There exists at least one other endofunctor of $\mathbf{Set}$ that sends every set to its powerset. This endofunctor sends a function $f:X\to Y$ to $$\widehat{f} :P(X)\to P(Y):U\mapsto \widehat{f}(U)=\{y\in Y\mid f^{-1}(\{y\})\subset U\}$$ (where $f^{-1}$ is the inverse image).

One can check directly that $\widehat{f\circ g}=\widehat{f}\circ \widehat{g}$ and $\widehat{id_X}=id_{P(X)}$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^{-1}$ and $\widehat{f}$ are all monotone functions and we have two adjunctions $P(f)\dashv f^{-1}\dashv \widehat{f}$. Then, for any $g$ we have a chain of adjunctions $$P(f\circ g)\dashv (f\circ g)^{-1}\dashv \widehat{f\circ g}$$ and since adjunctions can be composed, we also have $$P(f)\circ P( g)\dashv g^{-1} \circ f^{-1}\dashv \widehat{f}\circ \widehat{g}$$

Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $\widehat{f\circ g}=\widehat{f}\circ \widehat{g}$. You can use a similar argument for the identities.

$\endgroup$
3
  • 1
    $\begingroup$ Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $\mathcal{P}$. Yours isn't, I guess. $\endgroup$
    – ComFreek
    Sep 28, 2019 at 8:48
  • $\begingroup$ @ComFreek That’s an interesting question...anyway thank you for a good counterexample! $\endgroup$
    – Seewoo Lee
    Sep 28, 2019 at 13:45
  • 2
    $\begingroup$ This map is also known as $\hat f(U) = Y\setminus f(X\setminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor! $\endgroup$ Sep 28, 2019 at 22:49
5
$\begingroup$

Here's a class of counter-examples:

For each set $X$ choose a bijection $r_X\colon \mathcal P(X)\to\mathcal P(X)$. Now let your functor $\mathcal F$ be defined on morphisms $f\colon X\to Y$ by $$ \mathcal F(f) = r_Y\circ \mathcal P(f) \circ r_X^{-1}. $$ You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=X\setminus U$, then $\mathcal Ff(U) = Y\setminus f(X\setminus U)$.

$\endgroup$
1
  • 2
    $\begingroup$ Indeed every such functor $\mathcal{F}$ is naturally isomorphic to $\mathcal{P}$: $$\require{AMScd} \begin{CD} \mathcal{P}(X) @>{r_X}>> \mathcal{P}(X)\\ @V{\mathcal{P}f}VV @VV{\mathcal{F}f = r_y\ \circ\ \mathcal{P}f\ \circ\ r_X^{-1}}V \\ \mathcal{P}(Y) @>{r_Y}>> \mathcal{P}(Y). \end{CD}$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $\mathcal{P}$ is a special case for $\forall X. r_X := id_X$.) $\endgroup$
    – ComFreek
    Sep 28, 2019 at 8:40

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .