1.2. Counterexamples and Properties of Equivalence Relations

This question you are given two equivalence relations on a non-empty set X. You are asked to prove or disprove whether R1 ∪ R2 is an equivalence relation or not. So, it turns out at a union of two equivalence relations need not be an equivalence relation. And this is demonstrated by this counter example. So, I consider my set X={a,b,c}. And let me have equivalence relations R1 and R2. So, R1 = {(a,a),(b,b),(c,c),(a,b),(b,a)} and R2 = {(a,a),(b,b),(c,c),(b,c),(c,b)}. It is easy to see that both of them are equivalence relations over the set X they are reflexive. Each of them is a reflexive relations symmetric relation and a transitive relation.

When we consider the union of two equivalence relations R1 and R2, it might not be an equivalence relation itself. Let's take the set X={a,b,c} and define R1 = {(a,a),(b,b),(c,c),(a,b),(b,a)} and R2 = {(a,a),(b,b),(c,c),(b,c),(c,b)}. Both R1 and R2 satisfy the properties of equivalence relations: reflexive, symmetric, and transitive. The reflexive property is satisfied because each element is related to itself, and the symmetric property is satisfied because if (x,y) is in the relation, then (y,x) is also included. However, when we look at the union R1 ∪ R2, this union is reflexive and symmetric but fails to be transitive. For instance, (a,b) is in R1 and (b,c) is in R2, but (a,c) is not in R1 ∪ R2, hence violating transitivity.

Think of two different clubs, each with its own set of members and a defined way to relate to each other. In Club A, every member is friends with each other, while Club B has some cross-friendships. If we consider all the friendships (the union of two clubs), people might know that they are friends with some but are not directly connected through the shared friendships. Thus, while you know some members are friends through one club or the other, not every friend relationship holds when combining both clubs.

In part b of question 1, we are supposed to prove whether the intersection is an equivalence relation or not. And it turns out that intersection of two equivalence relations over the same set X is always an equivalence relation. So, let us prove the three required properties. If I take R1 and R2 to be equivalence relations over the set X, then since R1 and R2 are individually reflexive relations, you will have ordered pairs of the form (a,a) present in both R1 as well as in R2. And as a result, you will have ordered pairs of the form (a, a) present in the intersection of R1 and R2 as well. That shows that R1 ∩ R2 is a reflexive relation.

When considering the intersection of two equivalence relations, R1 ∩ R2, it will always remain an equivalence relation. Let's verify this by examining the required properties: reflexive, symmetric, and transitive. First, for reflexivity: since both R1 and R2 have (a,a) for any element a in set X, their intersection must also have (a,a). Thus, the intersection is reflexive. For symmetry: if (a,b) exists in the intersection, then it exists in R1 and R2. Since both relations are symmetric, (b,a) must also be included in both R1 and R2, hence in the intersection. Lastly, for transitivity: if (a,b) and (b,c) are in the intersection, they are in both R1 and R2, and thus (a,c) would also be in both, ensuring transitivity is upheld. Therefore, R1 ∩ R2 is indeed an equivalence relation.

Consider two overlapping groups of friends. If one group represents people who are friends through work and another through school, the intersection of these two groups consists of friends who are recognized through both environments. As a result, they share mutual friendships that retain properties like knowing each other (reflexivity), their friendships are mutual (symmetry), and friends of friends are still friends (transitivity), ensuring that the intersection forms a cohesive network.

Now on question number 2 again, you are given two equivalence relations over a non-empty set and we want to prove that R1 ∪ R2 will be an equivalence relation if and only if the composition R1 ∘ R2 is equal to the R1 ∪ R2. This is, an if and only if statement. So, we have to give two proofs. We have to prove the implication in both the directions.

In this section, we are tasked with proving an important condition regarding the union of equivalence relations and their composition. Specifically, we need to show that the union, R1 ∪ R2, is an equivalence relation if and only if the composition R1 ∘ R2 equals R1 ∪ R2. First, we assume R1 ∘ R2 = R1 ∪ R2 and show R1 ∪ R2 is transitive. To establish this, consider pairs (a,b) and (b,c) from the union. There are several cases depending on which relation they belong to, and by verifying through these cases, we can show that (a,c) must also exist in the union. The reverse implication requires us to prove that if R1 ∪ R2 is an equivalence relation, then R1 ∘ R2 must equal R1 ∪ R2. This is done by showing that any relation in the composition also belongs to the union and vice versa.

Imagine two local transit systems in a city that connect major points. If the routes of both systems allow for seamless transfers, we can say the union of their routes can serve every destination (R1 ∪ R2 is a complete relation). For simplicity’s sake, if you can go from point A to point C by transferring at point B, this interconnected route reflects the essence of transitive relationships in the context of our set relations.

--