Where in (a) and (b) above shows that $x/\mathscr E = y/\mathscr E \Rightarrow x \mathscr E y$?

74 Views Asked by At

"Definition 6. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. For each $x \in X$, we define

$x/ \mathscr E=\{y \in X \mid y\mathscr Ex\}$

which is called the equivalence class determined by the element x.

The set of all such equivalence classes on $X$ is denoted by $X/\mathscr E$; that is, $X/\mathscr E=\{x/\mathscr E \mid x \in X\}$. The symbol $X/\mathscr E$ is read "$X$ modulo $\mathscr E$," or simply "$X$ mod $\mathscr E$".

Theorem 3. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. Then

(a) Each $x/\mathscr E$ is a nonempty subset of $X$.

(b) $x/\mathscr E \bigcap y/\mathscr E \neq \emptyset$ if and only if $x\mathscr Ey$.

(c) $x\mathscr E y$ if and only if $x/\mathscr E = y/\mathscr E$.

[Proof]

(a) Since $\mathscr E$ is reflexive, for each $x \in X$, we have $x \mathscr E x$. By Definition 6, $x \in x / \mathscr E$ and hence $x / \mathscr E$ is a nonempty subset of $X$.

(b) Since $\mathscr E$ is an equivalence relation and $X \neq \emptyset$, we have

$x/\mathscr E \bigcap y/\mathscr E \neq \emptyset \Leftrightarrow \exists z(z \in x /\mathscr E \land z \in y/ \mathscr E)$

$\Leftrightarrow z \mathscr E x \land z \mathscr E y$ by definition 6

$\Leftrightarrow x \mathscr E z \land z \mathscr E y \mathscr E$ is symmetric

$\Leftrightarrow x \mathscr E y \mathscr E$ is transitive

(c) It follows immediately from (a) and (b) above that $x/\mathscr E = y/\mathscr E \Rightarrow x \mathscr E y$. ..." Source: Set Theory by You-Feng Lin, Shwu Yeng T. Lin

I don't understand what's written in the proof of (c) "It follows immediately from (a) and (b) above that $x/\mathscr E = y/\mathscr E \Rightarrow x \mathscr E y$". Where in (a) and (b) above shows that $x/\mathscr E = y/\mathscr E \Rightarrow x \mathscr E y$?

[EDIT] I understand it now.

Suppose (x/$\mathscr E$=y/$\mathscr E$)

then, (x/$\mathscr E$=y/$\mathscr E )\neq \emptyset$ by (a)

$\Leftrightarrow$ (x/$\mathscr E \bigcap$ y/$\mathscr E = x$ /$\mathscr E$) $\neq \emptyset$ by Idempotency law

$\Leftrightarrow x \mathscr E y$ by (b)

1

There are 1 best solutions below

7
On

You want to show $x/\mathcal E = y/\mathcal E \Rightarrow x = y$. Suppose then $x/\mathcal E = y/\mathcal E$.

From (a), you know that $x/\mathcal E$ and $y/\mathcal E$ are non-empty. Then the intersection $x/\mathcal E \cap y/\mathcal E = x/\mathcal E \cap x/\mathcal E = x/\mathcal E$ is not empty.

By (b), $x\mathcal E y$.

Edit : Note that, at least to me, it is not the clearest way to show that. If the equivalences classes are equal, then as $x\in x/\mathcal E$, $x \in y/\mathcal E$. It means exactly $x\mathcal E y$.