# Show that the union of two equivalence relations G and H on A is transitive if G ◦ H ⊆ G ∪ H and H ◦ G ⊆ G ∪ H

The original question is: "Suppose G and H are equivalence relations on A. Then G ∪ H is an equivalence relation on A if and only if G ◦ H ⊆ G ∪ H and H ◦ G ⊆ G ∪ H"

At first, I assumed that G ∪ H is an equivalence relation and proved that G ◦ H ⊆ G ∪ H and H ◦ G ⊆ G ∪ H

The second assumption is that G ◦ H ⊆ G ∪ H and H ◦ G ⊆ G ∪ H. So I have to prove that G ∪ H is reflexive, symmetric and transitive. I have done the first two, but I'm stuck in the third one. I'm trying to solve it like this:

Suppose $$(a,b) \in G \circ H$$ and $$(b,c) \in G \circ H$$. (This means $$(a,b)\in G \cup H$$ and $$(b, c) \in G \cup H$$) Then by the definition of composition, $$(a,s) \in H \wedge (s,b)\in G$$ and $$(b, t) \in H \wedge (t,c) \in G$$

As $$((s,b)\in G \wedge (b, t)\in H)$$, $$(s, t) \in H\circ G$$

I don't know where to go from here. If I could somehow show that $$(s, t) \in G\circ H$$, then I could write

$$(s, d)\in H$$ and $$(d, t) \in G$$

$$(a, s) \in H \wedge (s, d) \in H$$ means $$(a, d) \in H$$

Similarly, $$(d, t) \in G \wedge (t, c) \in G$$ means $$(d, c) \in G$$

Thus, $$(a, d) \in H \wedge (d, c) \in G$$ means $$(a,c) \in G \circ H$$

Therefore, $$(a,c) \in G \cup H$$

Repeat the same thing for $$H\circ G$$

Any help would be appreciated. Thanks in advance :)

• You seem to be trying to prove the wrong thing. What you must prove is that $G\cup H$ is transitive, i.e., if $(a,b),(b.c)\in G\cup H$, then $(a,c)\in G\cup H$. You should do that using the inclusions in the hypothesis. Commented Oct 21, 2021 at 8:23
• That's precisely what I am trying to do. Supposing $(a,b)∈G∘H$ and $(b,c)∈G∘H$ gives $(a,b)∈G∪H$ and $(b,c)∈G∪H)$. Then I try to conclude that $(a,c)∈G∪H$. Commented Oct 21, 2021 at 8:40
• No, you must start by supposing that $(a,b),(b,c)$ are in $G\cup H$, not in $G\circ H$. Commented Oct 21, 2021 at 8:46

You have already proven that $$G\cup H$$ is reflexive and symmetric, so it remains to prove that it is transitive.
Suppose $$(a,b),(b,c) \in G\cup H$$.
You want to prove that $$(a,c) \in G\cup H$$.
If $$(a,b),(b,c) \in G$$, then $$(a,c) \in G \subseteq G\cup H$$; likewise if $$(a,b),(b,c) \in H$$.
If $$(a,b) \in G$$ and $$(b,c) \in H$$, then $$(a,c) \in G\circ H \subseteq G\cup H$$; likewise if $$(a,b) \in H$$ and $$(b,c) \in G$$.