Show Proof Equivalance

Question

Question: Assume $P$ is a partition on a set $A$ and define $$R_p=\{(a, b)\in A\times A : \exists U\in P (a\in U)\land (b\in U)\}$$

Show that $R_p$ is an equivalence relation on $A$.

In this question, I thought I could create a set such as $\{1,2,3\}$ then I write partitions but I couldn’t understand there is exist $U$ part so I need your help and my set is it suitable?

Answer 1

The sentence "there exists a $U\in P$" means that there is a set $U$ which is in the partition of the set $A$. For example, one partition of the set $\{1, 2\}$ is $P=\{\{1\}, \{2\}\}$. Then we could take $U$ to be the set $\{2\}$.

The question has already asked you assume that a partition of the set $A$ exists. You just have to show that the relation satisfies reflexivity, symmetry and transitivity.

In other words, you have to show that

• For every $a\in A$, there exists a set $U$(one exists because there exists a partition of $A$) such that $a\in U$ and therefore $(a, a)\in R_p$.

• If $(a, b)\in R_p$, then $(b, a)\in R_p$(Here you can assume that $a\in U$ and $b\in U$ because $(a, b)\in R_p$).

• If $(a, b)\in R_p$ and $(b, c)\in R_p$, then $(a, c)\in R_p$(again, you can assume that $a, b, c\in U$ as $(a, b), (b, c)$ is already an element of $R_p$).

I hope this helps!

Answer 2

We need to show that $R_p$ is reflexive, symmetric, and transitive.

Reflexivity: Let $a$ be any element in $A$. Since $P$ is a partition, there must be a set $U\in P$ such that $a\in U$. If $a\in U$, then $(a,a) \in R_p$ since $a\in U$ by assumption.

Symmetry: Let $a, b \in A$ be elements such that $(a,b) \in R_p$. This implies that there exists $U\in P$ such that $a\in U$ and $b \in U$. Since we have $b\in U$ and $a \in U$, we can conclude that $(b,a) \in U$.

Transitivity: Let $a,b,c \in A$ be elements satisfying $(a,b) \in R_p$ and $(b,c) \in R_p$. Since $(a,b) \in R_p$, there exists $U\in P$ such that $a \in U$ and $b \in U$. Similarly, there exists $V\in P$ such that $b \in V$ and $c \in V$ as $(b,c) \in R_p$. Since $P$ is a partition, we have $U \cap V= \emptyset$. Thus, $b$ cannot be in $U$ and $V$ at the same time unless $U=V$. Therefore, we must have $U=V$. As a result, $c \in U$ since $U=V$. Therefore, $(a,c) \in R_p$ as $a\in U$ and $c \in U$.