1

There is this problem:

"What is the smallest equivalence relation on the set {1, 2, 3, 4, 5} containing the relation {(1,2), (1,3), (4,5)}?"

Per my understanding, an equivalence relation need to satisfy three properties, reflexivity, transitivity, and symmetry.

Per that requirement, wouldn't the smallest equivalent relation be {(1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,3), (4, 4), (4,5),(5,4), (5,5)}?

However, when I search the problem online, the set would include (2,3) and (3,2) in them. Why is there a need for these two elements? Why not even more elements such as (3,4) and (4,3), etc?

nguyen quanganh
  • 11

2 Answers2

0

You need to include in that equivalence relation $(2,3), (3,2)$ since you have in the set $(1,2)$ and $(1,3)$, and by the transitive property, those I have mentioned have to appear to. With respect to why $(3,4)$ and $(4,3)$ are not included, take into account that in the set you want to be contained there is $(1,3)$ and $(4,5)$. Since there is not any relationship between 1 and 4 or 5, there is no need for 3 and 4 to be in the same couple. In is the same as why $(1,5), (5,1)$ is not in that smallest set satisfying that.

Daniel C.
  • 1,275
  • 2
  • 24
0

With respect to the "smallest equivalence relation containing these pairs" consider drawing yourself a graph (more specifically a directed multigraph with loops and no parallel edges in the same direction).

For each element in your set, draw a point for that element. For each comparison in your relation, draw a directed edge from that point to the other point.

enter image description here

The smallest equivalence relation containing your pairs for such a graph is simply going to be the one where the equivalence classes are the connected components of the graph. Here, $\{1,2,3\}$ are all in the same connected component and so needs all possible pairs made using these: $\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$. Similarly, $\{4,5\}$ are in the same connected component and so we need all possible pairs made using these: $\{(4,4),(4,5),(5,4),(5,5)\}$. No others are needed.

JMoravitz
  • 79,518