Prove that the functor $P : \text{Set}^\text{op} → \text{Set}$ , $F(f)=f^{-1}:P(Y)\rightarrow P(X)$ for $f: X \rightarrow Y$ is representable

Question

Let $P(A)$ denote the power set of a set $A$

For a map $f : X \mapsto Y$ of sets, I can define a map $P( f ): P(Y) → P(X)$ s.t that I obtain a functor $P : \text{Set}^\text{op} \to \text{Set}$ in the following way:

$F(f)=f^{-1}:P(Y)\rightarrow P(X)$ for $f: X \rightarrow Y$ a set-theoretic map, where $f^{-1}$ is the preimage mapping.

$F(X)=P(X) , \forall X \in \text{Obj(Set)}$

How can I prove that P is representable and find the representing object?

So by definition of representability, I want to find and set $R$,

s.t. $h_R=\text{Hom}_\text{Set}(-,R)\cong P$

i.e. s.t. $h_R(X)=\text{Hom}_\text{Set}(X,R)\cong P(X)$, for all $X \in \text{Set}$

On the other hand Yoneda lemma tells me that:

$\text{Hom}_\text{Set^}(h_X,P)\cong P(X)$, for all $X \in \text{Set}$

But I don't know how this helps. Any help is appreciated

Answer 1

Let $2=\{0,1\}$, the two-element set. The claim is that $P$ is represented by $2$. We need to prove that there is a natural isomorphism $P \Rightarrow \mathsf{Hom}_{\mathsf{Set}}(-,2) $. This isomorphism is defined by the correspondence that maps a subset $Y$ of $X$ to its characteristic function $\chi_Y: X \to 2$. (Try to find its inverse). Naturality means that for any function $f: X \to A$, if $\chi_B$ is the characteristic function of $B \subseteq A$, then $\chi_B \circ f$ is the characteristic function of $f^{-1}(B) \subseteq X$, that is that the following commutes:

$$ \require{AMScd} \begin{CD} P(A) @>{}>> \mathsf{Hom}_{\mathsf{Set}}(A,2) \\ @V {f^{-1}} VV @VV{- \circ f }V \\ P(X) @>>{}> \mathsf{Hom}_{\mathsf{Set}}(X,2) \end{CD} $$

Hope it helps.

Answer 2

The first check you should do to see if a functor is representable is whether is preserves limits. Since $P : \mathsf{Set}^\text{op} \to \mathsf{Set}$, that means we want to show $P$ sends limits in $\mathsf{Set}^\text{op}$ to limits in $\mathsf{Set}$. That is, $P$ should send colimits in $\mathsf{Set}$ to limits in $\mathsf{Set}$.

As a special case of this fact, can you show $P(A \sqcup B) = P(A) \times P(B)$? That is, that the powerset of a disjoint union is (in natural bijection with) the product of the powersets?

This is some evidence that the functor is representable at all. But now, how do we go about finding the representing object? One way is to try and guess it directly. We want to write the powerset $P(X)$ as a homset $\mathsf{Set}(X,R)$ for a representing object $R$. Since sets are determined by their cardinality (up to isomorphism), let's do some examples and see if we can spot a pattern!

If $|X| = 0$, then $|P(X)| = 1$. If $|X| = 2$, then $|P(X)| = 2$. In general, you probably know that if $|X| = \alpha$ then $|P(X)| = 2^\alpha$. So, with this in mind, we want to find a set $R$ so that $|\text{Hom}(X,R)| = 2^{|X|}$. If you remember some combinatorics, this says you should take $|R| = 2$.

Can you show that $R = \{ \top, \bot \}$ works as the representing object?

---

Another angle is to try and find a universal element. If $R$ represents $P$, then $\mathsf{Set}(R,R) \cong P(R)$ and the image of $\text{id}_R$ under this isomorphism is a universal element of $P$. Call it $\xi \in P(R)$. This means that every element of $P(X)$ is the preimage of $\xi$ under a unique map $f : X \to R$.

Said this way, we want to find a set with a distinguished subset, so that every subset is a preimage of this one. Since we know what the answer should be from the previous discussion, I'll say that the subset in question is $\{ \top \} \in P(\{\top, \bot\})$.

After all, if $A \in P(X)$ is any subset of $X$, then write $\mathbb{1}_A(x) = \begin{cases} \top & x \in A \\ \bot & x \not \in A \end{cases}$ for the indicator function of $A$. (Note $\mathbb{1}_A \in \mathsf{Set}(X, \{ \top, \bot \})$). It's not hard to see that $A = \mathbb{1}_A^{-1}( \{ \top \} )$ is the preimage of the universal subset under this map.

---

Lastly, you might ask about "automating" this process. Is there a way to always find the representing object given a representable functor? Eventually this kind of thing becomes "easy to see", after you've worked with enough exmaples, but in general it can be hard to explicitly get your hands on a representing object if you merely know that one exists. For instance, many moduli spaces are defined as representing objects for certain functors, but investigating their geometry explicitly can be quite challenging. Ironically, this is one place where the category theory can be quite helpful, by giving a way to show that functors are representable without necessarily needing to find the representing object! See an old blog post of mine here for more about that.

---

I hope this helps ^_^

Answer 3

On the specific question of how you could discover a candidate for a representing object without guessing:

Note that if we have an isomorphism of functors $P \simeq h_R$, then in particular we get a bijection $P(\{ * \}) \simeq h_R(\{ * \})$ where $\{ * \}$ is a one-element set. On the other hand, $h_R(\{ * \}) = \operatorname{Hom}_{\mathsf{Set}^{op}}(R, \{ * \}) = \operatorname{Hom}_{\mathsf{Set}}(\{ * \}, R)$ is bijective to $R$. Therefore, we would get $R$ bijective to $P(\{ * \}) = \{ \emptyset, \{ * \} \}$. In other words, the representing object $R$ must be some two-element set.

Once you have this information, you can then use Yoneda's lemma to observe that giving a morphism of functors $\alpha : h_\Omega \to P$ is equivalent to giving an element $\Omega_0 \in P(\Omega)$ where we set $\Omega$ to be the particular two-element set $\{ true, false \}$. Furthermore, the proof of Yoneda's lemma gives that once you have chosen the element $\Omega_0$, the corresponding functor $\alpha : h_\Omega \to P$ is given by $\alpha_X : h_\Omega(X) \to P(X)$, $f \in h_\Omega(X) = \operatorname{Hom}(X, \Omega) \mapsto f^{-1}(\Omega_0)$. Finally, you know that $\alpha$ is an isomorphism of functors if and only if $\alpha_X$ is an isomorphism in $\mathsf{Set}$ for each object $X$.

So, at this point, you are left with simply checking which of the possible choices $\Omega_0 \in P(\Omega)$ satisfy that $f \mapsto f^{-1}(\Omega_0)$ is a bijection $\operatorname{Hom}(X, \Omega) \simeq P(X)$ for each set $X$. It turns out that exactly $\Omega_0 := \{ true \}$ and $\Omega_0 := \{ false \}$ work; it turns out it is more customary to set $\Omega_0 := \{ true \}$.