Let $S=\{a,b,c,d\}$ and let $\mathscr{P}=\{ \{ a \}, \{ b,c \}, \{ d \} \}$. Note that $\mathscr{P}$ is a partition of $S$. Describe the equivlanece relation $\textbf{R}$ on $S$ determined by $\mathscr{P}$ as indicated in Theorem 6.15.

Theorem 6.15 states, "Let $\textbf{R}$ be an equivalence relation on a set $S$. Then $\{ E_x:x \in S \}$ is a partition of $S$. The relation 'belongs to the same piece as' is the same as $\textbf{R}$. Converseley, if $\mathscr{P}$ is a partition of $S$, let $\textbf{R}$ be defined by $x\textbf{R}y$ iff $x$ and $y$ are in the same piece of the partition. Then $\textbf{R}$ is an equivalence relation and the corresponding partition into equivalence classes is the same as $\mathscr{P}$"

A relation acts on a set if $(x,y)\in \textbf{R}$. Since $\mathscr{P}$ has three members that must mean there are three pieces of the partition (and thus three seperate equivalence classes). $E_h=\{y \in S:y\textbf{R}h \}$, $E_i=\{y\in S: y\textbf{R}i \}$, $E_j=\{y\in S: y \textbf{R} j \}$.

Each piece of the partition (i think) can be used to construct the ordered pairs of the members of the relation $\textbf{R}$ by simply using the members of each equivalence class in all possible combinations of ordered pairs similar to below.

$\mathscr{P}=\{ \underbrace{\{ a \}}_{(a,a)}, \underbrace{\{ b,c \}}_{(b,b),(b,c),(c,b),(cc)}, \underbrace{\{ d \}}_{(d,d)} \}$

This yields the relation to be $\textbf{R}=\{(a,a),(b,b),(b,c),(c,b),(c,c),(d,d) \}$ which according to the book is the correct answer. However I pretty much worked this out going backwards (starting from the answer and working my way to the original practice problem) so I am unsure if my understanding of the difference between pieces of a partition and thee members of the equivalence class are correct. Is there a more formal way to figure out the equivalence relation $\textbf{R}$?

  • $\begingroup$ what is $\{E_z:x\in S\}$ supposed to mean? $\endgroup$ – Pink Panther Jul 30 '19 at 17:44
  • 1
    $\begingroup$ It seems your understanding is correct. For each piece of the partition, make all possible pairs of their members; the equivalence class is the union of these sets of pairs. It is actually very simple. $\endgroup$ – amrsa Jul 30 '19 at 17:46
  • $\begingroup$ Typo my apologies, it actually says. "Then $\{E_x:x \in S \}$ is a partition of $S$." $\endgroup$ – kristhedemented Jul 30 '19 at 17:46

The equivalence relation $\mathbf{R}$ is defined by

for all $x,y\in S$, $(x,y)\in\mathbf{R}$ if and only if there exists $E\in\mathscr{P}$ such that $x,y\in E$.

This is easily seen to be an equivalence relation that induces the same partition on $S$.

Thus $$ \mathbf{R}=\bigcup_{E\in\mathscr{P}}(E\times E) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.