0
$\begingroup$

"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 \cap y/\mathscr E \neq \emptyset$ if and only if $x\mathscr Ey$.
(c) $x\mathscr Ey$ if and only if $x/\mathscr E = y/\mathscr E$"

In the following proof of (c) I don't think it have to be as lengthy as like that

"Proof of Theorem 3

(c) It follows immediately from (a) and (b) above that x/$\mathscr E$ = y/$\mathscr E \Rightarrow x \mathscr E$ y

We need to prove that x$\mathscr E$y $\Rightarrow x/\mathscr E = y/\mathscr E$

Let x$\mathscr E$y. Then
$z\in x/\mathscr E \Rightarrow z\mathscr E x$ Def. 6
$z\mathscr Ex$ $\land$ $x\mathscr E y$ $\Rightarrow$ $z\mathscr Ey$ $\space\space\space\space\space\mathscr E$ is transitive.
$\Rightarrow z\in y/\mathscr E$ Def. 6
Since $z$ is arbitrary, it follows that $x/\mathscr E \subseteq y/\mathscr E$. A similar argument gives $y/\mathscr E \subseteq x/\mathscr E$; hence $x/\mathscr E \subset x/\mathscr E$ "
Source: Set Theory by You-Feng Lin, Shwu-Yeng T.Lin

The proof of Theorem 3 (c) can be shortened to the following:

$x/\mathscr E = y/\mathscr E$ $\Leftrightarrow$ $x/\mathscr E \cap y/\mathscr E = x/\mathscr E \neq \emptyset$ by Idemp, (a)
$\space\space\space\space\space\space\space\Leftrightarrow$ $x\mathscr E y$ by (b)

So there's no need to prove that $x\mathscr E y$ $\Rightarrow$ $x/\mathscr E = y/\mathscr E$, isn't it?

FYI

Idempotency law of set (Idemp.): P$\bigcap P\Leftrightarrow P$, P$\bigcup P\Leftrightarrow P$

Definition of equivalence class of $x$ in $X$ in symbols, $x/\mathscr E=\{y∈X| y \mathscr E x\} = \{y\in X | (y, x) \in\mathscr E\}$

"

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∈X∣y$\mathscr E$x}

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$∣x∈X} X/ɛ={x/$\mathscr E$$x\in X$}.

The symbol X/ɛ is read "X modulo $\mathscr E$," or simply "X mod $\mathscr E$".

$\endgroup$
5
  • $\begingroup$ Related post: math.stackexchange.com/questions/238940/… $\endgroup$ Jan 25, 2016 at 13:51
  • 2
    $\begingroup$ I think that Michael Hardy's comment on your previous post applies to the formatting of this post, too. $\endgroup$ Jan 25, 2016 at 13:53
  • $\begingroup$ The right-to-left implications in your attempt at a shorter proof of (c) reads $x E y\to x/E\cap y/E=x/E\ne \phi \to x/E=y/E.$ PROBLEMS: From (a) and (b) you have $x E y \to x/E\cap y/E \ne \phi,$ but how does $x/E \cap y/E \ne \phi$ imply that $x/E\cap y/E=x/E$ unless you already know what you are trying to prove (which is $xEy \to x/E=y/E $ )? $\endgroup$ Jan 25, 2016 at 22:23
  • $\begingroup$ @user254665 Aha. The right to left implication, doesn't suppose x/E=y/E, right? That cleared up my problem! Now I understand the proof $\endgroup$
    – buzzee
    Jan 26, 2016 at 5:16
  • $\begingroup$ Exactly. You will find that partitions and equivalence relations are a widely used, very useful tool in many subjects. $\endgroup$ Jan 26, 2016 at 20:56

1 Answer 1

3
$\begingroup$

Comment

From Def. 6 we have that: if $x \mathrel{\mathscr{E}}y$, then $x \in y/\mathscr E$.

From Th. 3(a) we have that: $x \in x/\mathscr{E}$

Thus, we have that:

if $x \mathrel{\mathscr{E}}y$, then $x \in x/\mathscr{E}\cap y/\mathscr{E} \neq \emptyset$.

Thus, how to conclude from: $x/\mathscr{E}\cap y/\mathscr{E}\neq \emptyset$ that $x/\mathscr{E} = y/\mathscr{E}$ ?

Consider the sets $A = \{ c \}$ and $B = \{ b, c \}$; we have two non-empty sets whose intersection is: $A \cap B = \{ c \} = A \ne \emptyset$.

But $A \ne B$.


Please, note that your version of "Idempotency" is wrong; we have:

$P \cap P = P$;

it is equality between sets, and not equivalence between sentences regarding sets.

$\endgroup$
5
  • $\begingroup$ Did you check the Theorem (3) and my reason? $$"x/E = y/E ⇔ [x/E⋂ y/E = x/E] ≠∅ ⇔ xEb"$$ $\endgroup$
    – buzzee
    Jan 25, 2016 at 10:54
  • $\begingroup$ = is a equality relation, but in the set theory book, "P∩P=P" is called idempotency law. $\endgroup$
    – buzzee
    Jan 25, 2016 at 10:59
  • $\begingroup$ @buzzee - but from Theorem 4 [page 42] (b) The idempotency laws: $A U A = A$ and $A ∩ A = A$, it does not follows that : "if $A ∩ B = A$, then $A=B$. $\endgroup$ Jan 25, 2016 at 11:06
  • $\begingroup$ Aha, come to think of it. The author sometimes used ⇔ where = is normally used, so "x/E∩y/E=x/E≠∅" in my reasoning can be (x/E∩y/E)⇔(x/E≠∅), so the iff between them is wrong. (x/E∩y/E)⇒(x/E≠∅) $\endgroup$
    – buzzee
    Jan 26, 2016 at 5:20
  • $\begingroup$ Oh, no, considering your sign again, mine should've been (x/E=y/E) ⇔ (x/E∩y/E=x/E)⇒(x/E∩y/E=≠∅), but I had thought (x/E=y/E) ⇔ (x/E∩y/E=x/E) ⇔(x/E∩y/E=≠∅). $\endgroup$
    – buzzee
    Jan 26, 2016 at 5:37

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.