# Pullbacks and the power set functor

I have a very stupid question, so sorry in advance. I want to show that a power set functor $2^{-} : (Sets) \rightarrow (Sets)$ does not preserves pullbacks by a counterexample. Here is my logic: we know how to construct pullbacks in $(Sets)$, so suppose $X = \{a,b,c\},\ Y = \{a,b\},\ Z = \{a\}$ and $f:X \rightarrow Z$ is such that $f(x) = a$ and $g:Y \rightarrow Z$ is such that $g(y) = a$. Now the pullback object is $D = \{(x,y) \in X \times Y: f(x)=g(y)\}= X \times Y$. $|X \times Y|=6$, so $|2^{X \times Y}| = 64$.

Now consider $2^{X} = \{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$, $2^{Y} = \{ \emptyset, \{a\},\{b\}, \{a,b\} \}$ and $2^Z = \{ \emptyset, \{a\}\}$. Note that $2^{f}(\emptyset) = \emptyset$ and $2^{f}(X') = \{a\}$, where $X'$ is a nonempty subset of $X$, and we have the same rule for $2^{g}$ respectively. The pullback $D$ of these guys is $\{ (X',Y'): X' \subset X,\ Y' \subset Y,\ 2^{f}(X') = 2^{g}(Y')\}$. But $2^{f}(\emptyset) \neq 2^{g}(Y')$ for a nonempty $Y'$, so the pullback object will contain $22$ elements, which is less that $64$.

Could you please clarify, does it work?

-
Seems fine to me. – Thomas Belulovich Dec 17 '13 at 7:47
@ThomasBelulovich Yes, it seems fine, but I was confused with the argument about empty sets ($2^f(\emptyset) = \emptyset$). – user116307 Dec 17 '13 at 7:51
The argument that $2^f(\emptyset) = \emptyset$ is correct. Is there something particular about it that feels weird? – Thomas Belulovich Dec 17 '13 at 7:57

This works. In fact, in general if you are looking at the pullback $\lim D$ of $D = (X \to * \gets Y)$ (where $*$ is the terminal object in Sets), and $\mathcal{P}$ denotes the power set functor, then

$$\mathcal{P}(\lim(D)) \to \lim \mathcal{P}_* D$$

will generally not be an isomorphism. If $X$ and $Y$ are finite, then $|\mathcal{P}(\lim(D))| = 2^{|X| |Y|}$ as you indicated. Meanwhile, the pullback of $\mathcal{P}_* D$ breaks into two fibers over $\mathcal{P}(*) = \{\emptyset, \{*\}\}$.

The lone point in fiber over $\emptyset$ comes from choosing $\emptyset \subset X$ and $\emptyset \subset Y$.

Each point in the fiber over $\{*\}$ comes from choosing a nonempty subset of each of $X$ and $Y$. There are $(2^{|X|}-1)(2^{|Y|}-1)$ ways of doing this.

So you get $1 + (2^{|X|}-1)(2^{|Y|}-1)$ elements in the pullback of $\mathcal{P}_* D$.

(There are more sophisticated ways of getting at this, even when $X,Y,Z$ are not finite, as well)

-
With $\mathcal{P}_* D$ you mean the functor composition of $\mathcal{P}$ and $D$? – magma Dec 17 '13 at 13:57
Yes, by $\mathcal{P}_*D$ I mean the diagram $\mathcal{P}(X) \to \mathcal{P}(*) \gets \mathcal{P}(Y)$. – Thomas Belulovich Dec 17 '13 at 23:56