Transitive closures and inductive reasoning [solved] - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:14:06Z http://mathoverflow.net/feeds/question/109066 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109066/transitive-closures-and-inductive-reasoning-solved Transitive closures and inductive reasoning [solved] Helmut Brandl 2012-10-07T14:28:20Z 2012-10-07T22:53:23Z <p>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).</p> <p>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).</p> <p>I am trying to proof that the transitive closure $\bar{r}$ of r has this property as well.</p> <p>I.e. I am trying to proof</p> <p>$$(\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))$$</p> <p>But I cannot find a proof of this assertion.</p> <p>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.</p> <p>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.</p>