MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.