Transitive closures and inductive reasoning [solved]

2012-10-07T14:28:20Z

Let's say that r is an endorelation over A (i.e. $r$ is a subset of $A \times A$), $\bar{r}$ is the transitive closure of r (i.e. the least set containing r and being transitive).

Furthermore $r$ has the property that for all $x,y$ such that $(x,y) \in r$ and $x$ has a certain property $p(x)$ implies that $y$ has the property as well ($p(y)$ is valid).

I am trying to proof that the transitive closure $\bar{r}$ of r has this property as well.

I.e. I am trying to proof

\begin{equation} (\forall x,y: (x,y) \in r \land p(x) \Rightarrow p(y)) \Rightarrow (\forall x,y: (x,y) \in \bar{r} \land p(x) \Rightarrow p(y)) \end{equation}

But I cannot find a proof of this assertion.

For me the above claimed assertion is obvious so it should have a proof. Can anybody help me to find some or to find counterexample which demonstrates that the above assertion is not valid in general.

It is easy to prove that $r$ and its transitive closure have the same domain and the same range. Furthermore I can prove that any domain/range restriction of $r$ results in the same domain/range restriction of its transtitive closure.

Transitive closures and inductive reasoning [solved] - MathOverflow

Transitive closures and inductive reasoning [solved]