0

Given:

Let $P$ be a partition of the set $S$. Let $a$ and $b$ in $S$. Relation $R$ on $S$: $a R b$ iff $a \in X$ and $b \in X$ for some $X \in P$. Then, $R$ is an equivalence relation.

I have asked this before, but I am not confident I understood the answer well enough.

Here's my attempt at proving it again. Please, see if it's correct.

Let $a$ be $\in S$. Since $P$ is a partition of $S$, there's $X \in P$ with $a \in X$.
By definition, $[a] = \{x \in S| a R x\}$. So, $[a] = X$. Let $\{[a]| a \in S\}$ be the set of all equivalence classes of $R$. Since $[a] = X$, $[a] \in P$ and $X \in \{[a]| a \in S\}$. So, $P = \{[a]| a \in S\}$

El-P
  • 33
  • 2

2 Answers2

1

Let $a\in S$. Since the union of all elements of $P$ is equal to $S$ we have $a\in X$ for some $X\in P$. Thus $R$ is reflexive.

Let $a,b,c\in S$ and suppose that $\def\r{\mathrel{R}}a\r b$ and $b\r c$. That is, $a,b\in X$ and $b,c\in Y$ for some $X,Y\in P$. Since $b\in X$ and $b\in Y$ and the sets forming a partition are disjoint, we must have $X=Y$. Thus $a\in X$ and $c\in X$, so $a\r c$. Thus $R$ is transitive.

Symmetric: try this for yourself: it's similar to, but a bit easier than, transitivity.

In your proof it appears to me that you are trying to show something further, namely: the set of equivalence classes of $R$ is equal to the given partition $P$. This is in fact true, but it's not the same thing as proving that $R$ is an equivalence relation.

David
  • 82,662
0

This is a classical result as shown in this paper : relations. To each partition on a set corresponds an equivalence relation and vice versa.

Marc Bogaerts
  • 6,197