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

1)

$\begin{equation*} \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^*\\ \end{equation*}$

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

2)

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

$\begin{equation*}\begin{array}{rcl} \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 \end{array}\end{equation*}$

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