Lab 02, Solution of Exercise 2
We will show this by structural induction on the expression trees. Suppose we have for some fixed . Note that when writing , we mean the subset on relations represented by the expressions.
The expression is just a leaf, i.e. for some . Then either and follows directly from . Otherwise, , but in this case , since , so the result follows.
Now suppose monotonicity holds for two expressions and . Hence, denoting the relations represented by these expressions
by and respectively, and , where the primed version come from
replacing by in and .
Let . By
sequential composition preserves monotonicity and so .
Now let . Since
union preserves monotonicity and so .