Monotonic Relation

Question

Consider the relations $r_1, r_2, \ldots , r_n$ and consider a relational expression language as follows:

$r_i$ is a relational expression, $1 \le i \le n$

$e_1 \circ e_2$ is a relational expression if $e_1$ and $e_2$ were relational expressions and where $\circ$ is the composition operator.

$e_1 \cup e_2$ is a relational expression if $e_1$ and $e_2$ were relational expressions and where $\cup$ is the union operator.

For example, $(r_1 \circ r_2) \cup r_2$ is a relational expression. Show that any relational expression $e(r_1, r_2, \ldots , r_n)$ where each $r_i$ appears exactly once is monotonic that is for all $i$, $1 \le i \le n$,

$r_i \subseteq r_i' \rightarrow e(r_1, r_2, \ldots , r_i, \ldots , r_n) \subseteq e(r_1, r_2, \ldots, r_i', \ldots , r_n)$

Answer 1

The definition of relational expression is inductive, so the natural way to prove statements about relational expressions is by induction on their construction. Suppose that you want to show that all relational expressions have a certain property $P$. Then you prove

1. that the atomic relational expressions $r_1,\dots,r_n$ have $P$;
2. that if $e_1$ and $e_2$ are relational expressions with $P$, then $e_1\circ e_2$ has $P$; and
3. that if $e_1$ and $e_2$ are relational expressions with $P$, then $e_1\cup e_2$ has $P$.

From this it follows that all relational expressions have $P$; this is structural induction.

To see why this is so, suppose that some relational expression fails to have $P$. Among all such ‘bad’ relational expressions, let $e$ be one of minimal length. We know from (1) that $e$ isn’t one of the atomic relational expressions, so there must be relational expressions $e_1$ and $e_2$ such that either $e=e_1\circ e_2$ or $e=e_1\cup e_2$. But $e_1$ and $e_2$ are shorter than $e$, so by the choice of $e$ they do have $P$, and therefore so does $e$, by (2) or by (3), whichever is appropriate. This contradiction shows that there are no such ‘bad’ relational expressions: all relational expressions have $P$.

In this problem the basic property in question is montonicity, but there is a small twist: we demand it only of those relational expressions in which each $r_i$ appears exactly once. There’s a fairly standard trick for accommodating this kind of limitation. For now let’s say that a relational expression is nice if each of $r_1,\dots,r_n$ appears in it exactly once. Then we define our property $P$ as follows:

a relational expression $e$ has $P$ iff either $e$ is not nice, or $e$ is both nice and monotonic.

Proving that every relational expression has this property $P$ is the same as proving that every nice relational expression is monotonic.

However, it’s not clear to me that niceness matters. At the very least you ought to be able to show monotonicity for all relational expressions in which each of the $r_i$’s appears at most once, and probably for all relational expressions, though I’ve not thought through the details to be sure.