We are given a binary relation $R \subseteq X \times X$ and $R^+ \subseteq X \times X$, where $R \subseteq R^+$.
Given the axiom $$\frac{}{(x,x) \in R^+} ,\ (x \in X)$$ and the rule: $$\frac{(x,y) \in R^+}{(x,z) \in R^+},\ (x\in X \land (y,z) \in R)$$
We want to use rule induction to prove that $R^+$ is a subset of the following set S:
$$S = \{(y,z) \in X \times X : \forall x\in X. (x,y) \in R^+ \implies (x,z) \in R^+\}$$
and thus show that $R^+$ is transitive.
My thoughts:
To show that $R^+$ is a subset of $S$, I got to show that for any element of $R^+$ implies that element is also in $S$.
Looking at how $S$ requires $(y,z)$, I am thinking of showing the transitive relation $(y,x) \in R^+ \land (x,z)\in R^+ \implies (y,z) \in R^+$.
But the problem is I cannot be sure $(y,x) \in R^+$ since I only know it's $(x,y) \in R^+$. Also, even if I can prove the statement in point 2, I cannot show it means $(y,z) \in S$.
How should I proceed further?
