Proof of Unique Equivalence Relation on Set w/ Partition Classes

[Ciaran]

Hello,

I've to construct a proof of the following statement: Prove that if S is a set and S_1... S_k is a partition of S, then there is a unique equivalence relation on S that has the S_i as its equivalence classes.

I'm really not sure how to go about this proof at all, so any help would be much appreciated!

 

[Evgeny.Makarov]

First make sure you understand the definitions of equivalence relation, equivalence class and partition. Also, look at several examples of how an equivalence relation induces a partition of a set into equivalence classes.

To construct an equivalence relation $R$, you need a way to say for any two given $x,y\in S$ whether $R(x,y)$ holds. You also need to show that there is only one answer to this question for given $S_1,\dots,S_k$. Note that $R(x,y)$ holds if and only if $y\in[x]$ ($y$ lies in the equivalence class of $x$) by definition of equivalence class. Well, since we have a partition, $x$ belongs to one and only one set, say, $S_i$. So how do you answer the question whether $R(x,y)$ holds? If $x$ belonged to more than one class, then there would be more than one way to answer it.

 

[Ciaran]

Hello,

Thanks for your reply! So what you're saying is that R(x,y) is that x and y lie in the same subset, namely S_i?

 

[Ciaran]

This is my proof- could you tell me what you think?

For a relation to be an equivalence relation, it must satisfy three conditions- it must be reflexive, symmetric and transitive.
The relation is reflexive as x ~ x means x is in the same subset as x, which is clearly true. The relation is symmetric as x~y means x and y belong to the same subset. This implies y and x belong to the same subset and so y~x. The relation is transitive as x~y means x and y belong to the same subset, and y~z means y and z belong to the same subset. Thus x and z belong to the same subset and thus x~z. Thus the relation is an equivalence relation.

 

[Evgeny.Makarov]

You are correct, but the problem also asks to show that this equivalent relation, i.e., $R(x,y)\iff\exists i\;(x,y\in S_i)$, has $S_1,\dots,S_k$ as its equivalence classes, and that such relation is unique.

 

[Ciaran]

Ah I see, so how would I go about doing that? I've never attempted a proof such as this.

 

[Evgeny.Makarov]

Ah I see, so how would I go about doing that?

Intuitively, equivalence classes are sets of equivalent elements, and elements are equivalent iff they belong to the same $S_i$. Therefore, equivalence classes are $S_i$ for $i=1,\dots,k$.

More precisely, you need to review the definition of equivalence classes of any given relation. We have $S=\bigcup_{i=1}^k S_i$. Let's suppose the definition says that the equivalence class of $x\in S$ with respect to $R$, denoted by $[x]$, is $\{y\in S\mid R(x,y)\}$ (the definition in your textbook or lecture notes may be slightly different, but essentially equivalent). Since $x\in S$, there is some $1\le j\le k$ such that $x\in S_j$. Since $S_i$ form a partition, they are disjoint, so $x\notin S_i$ for any $i\ne j$. Then
\begin{align}
R(x,y)&\iff\exists i\;(x\in S_i\text{ and }y\in S_i)&&\text{by definition of }R\\
&\iff y\in S_j&&\text{because }x\text{ is in }S_j\text{ and only }S_j.
\end{align}
Therefore,
\[
[x]=\{y\in S\mid R(x,y)\}=\{y\in S\mid y\in S_j\}=S_j
\]
Since $x$ was arbitrary and all equivalence classes have the form $[x]$ for some $x\in S$, every equivalence class is one of $S_i$. Conversely, by definition of partition, each $S_j$ is nonempty, so there exists an $x\in S_j$, and then, as shown above, $[x]=S_j$. So all $S_i$ are equivalence classes.

Now suppose there are two relations $R_1$ and $R_2$. Let's denote the equivalence classes of $x$ with respect to $R_1$ and $R_2$ by $[x]_1$ and $[x]_2$, respectively. We are given that $S_1,\dots,S_k$ are $[x]_1$ for various $x$, and similarly for $[x]_2$. Fix some $x\in S$ and suppose $j$ is the unique index such that $x\in S_j$. Then $[x]_1=[x]_2=S_j$ (Why?). Therefore,
\[
R_1(x,y)\iff y\in [x]_1\iff y\in [x]_2\iff R_2(x,y),
\]
so $R_1$ coincides with $R_2$.