1. ## Prove transitive relations

I have two related problems. Prove or disprove:

If $R \subseteq A \times A$ and $S \subseteq A \times A$ are transitive relations then $R \cup S$ is a transitive relation.

If $R \subseteq A \times A$ and $S \subseteq A \times A$ are transitive relations then $R \cap S$ is a transitive relation.

The first, I completely understand, because if you union two transitive relations, the combined relation will still be transitive. (Unless I am way off.)

The second has proven more difficult to prove/disprove. Every example that I have come up with has been "vacuously" transitive. I had never heard of that until the other day and I believe that is why it is proving more difficult for me. If anyone could help with this proof, I would much appreciate it. A good nudge in the right direction?

Thanks!

2. Originally Posted by Pi R Squared
I have two related problems. Prove or disprove:
If $R \subseteq A \times A$ and $S \subseteq A \times A$ are transitive relations then $R \cup S$ is a transitive relation.
If $R \subseteq A \times A$ and $S \subseteq A \times A$ are transitive relations then $R \cap S$ is a transitive relation.

The first, I completely understand, because if you union two transitive relations, the combined relation will still be transitive. (Unless I am way off.)

The second has proven more difficult to prove/disprove.
The first is false. $A=\{1,2,3\},~R=\{(1,2)\}~\&~S=\{(2,3)\}$.
There are two transitive relation but their union is not transitive.

The second is trivial. $(a,b) \in R \cap S \Rightarrow (a,b) \in R\,\& \,(a,b) \in S$.
So both transitive implies the intersection is transitive.

3. ## This helps...

I typed the union and the intersection in backwards. But your explanation makes sense. So if I have two 'vacuously' transitive sets, I have the empty set. Therefore, it is not transitive. Am I understanding this correctly?

4. Originally Posted by Pi R Squared
I typed the union and the intersection in backwards. But your explanation makes sense. So if I have two 'vacuously' transitive sets, I have the empty set. Therefore, it is not transitive. Am I understanding this correctly?
The union of two transitive relations on a set is not necessarily transitive.
The intersection of two transitive relations on a set is transitive.

5. ## General proof R intersection S

Originally Posted by Plato
The second is trivial. $(a,b) \in R \cap S \Rightarrow (a,b) \in R\,\& \,(a,b) \in S$.
So both transitive implies the intersection is transitive.
Transitivity is whenever aRb and bRc, then aRc. How would I start a proof that would encompass all situations. I understand how to prove a certain given situation... It is the general proof when I am dealing with X number of terms that confuses me. I cannot just use aRb... I would continue with another line saying something like $(b,c) \in R \cap S \Rightarrow (b,c) \in R\,\& \,(b,c) \in S$.

By the way your explanations have helped immensely!

,

,

### the union of two transitive relation on a set s is not necessarily a transitive relation on s

Click on a term to search for related topics.