3
$\begingroup$

Theorem:

Let $P$ be a partition of a set $S$, and let $a$ and $b$ be $\in S$. Define the relation $R$ on $S$ as follows: $aRb$ iff there exists an $X \in P$ such that $a \in X$ and $b \in X$. Then $R$ is an equivalence relation on $S$. Furthermore, the set of equivalence classes of $R$ is equal to $P = \{[a]: a \in S\}$.

Proof for the bolded part:

Let $a \in S$. Then there exists an $X \in P$ such that $a \in X$.

$[a] = \{x: aRx\} = X$

So, the set of all equivalence classes of the relation R is the original partition: $P = \{[a]: a \in S\}$

Is the proof excerpt above saying this:

Let $a \in S$. Then there exists an $X \in P$ such that $a \in X$. So, $P =\{X: a \in X\}$. Thus $[a] = \{x: aRx\} = X$. Therefore $P = \{[a]: a \in S\}$.

$\endgroup$
1
$\begingroup$

Your statement $P = \{X\ :\ a\in X\}$ is not correct. $P$ is the set of all elements of the partition, while $\{X\ :\ a\in X\}$ consists only of that element of the partition containing $a$.

The portion of the proof you quoted is saying this: choose $a\in S$; then there is a $X\in P$ such that $a\in X$. By definition of $R$, $[a] = \{b\in S\ |\ b\sim a\} = \{b\in S\ |\ b\in X\} = X$. So each equivalence class of $R$ is a member of the partition $P$. Conversely, each member of the partition is an equivalence class; to see this, let $X\in P$ and choose $a\in X$. Then $[a] = X\in P$.

$\endgroup$
  • $\begingroup$ Let $a \in S$. Then there exists an $X \in P$ such that $a \in X$. That proves $[a] = X$. Is there a piece of info missing between that and the conclusion? I mean do we assume that $P$ is the set of all $X$'s? So since $P = \{X\}$ and $[a] = X$,then $P = \{[a]: a \in S\}$? $\endgroup$ – El-P Aug 25 '14 at 23:23
  • $\begingroup$ The first part of the argument (the one you quoted) shows that each $[a]$ is some $X\in P$. The second part of the argument, which is required but is almost trivial, is that each $X\in P$ is $[a]$ for some $a\in S$. $\endgroup$ – rogerl Aug 25 '14 at 23:59
  • $\begingroup$ Sorry to keep bothering you like that, but I am very shaky with this stuff, so just to be on the safe side, are you agreeing with me? Is $P = \{X\}$ assumed? $\endgroup$ – El-P Aug 26 '14 at 0:04
  • $\begingroup$ Sort of, yes. Certainly $P$ is a set of things, and you have named at least one of those things $X$. But just saying that $P = \{X\}$ without further qualification just isn't precise. You are given some partition $P$, and you can call any particular element of the partition anything you'd like. (I realize this may not be clear, but I hope it is.) $\endgroup$ – rogerl Aug 26 '14 at 0:07
  • $\begingroup$ Let me try one more time. The first part of the argument shows that $[a]\in P$ for any $a\in S$. That shows that each equivalence class is a member of the partition. But we also need to show that each member of the partition is an equivalence class. So choose any member of the partition; call it $X$. Since $X$ is not empty, choose $a\in X$; then the argument [way] above shows that $X = [a]$. Thus an arbitrary member of the partition is an equivalence class. $\endgroup$ – rogerl Aug 26 '14 at 0:09

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.