Lab 02, Solution of Exercise 2

We will show this by structural induction on the expression trees. Suppose we have $r_i \subseteq r_i'$ for some fixed $i$ . Note that when writing $E(r_1, ..., r_i, ... , r_n) \subseteq E(r_1, ..., r_i', ... , r_n)$ , we mean the subset on relations represented by the expressions.

Base case

The expression $E$ is just a leaf, i.e. $E(r_1,..., r_i, ..., r_n) = r_j$ for some $j$ . Then either $i = j$ and $E(r_1,..., r_i, ..., r_n) \subseteq E(r_1,..., r_i', ..., r_n)$ follows directly from $r_i \subseteq r_i'$ . Otherwise, $i \ne j$ , but in this case $r_j \subseteq r_j$ , since $r_j = r_j$ , so the result follows.

Inductive case

Now suppose monotonicity holds for two expressions $E_1$ and $E_2$ . Hence, denoting the relations represented by these expressions by $s_1$ and $s_2$ respectively, $s_1 \subseteq s_1'$ and $s_2 \subseteq s_2'$ , where the primed version come from replacing $r_i$ by $r_i'$ in $E_1$ and $E_2$ .
Let $E = E_1 \circ E_2$ . By

$\begin{equation*} \begin{array}{l} (x, y) \in s_1 \circ s_2 \leftrightarrow \exists w. (x, w) \in s_1 \wedge (w, y) \in s_2\\ \rightarrow \exists w. (x, w) \in s_1' \wedge (w, y) \in s_2 \\ \leftrightarrow (x, y) \in s_1' \circ s_2 \end{array} \end{equation*}$

sequential composition preserves monotonicity and so $E(r_1,..., r_i, ..., r_n) \subseteq E(r_1,..., r_i', ..., r_n)$ .

Now let $E = E_1 \cup E_2$ . Since

$\begin{equation*} \begin{array}{1} (x, y) \in s_1 \cup s_2 \leftrightarrow (x, y) \in s_1 \wedge (x, y) \in s_2\\ \rightarrow (x, y) \in s_1' \wedge (x, y) \in s_2\\ \leftrightarrow (x, y) \in s_1' \cup s_2 \end{array} \end{equation*}$

union preserves monotonicity and so $E(r_1,..., r_i, ..., r_n) \subseteq E(r_1,..., r_i', ..., r_n)$ .