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.

Question: How can I complete the following sentence: "For all $\mathsf{Rel}$-arrows $f : X \rightarrow Y$, $f$ is a function iff ..."?

Of course, this is easily done: "For all $\mathsf{Rel}$-arrows $f : X \rightarrow Y$, $f$ is a function iff for all $x \in X$ there exists unique $y \in Y$ such that $(x,y) \in f$." However, I'm looking for something more category-theoretic in "spirit."

I'm also interested in variants of the sentence: replace "function" with injection/surjection/partial function/left-total relation etc.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

First, one must recall that $\textbf{Rel}$ is an allegory and in particular is a 2-category. Thus there is a notion of adjunction in $\textbf{Rel}$. It is traditional to say that a map in an allegory is a morphism with a right adjoint. So what does this notion give us in $\textbf{Rel}$? Well, suppose $\phi : X \to Y$ has a right adjoint $\psi : Y \to X$. That means that $\textrm{id}_X \le \psi \circ \phi$ and $\phi \circ \psi \le \textrm{id}_Y$. So, for each $x$, there exists $y$ such that $\phi (x, y)$ and $\psi (y, x)$; and for each $x, y, y'$, if $\psi (y, x)$ and $\phi (x, y')$, then $y = y'$. We thus deduce that $\phi$ is an total functional relation, and moreover $\psi (y, x) \equiv \phi (x, y)$. So a map in $\textbf{Rel}$ is what we expect to be: the relation induced by a function.

More generally:

  • $\phi : X \to Y$ represents an injection if it has a right adjoint $\psi : Y \to X$ and $\psi \circ \phi = \textrm{id}_X$.
  • $\phi : X \to Y$ represents an surjection if it has a right adjoint $\psi : Y \to X$ and $\phi \circ \psi = \textrm{id}_Y$.
  • $\phi : X \to Y$ represents a partial function if $\phi \circ \phi^{\circ} \le \textrm{id}_Y$.
  • $\phi : X \to Y$ represents a total relation if $\textrm{id}_X \le \phi^{\circ} \circ \phi$.
share|improve this answer
    
Sorry if this is a dumb question, but how does being an allegory imply being a 2-category? –  goblin Apr 22 '13 at 9:20
2  
$\textbf{Poset}$ is a subcategory of $\textbf{Cat}$ that is closed under finite products, so a category enriched over $\textbf{Poset}$ is also enriched over $\textbf{Cat}$. –  Zhen Lin Apr 22 '13 at 9:29
    
Cool, makes sense. –  goblin Apr 22 '13 at 13:20

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.