1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – amrsa
    Commented Oct 21, 2021 at 8:23
  • $\begingroup$ 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$. $\endgroup$
    – user208872
    Commented Oct 21, 2021 at 8:40
  • $\begingroup$ No, you must start by supposing that $(a,b),(b,c)$ are in $G\cup H$, not in $G\circ H$. $\endgroup$
    – amrsa
    Commented Oct 21, 2021 at 8:46

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .