Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume $\tau$ is the transitive closure of a relation $R$ over $A$.

Show that $\tau(R_1 \cap R_2)\subseteq \tau(R_1)\cap\tau(R_2)$

I got up to the point that:

$\tau(R_1 \cap R_2) = (R_1\cap R_2)\cup (R_1\cap R_2)^2\cup ...(R_1\cap R_2)^n ...$

and that:

$\tau(R_1)\cap\tau(R_2)=(R_1\cap R_2)\cup(R_1^2 \cup R_2)... \cup (R_1^n\cap R_2)... $

But I'm not sure how to proceed from here.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

First a little bit about transitive closure. Let $R$ be a binary relation on $A$. The transitive closure $\tau(R)$ of $R$ can be defined in several different ways. First $\tau(R)$ is the smallest transitive set containing $R$. It can be defined as $\tau(R) = \bigcup_{n \in \mathbb N} R^n$. One other property that can be used to define transitive closure is $(x, y) \in \tau(R)$ iff $\exists z_0, ..., z_n \in A$ such that $x = z_0$, $y = z_n$ and $(z_i, z_{i+1}) \in R$ for $i = 0, ..., n - 1$. This is easy to derive from $\tau(R) = \bigcup_{n \in \mathbb N} R^n$.

Back to the question. Assume $(x, y) \in \tau(R_1 \cap R_2)$. Then there are $x = z_0, z_1, ..., z_n = y \in A$ such that $(z_i, z_{i+1}) \in R_1 \cap R_2$. But then $(z_i, z_{i+1}) \in R_1$ and $(z_i, z_{i+1}) \in R_2$ for $i = 0, ..., n - 1$. Then $(x, y) \in \tau(R_1)$ and $(x, y) \in \tau(R_2)$ and so $(x, y) \in \tau(R_1) \cap \tau(R_2)$.

share|improve this answer
    
Could you explain in a little more detail, I'm still very new at this. –  Robert S. Barnes Nov 24 '11 at 10:11
    
I've edited my answer for more clarity. –  Levon Haykazyan Nov 24 '11 at 10:51
    
You might edit the answer because it's not immediately clear that when you say $(z_i , z_{i+1})\in R_1$ that you're referring to the whole chain of numbers from x to y. –  Robert S. Barnes Nov 28 '11 at 8:20

We can simply use the following properties:

  • If $S_1$, $S_2$ are transitive, then $S_1\cap S_2$ is transitive.

  • For any relation $R$ we have $R\subseteq \tau(R)$

  • If $S$ is transitive relation and $R\subseteq S$, then $\tau(R) \subseteq S$.

Now $R_1\subseteq\tau(R_1)$ and $R_2\subseteq\tau(R_2)$, hence $R_1\cap R_2\subseteq \tau(R_1)\cap\tau(R_2)$.

Since both $\tau(R_1)$ and $\tau(R_2)$ are transitive, their intersection $\tau(R_1)\cap\tau(R_2)$ is transitive as well.

We see that $R_1\cap R_2\subseteq\tau(R_1)\cap\tau(R_2)$ and $\tau(R_1)\cap\tau(R_2)$ is transitive. By the third claim I mentioned above we get $\tau(R_1\cap R_2)\subseteq\tau(R_1)\cap\tau(R_2)$ .


Possible generalization:

Transitive closure is a special case of closure operator. Another example of closure operator is closure in topological space.

You can notice that we only used the properties which are true for every closure operator. (If $c: \mathcal P(X) \to \mathcal P(X)$ is a closure operator then the sets fulfilling $c(A)=A$ are closed. In your example, they are the transitive sets. In can be shown that, for aribtrary closure operator, intersection of closed sets is closed.)

share|improve this answer
    
+1 for a nice elegant answer. I accepted the other answer because I learned more that I didn't understand from it. Thanks. –  Robert S. Barnes Nov 28 '11 at 8:21

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.