# Category of sets and multi-valued functions

I would like to study category of sets and multi-valued functions: A category whose objects are sets and morphisms are multi-valued functions.

By a multi-valued function $f:A\rightarrow B$, from set A to set B, I mean a function that assigns to each element of A, a subset of B. There might be some elements like a in A that are associated with empty set, that is $f(a)=\emptyset$.

In general, I would like to know how the composition is defined and what are the following constructions semantics in such a category: Pullback, Pushout, Product, Coproduct, etc.

Question:

Is there any reference that studies this category that I can take a look?

ps. I would appreciate if somebody could provide at least a short answer with the semantics of the above constructs if no reference specifically studies this category.

What you are describing is the category of $\mathbb {Rel}$ of sets and relations.

The objects of this category are sets and the morphisms are binary relations. This comes from the fact that there is a bijection between the sets of function of the form $X \to \mathcal P(Y)$ and (relations) subsets of the cartesian product $X \times Y$: this bijection is given by the mapping that to every $R \subseteq X \times Y$ associates the mapping $r \colon X \to \mathcal P(Y)$ defined by $$r(x) = \{y \in Y \mid (x,y) \in R\}$$ the inverse of this correspondence associates to each mapping $r \colon X \to \mathcal P(Y)$ the subset $R \subseteq X \times Y$ defined by $$R = \{(x,y) \in X \times Y \mid y \in r(x)\}$$.

This category can be equivalently be characterized as the Kleisli category for the powerset monad on $\mathbb{Set}$. You can find more details on this in the references below.

http://ncatlab.org/nlab/show/Rel

https://en.wikipedia.org/wiki/Category_of_relations

• Indeed, the OP's description of the category is exactly the definition of the Kleisli category for the powerset monad. Jun 23, 2015 at 16:02

There are two categories you might be thinking of.

1) The category Rel of sets and relations, with composition defined via: $z \in (P \circ Q)(x) \Leftrightarrow \exists y \in Q(x) \ z \in P(y)$

This category is described in Giorgio Mossa's answer.

2) The category Mult of sets and multivalued functions, with composition defined via: $z \in (P \circ Q)(x) \Leftrightarrow [ (\forall y \in Q(x) \ P(y) \neq \emptyset) \wedge (\exists y \in Q(x) \ z \in P(y))]$

The motivation of this slightly more complicated definition comes from computer science. There we might want to use multivalued functions to describe (robust) non-deterministic computations - we don't know what output we're going to get precisely, but we know that we are going to get something according to the specification. As the question whether or not our computation will be succesfull is not supposed to depend on the non-deterministic part, we don't consider input valid, if not all outputs of the first multifunction can be put into the second.

A more formal way of expressing this is to look at partial choice functions: If $P : X \to Y$ is a multivalued function, then a partial function $f : \subseteq X \to Y$ is a choice function for $P$ if $P(x) \neq \emptyset$ implies that $f(x)$ is defined and $f(x) \in P(x)$. Now compositions of choice functions are choice functions of the (multivalued) composition, but not necessarily of the relational composition.

Some properties of Mult: Coproducts are just inherited from Set, but products don't work well. In many ways, the category of multivalued functions should be considered as having some addiotional structure, in particular as being poset-enriched.

Reference: http://arxiv.org/abs/1102.3151

• What's the difference between the category of sets and (binary) relations and the category of sets and multivalued function? They should be the same category, should be? Jun 23, 2015 at 12:59
• Composition is defined differently, and subsequently most properties are different. Essentially, the graph composition of multivaled functions is a subset of the (relational) composition of their graphs, and sometimes a proper subset.
– Arno
Jun 23, 2015 at 13:11
• could you provide an example? Jun 23, 2015 at 13:17
• @GiorgioMossa: If I'm not mistaken, the difference is the line in this answer which defines $dom(f\circ g)$. This means that $f(g(x))$ is nonempty only if $f$ has a value at every possible value of $g(x)$. On the other hand, in Rel, $f(g(x))$ is nonempty as long as $f$ has a value at some possible value of $g(x)$. Jun 23, 2015 at 15:18
• I've rewritten my answer, hopefully it makes sense now. The motivation is also explained a little bit.
– Arno
Jun 23, 2015 at 19:32