How do I use rule induction to prove this relation?

Question

Suppose $T^*$ denotes the reflexive-transitive closure of some relation T on set $A$. For relations $R$ and $S$ on set $A$, prove that if $id_A \subseteq (R \cap S)$ then $(R \cup S)^* = (R \circ S)^*$.

We are given the following inductive rules:

$$\frac{(x,y) \in T}{(x,y)\in T^*} (x,y\in A)$$ $$\frac{}{(x,x)\in T^*} (x \in A)$$ $$\frac{(x,y)\in T^*\qquad (y,z)\in T^*}{(x,z)\in T^*}(x,y,z \in A)$$

My thoughts:

1. The inductive rules seems to show the basic properties of transitivity and reflexivity.

2. For the proof, I think we might need to show two things, essentialy $(R\cup S)^* \subseteq (R\circ S)^*$ and $(R\circ S)^* \subseteq (R\cup S)^*$ to show the equality, using the identity relation.

Some stuff I've done:

First we know $id_A \subseteq (R \cap S)$

$$\implies \forall a \in A . a (R \cap S) a$$

$$\implies \forall a \in A . aRa \land aSa$$

But I'm stuck in transforming the intersection into the union as required, and since I start with the identity relation, I'm stuck with proving only reflexivity and not transitivity. Also, I'm unable to use the rule induction methods.

====

Edit: Is there a way to find a pure rule induction method to solve? i.e. something like this:

Source: https://www.andrew.cmu.edu/user/annpenny/15317-f13/rule-induction.pdf

The problem I've been facing is I can't seem to find a concrete way to use rule induction. I understand we can derive the rules in normal set theoretic form to try solve the problem, but is there a way to directly use the rule induction method? I've not been able to understand how the "derivatives" of rule induction works unfortunately (nevertheless there are great answers set out below).

Answer 1

Note $R\cup S\subseteq R\circ S$. This is because for any $(x,y)\in R$, you have $(x,y)\circ(y,y)=(x,y)\in R\circ S$, and similarly any $(x,y)\in S$ is in $R\circ S$. Therfore, $(R\cup S)^*\subseteq (R\circ S)^*$.

For the other direction, note that the elements of $(R\circ S)^*$ are of the form $(x_1,x_n)$, where there exists a chain of elements $$ x_1,x_2,\dots,x_n $$ such that each $(x_i,x_{i+1})\in R\circ S$. This means there exists a $y_i$ such that $(x_i,y_i)\in R$ and $(y_i,x_{i+1})\in S$, which gives a chain $$ x_1,y_1,x_2,y_2,\dots,y_{n-1},x_n $$ in $R\cup S$. This proves that $(x_1,x_n)\in (R\cup S)^*$, proving the reverse inclusion.

Answer 2

This is an hint of a proof, you should add the details, but hopefully it will be enough for your purposes.

As you noted you should prove that $(R \cup S)^* \subseteq (R \circ S)^*$ and $(R \circ S)^* \subseteq (R \cup S)^*$.

You should prove this inclusion by induction on the inference rules which provides an inductive definition for $(R \cup S)^*$ and $(R \circ S)^*$ when you replace $T$ with $R \cup S$ and $R \circ S$ respectively.

Consider the first inclusion, we would have to prove that for every $(x,y) \in (R \cup S)^*$ then $(x,y) \in (R \circ S)^*$.

By the inductive definition you have that $(x,y) \in (R \cup S)^*$ if and only if you can build a derivation/proof for the pair $(x,y)$ using the inference rules $T^*$ when $T=R \cup S$.

Then proceeding by induction on such derivation for $(x,y)$ you can prove that $(x,y) \in (R \circ S)^*$.

Specifically you have to prove that if

• $y=x$, that is $(x,y)$ is obtained by the first rule, then $(x,y) \in (R \circ S)^*$
• if $(x,y) \in R \cup S$, that is $(x,y)$ is obtained by the second rule, then $(x,y) \in (R \circ S)^*$
• if there is a $z$ such that both $(x,z)$ and $(z,y)$ belong to $(R \cup S)^*$, that is $(x,y)$ is obtained by the third inference rule, then $(x,y) \in (R \circ S)^*$.

Then you have to do the same exchanging the roles of $R \cup S$ and $R \circ S$.

Answer 3

Since $I \subseteq R \cap S$, one gets \begin{align} R &= R \circ I \subseteq R \circ S \\ S &= I \circ S \subseteq R \circ S \end{align} Thus $R \cup S \subseteq R \circ S$, and hence $(R \cup S)^* \subseteq (R \circ S)^*$. For the opposite inclusion, observe that $$ R \circ S \subseteq (R \cup S) \circ (R \cup S) \subseteq (R \cup S)^* $$ It follows that $(R \circ S)^* \subseteq ((R \cup S)^*)^* = (R \cup S)^*$. Thus $(R \circ S)^* = (R \cup S)^*$.

Answer 4

You've written out the rules but not what rule induction states. Rule induction for this set of rules states the following: $$\begin{align}&(\forall x\in A.(x,x)\in X)\\\land\ &(\forall x,y\in A.(x,y)\in T\Rightarrow(x,y)\in X)\\\land\ & (\forall x,y,z\in A. (x,y)\in X\land (y,z)\in X\Rightarrow(x,z)\in X)\\\implies\ &(\forall x,y\in A.(x,y)\in T^*\Rightarrow (x,y)\in X)\end{align}$$ for any relation $X$. Using the fact that $X\subseteq Y \iff (\forall x,y\in A.(x,y)\in X\Rightarrow (x,y)\in Y)$ we can rewrite this rule induction more compactly as: $$(id_A\subseteq X)\land(T\subseteq X)\land(X\circ X \subseteq X)\implies T^*\subseteq X$$ This is what leads to the usual set-theoretic expression of inductively defined structures as the smallest set meeting some rules, i.e. $T^*$ is the smallest binary relation on $A$ containing $T$ and closed under reflexivity and transitivity. Any other binary relation on $A$, $X$, which contains $T$ and is closed under reflexivity and transitivity contains $T^*$.

As you intuited, you'll want to show $(R\cup S)^* = (R\circ S)^*$ via showing $(R\cup S)^*\subseteq (R\circ S)^*$ and $(R\circ S)^*\subseteq (R\cup S)^*$. Rule induction will give you this if choose $T=R\cup S$ and $X=(R\circ S)^*$, and $T=R\circ S$ and $X=(R\circ S)^*$ respectively.

The good news is that $T^*$ for any binary relation $T$ on $A$ automatically satisfies $id_A\subseteq T^*$ and $T^*\circ T^* \subseteq T^*$. (To prove this, just apply rule induction for $X=T^*$.) This means for the $T=R\cup S$ and $X=(R\circ S)^*$ case, we simply only need to show $R\cup S \subseteq (R\circ S)^*$ since the other two antecedents hold automatically. Similarly, for the opposite direction, we only need to show $R\circ S\subseteq (R\cup S)^*$.

From here, it is largely binary relational algebra calculations a la J.-E. Pin's answer or Mike Earnest's answer, though you can omit some of their argumentation as that's already been covered by the general reasoning about rule induction above. For example, the last line of J.-E. Pin's answer involving $((R\cup S)^*)^*$ is not necessary, as we were done (with this half) as soon as we established $R\circ S\subseteq (R\cup S)^*$. Rule induction also gives a formal basis for some of the steps they've elided, e.g. that $R\cup S\subseteq R\circ S\implies (R\cup S)^*\subseteq (R\circ S)^*$. This is intuitively true and easily proven directly, but it also follows from rule induction, though really we just need to establish $R\cup S\subseteq (R\circ S)^*$.