MHB Proof of Unique Equivalence Relation on Set w/ Partition Classes

Ciaran
Messages
71
Reaction score
0
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!
 
Physics news on Phys.org
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.
 
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?
 
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.
 
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.
 
Ah I see, so how would I go about doing that? I've never attempted a proof such as this.
 
Ciaran said:
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$.
 
Back
Top