LARA

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)$.