3

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\}$.

Community
  • 1
El-P
  • 33
  • 2

1 Answers1

1

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$.

rogerl
  • 22,399
  • 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}$? – El-P Aug 25 '14 at 23:23
  • 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$. – rogerl Aug 25 '14 at 23:59
  • 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? – El-P Aug 26 '14 at 00:04
  • 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.) – rogerl Aug 26 '14 at 00:07
  • 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. – rogerl Aug 26 '14 at 00:09