0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Todd Trimble
    Commented Oct 7, 2012 at 14:35
  • $\begingroup$ Yes, I thought the convention that $\land$ binds tighter than $\Rightarrow$ is quite common. Thanks for the hint. $\endgroup$
    – Helmut Brandl
    Commented Oct 7, 2012 at 14:49
  • 2
    $\begingroup$ 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)$".) $\endgroup$
    – Andreas Blass
    Commented Oct 7, 2012 at 15:02
  • $\begingroup$ It would be common for guarded universal quantification, yes. I don't think you could consider it the convention for guarded existential quantification. $\endgroup$
    – Todd Trimble
    Commented Oct 7, 2012 at 15:55

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .