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