I'm reading "an introduction to category theory" by Harold Simmons. In this books, exercise 1.2.7 wants us to show that $\mathcal{Set}_\bot$ (the category of pointed sets) and $\mathcal{Pfn}$ (the category of sets and partial functions) are "essentially the same" category. So I guess this is to let us prove that these two categories can be somehow converted to each other. Here is my attempt:

For every arrow $\phi : S \rightarrow T$ in $\mathcal{Set}_\bot$, just restrict the domain of $\phi$ to $\{\bot_s\}$, and then the category becomes $\mathcal{Pfn}$.

For every arrow $f : S \rightarrow T$ in $\mathcal{Pfn}$, let $X$ be the domain of $f$. For each $x \in X$, we make two pointed sets: $(S,x)$, $(T,f(x))$ and also an arrow between these two pointed sets, which is a function: $\forall x' \in S, f(x') = f(x)$. I think this should convert $\mathcal{Pfn}$ into a $\mathcal{Set}_\bot$.

Obviously there are many ways to convert from $\mathcal{Pfn}$ to $\mathcal{Set}_\bot$ and the other way around might also be true. However, the problem is: once I convert one to the other, some information are "dropped" so that I can't convert it back to recover the category before conversion.

So my question is:

  • When we say two categories are "essentially the same", what does it exactly mean?
  • Is my attempt valid?
  • Is there some way to convert between each other without losing anything?
  • 2
    $\begingroup$ I can't quite figure out what you're trying to do. What you really want to do is to find two functors between the two categories that are an equivalence. The simplest pair of functors is based upon the idea of thinking of the point as representing an undefined value of the set. $\endgroup$
    – user14972
    Aug 1 '14 at 8:32
  • 1
    $\begingroup$ "Is my attempt valid?" - No. $\endgroup$ Aug 1 '14 at 8:44

It means that the categories are equivalent.

Consider the functor $F : Pfn \to Set_*$ which maps a set $X$ to the pointed set $(X \sqcup \{*\},*)$, and a partial map $p : X \to Y$ to the pointed map $p_* : X \sqcup \{*\} \to Y \sqcup \{*\}$ which maps $* \mapsto *$, $x \mapsto *$ if $p(x)$ is not defined, and otherwise $x \mapsto p(x)$. It is easy to check $(\mathrm{id}_X)_* = \mathrm{id}_{X \sqcup \{*\}}$ and $(p \circ q)_* = p_* \circ q_*$. Hence, $F$ is in fact a functor.

The functor $F$ is essentially surjective: If $(P,*)$ is any pointed set, then $X:=P \setminus \{*\}$ is a preimage, i.e. $(X \sqcup \{*\},*) \cong (P,*)$.

The domain of $p$ can be recovered from $p_*$, namely it consists of those points $\neq *$ which get mapped to something $\neq *$. But then also $p$ can be recovered from $p_*$, since $p$ is the restriction of $p_*$ to the domain of $p$. It follows that $F$ is faithful.

Finally, $F$ is full: If $X \sqcup \{*\} \to Y \sqcup \{*\}$ is any pointed map, let $D$ be the set of points of $X$ which do not get mapped to $* \in Y \sqcup \{*\}$. Then we obtain a map $D \to Y$ and hence a partial map $p : X \to Y$, which is clearly a preimage.

Alternatively, one writes down directly a functor $G : Set_* \to Pfn$ which is (pseudo-) inverse to $F$: We put $G(X,*)=X \setminus \{*\}$ and $G(f : X \to Y) = (X \setminus f^{-1}(*) \to Y \setminus \{*\}, x \mapsto f(x))$.

  • $\begingroup$ Thanks for your answer! Now I get the idea about how the basepoint should be used to make a partial function full. $\endgroup$
    – Javran
    Aug 1 '14 at 9:31
  • 1
    $\begingroup$ Yes. You can also read $*$ as "undefined". $\endgroup$ Aug 1 '14 at 9:32
  • $\begingroup$ @MartinBrandenburg Or just let $F(X)=(X\cup\{X\},X)$ (uses the axiom of regularity) $\endgroup$ Aug 1 '14 at 12:27
  • 2
    $\begingroup$ This works, but it is not really important what the new base point "is". It is only important that it doesn't lie in $X$. The axioms of ZFC permit us to choose $X$ to be the base point, that's true. But sets and ZFC are not the end of the story. The equivalence works for any elementary topos in which the terminal object $*$ is injective, I think. $F(X)$ is the coproduct of $X$ with $*$. $\endgroup$ Aug 1 '14 at 14:11
  • $\begingroup$ @MartinBrandenburg By "injective" you mean projective? ;) $\endgroup$ Aug 1 '14 at 15:00

Despite that these categories are equivalent, you have to be a little careful with the translation.

For example, partial functions $X \times Y \rightarrow Z$ correspond to pointed-set homomorphisms $X \otimes Y \rightarrow Z$, where $\otimes$ is the smash product. This is because the free functor $F : \mathbf{Set} \rightarrow \mathbf{Set}_*$ satisfies the identity $F(X \times Y) = F(X) \otimes F(Y),$ not the identity $F(X \times Y) = F(X) \times F(Y)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.