# 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.

##### Base case

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.

##### Inductive case

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 .