2
$\begingroup$

I recently started reading about relation algebras. This is a very new and unfamiliar, but interesting field to me. I'm not taking a course in it, it's self learning on my spare time, so please bear with me. My level is undergraduate-master with no real knowledge of relation algebras or formal order theory, but with some minor knowledge of category theory.

Let $R, S$ be binary relations (subsets of $X\times X$) on a finite set $X=\{x_1,\dots,x_n\}$. We can then define the composition of relations as

$\begin{equation*} R;S:= \{\,(x,y)\in X\times X\mid (x,z)\in R \operatorname{and}\, (z,y)\in S \text{ for some } z\in X\}. \end{equation*}$

This corresponds nicely to multiplication of logical matrices with elements in the two element boolean algebra.

Example: The following directed graph represents a relation $P$ on $X=\{A,B,C,D\}$.

Family tree

This can be represented by the logical matrix

$P=\begin{pmatrix} 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}$.

Say that $X$ represents a family. Then, we could possibly express the relation of being siblings as $P^\top;P$ where $P^\top$ means the converse of the relation $P$, and corresponds naturally to a transpose. However, we don't say that you are your own sibling, so we would set the diagonal to 0, perhaps like \begin{equation} (P^\top;P)\wedge \operatorname{di}_X \end{equation} where $\operatorname{di}_X=\{(x,y)\mid x\not=y\}$, here represented by $\operatorname{di}_X=\begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}$, and $\wedge$ denotes elementwise 'and'.

Then being someones aunt/uncle could possibly be represented by \begin{equation} ((P^\top;P)\wedge\operatorname{di}_X);P=\\ \Big(\Big(\begin{pmatrix} 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}\Big)\wedge \begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}\Big) \begin{pmatrix} 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 \end{pmatrix}=\\ \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}= \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix} \end{equation} which does make sense, since $B$ is the aunt/uncle of $D$ and it's the only such relation.

One can however define a dual notion of composition by exchanging and/or and exist/for all, let's call it $R\oplus S$ for now, as

$\begin{equation*} R\oplus S:= \{\,(x,y)\in X\times X\mid (x,z)\in R \operatorname{or}\, (z,y)\in S \text{ for all } z\in X\}. \end{equation*}$

As I understand it, this is the dual of $R;S$ in the same sense as $\vee$ and $\cup$ are duals of $\wedge$ and $\cap$ in order theory/logic and set theory, since we have that

\begin{equation} R\oplus S = \neg(\neg R;\neg S). \end{equation}

Just as $R;S$ can be represented by "ordinary" matrix multiplication, this dual can be represented by defining composition of matrices dually by exchanging operations in the usual definition, i.e. \begin{equation} (M\oplus N)(i,j):=\prod_{k=1}^{n}(M(i,k)+N(k,j)) \end{equation} where multiplication of elements means 'and' and addition 'or'. It then turns out that

\begin{equation} M\oplus N=\neg(\neg M\cdot \neg N) \end{equation}

if we let $\cdot$ denote the usual multiplication of logical matrices.

Questions:

  1. What is $R\oplus S$ as defined above called in general (cocomposition)? I've found very few references to it, for example in Relation Algebras by Steven Givant, where it's called relational sum. However, I cannot even seem to find the definition anywhere else, yet it seems like a very general thing. I looked at different types of joins of relations but I can't seem to find this one. Perhaps it's not so widely used, or I am lousy at looking. I've also looked a bit in Relational Topology by Winter and Schmidt, but that book was way above my level at the moment. Perhaps 'sum' is fine, but it sounds more like ordinary union to me.
  2. Is this dual multiplication of matrices used in other areas, i.e. over other structures, especially with ordinary real matrices, and if so, what is it called?
  3. Would anyone try and give (if possible) some intuition for the relational sum in a similar sense as one could for the composition, e.g. in the example of uncle above?
  4. Less important: Is my way of "setting the diagonal to zero", i.e. taking away the reflexive property of a relation $P$ by doing $P\wedge \operatorname{di}_X$ correct and standard, or would one express it differently?
$\endgroup$
1
$\begingroup$

The "relational sum" is often called "relative sum" and denoted $R \dagger S$ in (for example) Maddux Relation Algebras (2006). Maddux explains a lot about the history of the operation, which is also called "relative addition", and quotes Pierce in a useful extract. As Maddux says (p8) "It is fairly easy to express relative products in everyday language ... but relative sums present a greater challenge" and the examples provided do not make the operation sound conceptually obvious when modelling examples like uncles and aunts etc.

$\endgroup$
1
  • $\begingroup$ I will leave some room for more answers (I know I had one too many questions), but this was very useful and interesting. I had completely missed Maddux book, I will most certainly look it up and read about this. I've seen $R\dagger S$ actually, but only in one place, so I wasn't sure how standard it was. I rather like ; for composition and a '+' above a comma for relative sum (see tex.stackexchange.com/questions/237770/a-symbol-above-a-comma/… ), but perhaps that's just me, and I'm digressing. (Thank you!) $\endgroup$ Mar 12 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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