Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
So I'm wondering about some finer points of relation algebra, a field in which I'm not an expert:
Given relations $A$, $B$ and $C$ over the same set $S$, is it always true that $A^*\subseteq (B\cup C)^*$ iff $(A\setminus B)^*\subseteq C^*$ ?
Here, $A^*$ denotes the reflexive, transitive closure of $A$, $\cup$ is set union, and $\setminus$ is set difference.
Consider $S=\{1,2,3\}$ and relations $A=\{(1,3)\}, B=\{(1,2)\}, C=\{(2,3)\}$. Then
$A^*=(A\setminus B)^*= A\cup\{(i,i)\ |\ i\in S\}$,
$(B\cup C)^* = \{(i,j)\ |\ i,j\in S, i\le j\}$, and
$C^* = C\cup \{(i,i)|i\in S\}$.
In particular, $A^*\subseteq (B\cup C)^*$, but $(A\setminus B)^*\nsubseteq C^*$.
