1
$\begingroup$

"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)

$\endgroup$
1
  • 3
    $\begingroup$ I changed $x/ɛ$={$y \in X$ | $yɛx$} to $x/ɛ=\{y \in X \mid yɛx\}$. The former is not proper MathJax usage. I also cleaned up numerous other instances in which you keep inexplicably alternating in and out of MathJax within an expression instead of just putting the whole expression in MathJax. ${}\qquad{}$ $\endgroup$ Jan 11, 2016 at 15:07

1 Answer 1

3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Why x/$\mathscr E$ and y/$\mathscr E$ are equal when they are non-empty? What does being non-empty have to do with x/$\mathscr E$ and y/$\mathscr E$ being equal? $\endgroup$
    – buzzee
    Jan 11, 2016 at 15:14
  • 1
    $\begingroup$ I didn't say that. $x/\mathcal E$ and $y/\mathcal E$ being equal is your hypothesis. Thus, $x/\mathcal E\cap y/\mathcal E = x/\mathcal E\cap x/\mathcal E = x/\mathcal E \not= \emptyset$ $\endgroup$ Jan 11, 2016 at 15:16
  • $\begingroup$ I don't understand "x/$\mathscr E$ x/$ and y/$\mathscr E$ are non-empty ; thus, if they are equal". Where can I find this in the theorem or proof? $\endgroup$
    – buzzee
    Jan 11, 2016 at 15:19
  • $\begingroup$ edited my answer to be (I hope) clearer $\endgroup$ Jan 11, 2016 at 15:23
  • $\begingroup$ Counterexample if $x/\mathcal E$={2, 3} and $y/\mathcal E$={5, 6}, then the intersection $x/\mathcal E \cap y/\mathcal E = {2,3}$\bigcap${5, 6} =$/emptyset$ $\endgroup$
    – buzzee
    Jan 11, 2016 at 15:38

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.