Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
2  
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. –  Hurkyl Aug 1 at 8:32
    
"Is my attempt valid?" - No. –  Martin Brandenburg Aug 1 at 8:44

2 Answers 2

up vote 8 down vote accepted

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))$.

share|improve this answer
    
Thanks for your answer! Now I get the idea about how the basepoint should be used to make a partial function full. –  Javran Aug 1 at 9:31
1  
Yes. You can also read $*$ as "undefined". –  Martin Brandenburg Aug 1 at 9:32
    
@MartinBrandenburg Or just let $F(X)=(X\cup\{X\},X)$ (uses the axiom of regularity) –  Hagen von Eitzen Aug 1 at 12:27
2  
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 $*$. –  Martin Brandenburg Aug 1 at 14:11
    
@MartinBrandenburg By "injective" you mean projective? ;) –  Rooibos Tee Aug 1 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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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