Prove that if $(a, b) \in \rho$ then $[a]_{\rho} = [b]_{\rho}$

138 Views Asked by At

Given an equivalence relation $\rho$ over the set $A$. Prove that if $(a, b) \in \rho$ then $[a]_{\rho} = [b]_{\rho}$. Also prove that if $(a, b) \notin \rho$ then $[a]_{\rho} \cap [b]_{\rho} = \emptyset $.

By the notation $[a]_{\rho} = \{b \ | \ (a, b) \in \rho\} $.

I have tried to do this problem intuitively, by drawing a graph: enter image description here

Since there is a path from a to be (i.e. $(a, b) \in \rho$) then the pairs $(a, b'_1), (a, b'_2), ...$ must exist. So $[a]_{\rho} = [b]_{\rho}$.

I have applied the same reasonig to the second point. Since there is no path from a to b, then the intersection of the two equivalence classes is $\emptyset$.

However this doesn't feel right. What is a more formal way of proving these 2 things?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $\rho$ be an equivalence relation over $A$. Assume that $(a,b) \in \rho$ and take some element $c \in [a]_\rho$. By definition of equivalence class, this means that $(a,c) \in \rho$, and by symmetry and transitivity, this means that $(b,c) \in \rho$, so also $c \in [b]_\rho$. We have thus proven that $[a]_\rho \subseteq [b]_\rho$, and a similar argument shows that $[b]_\rho \subseteq [a]_\rho$, so $[a]_\rho = [b]_\rho$.

For your second question, we show that contrapositive. Assume towards a contradiction that $[a]_\rho \cap [b]_\rho$ is non-empty, and let $c$ be an element of this intersection. Then we have $(a,c) \in \rho$ and $(b,c) \in \rho$. Again, using symmetry and transitivity, this means that $(a,b) \in \rho$.