1.1.1. Introduction to Tutorial 4: Part I

In 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. It turns out that a union of two equivalence relations need not be an equivalence relation. To demonstrate this, consider a counter-example where X = {a, b, c} and the equivalence relations R1 and R2 are defined as: R1 = {(a, a), (b, b), (c, c), (a, b), (b, a)} R2 = {(a, a), (b, b), (c, c), (b, c), (c, b)}. It is easy to see that both of these relations are equivalence relations over the set X as they satisfy reflexivity, symmetry, and transitivity.

This chunk focuses on the importance of equivalence relations and their unions. Equivalence relations are defined by three properties: reflexivity (every element is related to itself), symmetry (if a is related to b, then b is related to a), and transitivity (if a is related to b, and b is related to c, then a is related to c). Here, we illustrate that while each individual relation, R1 and R2, satisfies these properties, their union R1 ∪ R2 might not satisfy all properties. Specifically, even though both R1 and R2 are reflexive and symmetric, the union is not necessarily transitive. An example illustrates this point clearly: the presence of (a, b) and (b, c) in the union without (a, c) results in a violation of transitivity.

Consider a social network where R1 represents friendships and R2 represents coworkers. Just because you are friends with someone and someone else is a coworker does not mean you are directly connected to the second person. In other words, knowing someone through different relationships does not guarantee a direct tie between you and all of their connections.

The union R1 ∪ R2 is reflexive over the set X because ordered pairs (a, a), (b, b), and (c, c) are present in this relation. It is also symmetric since if (a, b) is in the union, then (b, a) is also present. However, it is easy to see that the union is not a transitive relation. For instance, if (a, b) is in R1 ∪ R2 and (b, c) is in R2, (a, c) is not necessarily in the union. Hence, generally, while the union of two equivalence relations is always reflexive and symmetric, it need not be transitive.

This chunk assesses the characteristics of the union of two equivalence relations. Even when we take the union of R1 and R2, we still find that this union maintains reflexivity and symmetry. However, it fails the transitivity test, which is crucial for establishing if this union can be classified as an equivalence relation. Thus, we confirm the mixed properties of this union: guaranteed reflexivity and symmetry, but questionable transitivity.

Think of this situation in the context of class relationships: being in the same study group (R1) and participating in a club together (R2). Just because you study with Sarah and Sarah is in the club with John doesn’t mean you and John are connected directly in any way. While you both share a connection through Sarah (reflexive), and you both know Sarah (symmetric), without a direct link you are not guaranteed any simple relationship (transitive).

--