Lab 02 - Partial solution of Exercise 4

We will show that the first two statements are equivalent.

Let $P = \bigtriangleup_A \cup s \circ r \subseteq s$ and $H = \lbrace s | P(s)\rbrace$. Note that the full relation $A \times A$ satisfies $P$, hence the intersection is well-defined.
Then we claim that $l = \bigcap H$ is the least relation $s$ satisfying $P$. It is least, since $\forall s. P(s) \wedge l \subseteq s$ by the properties of intersection. It remains to show that $l$ itself satisfies $P$, i.e. that $P(l)$.

Now we claim $r^* = l$, i.e. $\bigcap H = r^*$.


  \bigtriangleup_A \cup r^* \circ r &= \bigtriangleup_A \cup (\bigcup_{i \ge 0} r^i) \circ r \\
  &= \bigtriangleup_A \cup \bigcup_{i \ge 0} r^{i+1}\\
  &= r^*\\

Hence, we have shown that $r^* \in H$ and thus $\bigcap H = ... \cap r^* \cap ... \subseteq r^*$.


From $\Delta_A\ \cup\ (s \circ r)\ \subseteq\ s$, we have that $\bigtriangleup_A \subseteq s$.

 \bigtriangleup_A &\subseteq& s\\
 r = \bigtriangleup_A \circ r &\subseteq& s \circ r \subseteq s\\
 r &\subseteq& s \\
 r \circ r &\subseteq& s \circ r \subseteq s\\
 r^2 &\subseteq& s\\
 r^n &\subseteq& s\\
 r^n \circ r &\subseteq& s \circ r \subseteq s\\
 r^* &\subseteq& s

Hence, $\bigcap H = ... \cap s_1 \cap s_2 \cap ... \supset ... \cap r* \cap r* \cap ... $. Thus we have shown $\bigcap H \supseteq r^*$.

From $\bigcap H \supseteq r^*$ and $\bigcap H \subseteq r^*$ it follows that $\bigcap H = r^*$.