1
$\begingroup$

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.

2 Answers 2

2

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)$.

  • 0
    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.2011-11-28
2

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

  • 0
    +1 for a nice elegant answer. I accepted the other answer because I learned more that I didn't understand from it. Thanks.2011-11-28