Rigorous definition of relation composition

Question

Let $R$ be an $n$-ary multivalued function on $A$, and let $S_1, ..., S_n$ be a list of length $n$, each member of which is an $m$-ary multivalued function on $A$. How does one rigorously define the composition $R(S_1, ... , S_n)$?

Answer 1

Rather than thinking of an $n$-ary multivalued function on $A$ as an $(n+1)$-ary relation, let's think of it as a (genuine) function from $A^n$ to the powerset $\mathcal P(A)$ of $A$. That is, the output of a multivalued function will be a set of elements of $A$ instead of just a single element of $A$.

Now let's turn to your motivating example to get an idea of how we might want to define composition. In our setting, the multivalued square root is just a function $\mathbb R\to\mathcal P(\mathbb R)$ that sends $16$ to $\{-4,4\}$, $0$ to $\{0\}$ and $-1$ to $\emptyset$. What is going to happen if we try to take the square root of 16 twice? Well, the first square root gives us the set $\{-4,4\}$, but how do we now carry out the second square root?

The sensible option seems to be to apply our square root function to each element of the set $\{-4,4\}$ in turn and consider the union of the two resulting sets to be the output of the composition. The square root of $-4$ is $\emptyset$ and the square root of 4 is $\{-2,2\}$, so we have that the "fourth root" of $16$ is $\emptyset\cup\{-2,2\}=\{-2,2\}$.

The empty set in this example hides the idea a bit, so maybe we should consider what happens for the square root function $\mathbb C\to\mathcal P(\mathbb C)$ instead. The square root of $1$ is $\{-1,1\}$, and the square root of this set is $\{-\mathrm i,\mathrm i\}\cup\{-1,1\}$ - the set of fourth roots of unity.

So, to answer your original question, let's define your general composition in a similar way. Let $R\colon A^n\to\mathcal P(A)$ and let $S_1,\dotsc,S_n\colon A^m\to\mathcal P(A)$. Then we'll define $R(S_1,\dotsc,S_n)$ to be the function $A^m\to\mathcal P(A)$ sending $a=(a_1,\dotsc,a_m)$ to $$\bigcup_{b_i\in S_i(a)}R(b_1,\dotsc,b_n).$$ In other words, the multivalued function $R(S_1,\dotsc,S_n)$ takes the value $c$ at $a$ if and only if there exist $b_1,\dotsc,b_n\in A$ for which $R$ takes the value $c$ at $(b_1,\dotsc,b_n)$ and for which each $S_i$ takes the value $b_i$ at $a$.

If you prefer to think in terms of relations, you might notice that this description is very similar to the definition of composition of binary relations.