Category of sets and multi-valued functions

Question

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.

Answer 1

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

Answer 2

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