Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
I think you want to be careful about how you're bracketing the logical formulas. For example, you want to consider $\forall x, y: ((x, y) \in r \wedge p(x)) \Rightarrow p(y)$, and not $\forall x, y: (x, y) \in r \wedge (p(x) \Rightarrow p(y))$. Right? –  Todd Trimble Oct 7 '12 at 14:35
Yes, I thought the convention that $\land$ binds tighter than $\Rightarrow$ is quite common. Thanks for the hint. –  Helmut Brandl Oct 7 '12 at 14:49
The set of pairs $(x,y)$ such that either $p(x)$ is false or $p(y)$ is true is a transitive relation. By your assumption, it includes $r$. Therefore, it includes $\bar r$. (I've assumed classical logic here; for a constructive argument, replace "either $p(x)$ is false or $p(y)$ is true" with the classically equivalent but constructively weaker "if $p(x)$ then $p(y)$".) –  Andreas Blass Oct 7 '12 at 15:02
Thanks! It so simple. That's the answer to my question. –  Helmut Brandl Oct 7 '12 at 15:35
It would be common for guarded universal quantification, yes. I don't think you could consider it the convention for guarded existential quantification. –  Todd Trimble Oct 7 '12 at 15:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.