<p>Consider $S=\{1,2,3\}$ and relations $A=\{(1,3)\}, B=\{(1,2)\}, C=\{(2,3)\}$. Then </p>

<p>$A^*=(A\setminus B)^*= A\cup\{(i,i)\ |\ i\in S\}$,</p>

<p>$(B\cup C)^* = \{(i,j)\ |\ i,j\in S, i\le j\}$, and</p>

<p>$C^* = C\cup \{(i,i)|i\in S\}$.</p>

<p>In particular, $A^*\subseteq (B\cup C)^*$, but $(A\setminus B)^*\nsubseteq C^*$.</p>

CC BY-SA 3.0
2013-06-12T16:10:03.253Z
2013-06-12T16:10:03.253Z
Klaus Draeger
<p>So I'm wondering about some finer points of relation algebra, a field in which I'm not an expert:</p>

<p>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^*$ ?</p>

<p>Here, $A^*$ denotes the reflexive, transitive closure of $A$, $\cup$ is set union, and $\setminus$ is set difference.</p>

<relational-structures>
Relation between Kleene star, union and difference in relation algebra
Uli Fahrenberg
# Relation between Kleene star, union and difference in relation algebra

(Asked by: username_0 on 2013-06-12)

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.

**Tags:** relational-structures

---

## 1 answers

### Answer by username_1 on 2013-06-12. Score: 4 | Accepted answer

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^\*$.


---

